m数据结构 day16 图(六)拓扑排序:为有向无环图构造拓扑序列

2024-03-08 09:30

本文主要是介绍m数据结构 day16 图(六)拓扑排序:为有向无环图构造拓扑序列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 拓扑排序
    • 基础
      • 主角:有向无环图 DAG
      • AOV网 VS AOE网
        • AOV网(点表示活动,弧表示活动之间的制约关系)
        • AOE网(弧表示活动,弧的权值表示活动的持续时间,点表示事件)
      • 拓扑排序判断网是否有环
    • 算法1:khan算法,思路好理解, O ( n + e ) O(n+e) O(n+e)
      • 代码
        • 边结点结构,顶点结点结构,邻接表结构
        • 拓扑排序,要用栈来存储入度为0的点
    • 算法2:基于DFS,代码好写
      • 代码

拓扑排序

拓扑排序是很重要的,对于DAG有很大的应用价值。

基础

主角:有向无环图 DAG

有向无环图常常应用于工程规划中,通过拓扑排序可以有效分析出一个图中是否有环,如果不存在,那么他的拓扑序列是什么。

看了B站几个视频,大致了解了一点,现在开始自己看书,自己思考,自己总结。

拓扑排序要做的事情:把有向无环图的所有顶点排成一条线性序列,即拓扑序列。拓扑序列需要满足的唯一条件就是:只要v到w能走通,那v就必须排在w的前面。

拓扑序列不唯一
在这里插入图片描述

AOV网 VS AOE网

所有讲拓扑排序的视频和书都要提到这两个名词,所以这两个词很重要,还是要好好理解一下。

我觉得这两种网络就是就是两种特殊的图而已,特殊在于他们都是对工程建模,是为了适应某种工程应用需求而产生的,所以让顶点,边,权表示和普通网图不一样的含义,对他们使用的算法(比如对AOV拓扑排序,对AOE找关键路径)也和普通网图不一样,但这些不一样都是为了去迎合他们背后的应用需求,所以给他们起个特殊名字也并不难理解,因为他们也具有了一定通用性,塑造了一个不可忽视的类型。

AOV网(点表示活动,弧表示活动之间的制约关系)

AOV网,activity on vertex network, 一般用于表示工程的流程。即用顶点表示活动的有向网,而弧表示活动之间的制约关系,主要是活动执行的先后顺序。AOV网中不能有回路,因为你不能要求某个活动的执行要以自己的执行为先决条件。

AOE网(弧表示活动,弧的权值表示活动的持续时间,点表示事件)

AOE网,activity on edge network,用弧表示活动的有向网,弧的权值表示活动的持续时间,用顶点表示事件

AOE网中没有入边的顶点叫做始点或者源点,没有出边的顶点称为终点或者汇点

正常情况下,AOE网只有一个源点和一个汇点。因为一个工程只有一个开始和一个结束。比如:

在这里插入图片描述

拓扑排序判断网是否有环

如果拓扑排序能把网的所有顶点都输出,则无环;否则有环,且剩下的顶点们就是环的顶点(可能不止一个环)。就算只少了一个顶点也是有环,即少的那个顶点的自环。

算法1:khan算法,思路好理解, O ( n + e ) O(n+e) O(n+e)

拓扑排序的实现算法不止一种,常见的有两个,一个是khan算法,一个是基于深度优先搜索的,各有特点,khan算法适合考试,因为容易理解,容易做题,但是计算机上代码相对复杂点。而基于DFS的,则理解起来难一点,因为是逆序,但是代码极其简单,所以工程中用的更多。

khan算法:
在这里插入图片描述

这个思路,需要删除顶点以及顶点的出边,所以邻接表存储结构很适合,但是又要知道每个顶点的入度是否为0,所以需要给邻接表的结点结构增加一个数据域,存储入度。

在这里插入图片描述

比如,下面这个图:
在这里插入图片描述
转换为邻接表存储结构为:
在这里插入图片描述

代码

边结点结构,顶点结点结构,邻接表结构
typedef struct EdgeNode
{int adjvex;//弧头顶点的下标int weight;//权值struct EdgeNode * nextEdge;
}EdgeNode;typedef struct VertexNode
{int in;//入度int data;EdgeNode * firstEdge;
}VertexNode, AdjList[MAXVEX];typedef struct
{AdjList adjlist;int numV, numE;
}GraphAdjList;
拓扑排序,要用栈来存储入度为0的点

当然用队列也是可以的,但是这里用数组做一个动态的栈最方便,记得函数最后一定要释放内存哦

