m数据结构 day16 图（六）拓扑排序：为有向无环图构造拓扑序列

拼搏现实的明天。 2023-03-13 09:25 16阅读 0赞

### 文章目录 ###

*  拓扑排序
 *   *  基础
     *   *  主角：有向无环图 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的前面。

拓扑序列**不唯一**。  
![在这里插入图片描述][2020051511245521.png]

### AOV网 VS AOE网 ###

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

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

#### AOV网（点表示活动，弧表示活动之间的制约关系） ####

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

#### AOE网（弧表示活动，弧的权值表示活动的持续时间，点表示事件） ####

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

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]

### 拓扑排序判断网是否有环 ###

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

## 算法1：khan算法，思路好理解, O ( n + e ) O(n+e) O(n\+e) ##

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

khan算法：  
![在这里插入图片描述][20200515121543305.png]

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

![在这里插入图片描述][20200515122205421.png]

比如，下面这个图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]  
转换为邻接表存储结构为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]

### 代码 ###

#### 边结点结构，顶点结点结构，邻接表结构 ####

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++实现，[来自这个博文][Link 1]，也很好，用了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，代码好写 ##

### 代码 ###

也来自[这个博文][Link 1]

//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);
        }
    }

[2020051511245521.png]: /images/20230312/96c886f7c5c84e9eb48bd5a1e38ae6cd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200515165802358.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200515121543305.png]: https://img-blog.csdnimg.cn/20200515121543305.png
[20200515122205421.png]: https://img-blog.csdnimg.cn/20200515122205421.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200515122249617.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200515122306676.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[Link 1]: https://blog.csdn.net/baodream/article/details/80368764