DAG图中的拓扑排序

港控/mmm° 2021-09-21 06:18 308阅读 0赞

### 拓扑排序 ###

*   *  概念
     *  思想
     *  代码
     *  应用

## 概念 ##

> DAG是指有**向无环图**，而拓扑排序是有向无环图的一个具体应用。拓扑排序是指将DAG图的顶点排成一个线性的序列。这个线性的序列是满足一下规则的：如果在DAG图中存在v->u，那么在这个序列中v一定是排在u的前面的

## 思想 ##

拓扑排序在实际生活中有着广泛的应用。比如排课。如下图就是一个拓扑排序的例子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ljemZ5NTg1_size_16_color_FFFFFF_t_70]  
要求按照上图给出一个合理的排课序列。观察有向图的先序关系，我们可以很容易发现比如：

A -> B -> C -> D -> E -> F -> G -> H

就是一个合理的序列。当然，我们发现，如果一个DAG图中存在没有直接或是间接关系的先导的顶点的话，这两个顶点的先后顺序是任意的。对于该图拓扑排序的结果是不唯一的。  
那么，我们如何来实现拓扑排序呢？可以这样来想：

1.  首先定义一个队列Q，将图中所有入度为0的顶点入队
2.  取出队首的元素，输出（就会得到排序的元素），然后删除以该顶点为起点的边，并且将连接该顶点的其他顶点的入度减一。若某个顶点的入度减为0，那么就将改顶点加入到队列中。
3.  反复执行（2）操作，知道队列为空，如果队列为空时如果队的结点数目恰好为N，说明拓扑排序成功，否则说明G中存在环。

## 代码 ##

vector<int>G[maxn];//存储图 
    int n,m,inDegree[maxn]; //顶点数，边数，每个顶点的入度 
    
    bool toplogicalSort(){ 
    	//返回true表示排序成功
    	int num=0; //记录入队顶点数 
    	queue_priority<int,vector<int>,greater<int>> Q; //设置数字小的优先级高 
    	//将入度为0的顶点全部入队
    	for(int i=1; i<=n; i++){ 
    		if(inDegree[i]==0){ 
    			Q.push(i);
    		}
    	}
    	while(!Q.empty()){ 
    		int u = Q.top();
    		printf("%d ",u); //输出 
    		Q.pop();
    		for(int i=0; i<G[u].size(); i++){ 
    			int v = G[u][i]; //u的后继结点
    			inDegree[v]--;
    			if(inDegree[v] == 0){ 
    				Q.push(v);
    			} 
    		}
    		//清空以u为起点的边
    		G[u].clear();
    		num++; 
    	} 
    	if(num == n)return true;
    	else return false;
    }

## 应用 ##

拓扑排序的一个重要的应用就是判断给定的有向图是否存在环，上面的代码当返回为false时就是表明存在环。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ljemZ5NTg1_size_16_color_FFFFFF_t_70]: /images/20210920/d1352fb8d580491494249e650d395fa4.png