数据结构拓扑排序

古城微笑少年丶 2022-03-19 03:43 248阅读 0赞

拓扑排序是将有向无环图G的所有顶点排成一个线性序列,使得对图G中的任意两个顶点,如果存在u->v,那么u一定在v的前面

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsZXgxOTk3MjIy_size_16_color_FFFFFF_t_70][]

比如在这张图中,学科的学习要按照一定的顺序,学习了某些课程后,才能学习接下来的课程

学习顺序就可以按照拓扑排序算法得出:

1.定义1个队列Q,并把所有入度为0得结点加入队列Q

2.取队首结点,输出。然后删除它所有从它出发的边,然后令这些边到达的结点的入度-1

3.此时如果某个结点入度为0,那么就将这个结点入队

4.重复上述操作,直到队列为空

如果元素出队次数！=图中结点个数,那么这个图中就存在环,该图就不是拓扑排序

![20190214213326153.png][]

代码如下:

#include <iostream>
    #include <algorithm>
    #include <queue>
    #include <vector>
    using namespace std;
    const int MAXN = 510;
    vector<int> GEdges[MAXN];
    int n, m;
    int indegree[MAXN];  //每个顶点的入度数
    
    //拓扑排序
    bool topologyOrder() {
    	queue<int> oder_queue;
    	int num = 0;
    	for (int i = 0; i < n; ++i) {
    		if (indegree[i] == 0) {
    			oder_queue.push(i);
    		}
    	}
    	while (!oder_queue.empty()) {
    		int vertex = oder_queue.front();
    		oder_queue.pop();
    		for (int adj_vertex : GEdges[vertex]) {
    			indegree[adj_vertex]--;
    			if (indegree[adj_vertex] == 0) {
    				oder_queue.push(adj_vertex);
    			}
    		}
    		GEdges[vertex].clear();
    		num++;
    	}
    	if (num == n) return true;
    	else return false;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsZXgxOTk3MjIy_size_16_color_FFFFFF_t_70]: /images/20220319/ffcb73ad8a49472c9cc9c4877a0ac017.png
[20190214213326153.png]: /images/20220319/6edd8e823a824633903235534ae334f3.png