/*如果图G没有环,则输出拓扑序列并返回true,否则返回false*/
bool TopologicalSort(GraphAdjList * G)
{int count = 0;//已输出顶点的个数int * stack;//栈,存储入度为0的顶点int top = -1;//指向栈顶stack = (int *)malloc(G->numV * sizeof(int));//动态分配内存,避免宏定义值过大带来或过小的问题int i;//遍历所有顶点,把入度为0的顶点的在顶点表数组的下标入栈for (i=0;i<G->numV;++i)if (G->adjlist[i].in == 0)stack[++top] = i;int gettop;EdgeNode * e;while (top!=-1){gettop = stack[top--];//取出栈顶元素printf("%d -> ", G->adjlist[gettop].data);//打印这个元素,即加入拓扑序列++count;//遍历此顶点的边表,把边表的每个结点的顶点的入度减1(相当于删去了第gettop个点和他的出边)int k;for(e=G->adjlist[gettop].firstEdge;e!=NULL;e=e->nextEdge){k = e->adjvex;if (!(--G->adjlist[k].in))//如果这些顶点入度更新为0则也入栈stack[++top] = k;}}free(stack);if (count < G->numV)return false;return true;
}

时间复杂度分析:

不考虑有环的图,因为无环图需要的操作更多。第一个for把所有入度为0的点入栈, O ( n ) O(n) O(n);而后面的while循环里,每一个点出栈,都要执行他的出度边数目的操作次数,所有点都要出栈,所以总共的操作系数是总的边数,即e,所以是 O ( e ) O(e) O(e).

所以总的是 O ( n + e ) O(n+e) O(n+e)

下面的C++实现,来自这个博文,也很好,用了vector

//Kahn算法,关键在于需要维护一个入度为0的顶点的集合
int n,m;
int inDeg[N];  //i点的入度
vector<int>vec[N];  //i点的邻接表,即i与哪些点相连
int ans[N];    //排序结果数组int topSort()    //返回值代表是否有环,排序结果在ans数组
{int cnt=0;queue<int>q;  //如果需要相同优先级的顶点,序号小的先输出,则可建立优先队列,即//priority_queue<int,vector<int>,greater<int> >q;while(!q.empty())q.pop();for(int i=1;i<=n;i++)if(inDeg[i]==0)q.push(i);while(!q.empty()){int now = q.front();q.pop();ans[++cnt]=now;     //个数+1并存数组int len = vec[now].size();for(int i=0;i<len;i++){inDeg[vec[now][i]]--;if(inDeg[vec[now][i]]==0)q.push(vec[now][i]);}}return (cnt==n)?1:0;  //是否等于n,等于n代表无环
}void init()  //输入数据,n个点,m条边
{int x,y;cin>>n>>m;for(int i=1;i<=n;i++)vec[i].clear();memset(inDeg,0,sizeof(inDeg));for(int i=1;i<=m;i++){cin>>x>>y;inDeg[y]++;vec[x].push_back(y);}
}

算法2:基于DFS,代码好写

代码

也来自这个博文

//dfs实现,从出度的角度来构造,递归到最后返回
int n,m;
vector<int>vec[N];  //i点的邻接表,即i与哪些点相连
int ans[N],cnt;    //排序结果数组,cnt记录个数
int parent[N]; //记录其前置节点
//int d[N], Time, f[N]; //可以不要,时间time初始化为0,d[]记录第一次被发现时,f[]记录结束检查时
int vis[N];  //标记数组vis[i]=0表示还未访问过点i,c[i]=1表示已经访问过点i,并且还递归访问过它的所有子孙,c[i]=-1表示正在访问中,尚未返回bool dfs(int s)  //深度优先搜索(邻接表实现),记录时间戳,寻找最短路径
{vis[s]=-1;   //正在访问//Time++;d[s]=Time;int len = vec[s].size();for(int i=0;i<len;i++){int tmp=vec[s][i];if(vis[tmp]<0) //如果子孙比父亲先访问,说明存在有向环,失败退出return false;else if(!vis[tmp]&&!dfs(tmp)) //如果子孙未被访问,访问子孙返回假,说明也是失败return false;parent[tmp]=s;}vis[s]=1;//Time++;f[s]=Time;ans[cnt++]=s;  //结果是逆序的,递归的原因return true;
}bool topSort()    //返回值代表是否有环,排序结果在ans数组
{cnt=0;for(int i=1;i<=n;i++){parent[i]=-1;vis[i]=0;}//Time=0;for(int i=1;i<=n;i++)if(!vis[i])if(dfs(i)==false)return false;return true;
}void init()  //输入数据,n个点,m条边
{int x,y;for(int i=1;i<=n;i++)vec[i].clear();for(int i=1;i<=m;i++){cin>>x>>y;vec[x].push_back(y);}
}

这篇关于m数据结构 day16 图(六)拓扑排序:为有向无环图构造拓扑序列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/786686

相关文章

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

【软考】希尔排序算法分析

目录 1. c代码2. 运行截图3. 运行解析 1. c代码 #include <stdio.h>#include <stdlib.h> void shellSort(int data[], int n){// 划分的数组,例如8个数则为[4, 2, 1]int *delta;int k;// i控制delta的轮次int i;// 临时变量,换值int temp;in

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图