# 有向图的拓扑排序
图的创建与遍历
给定节点数和边数,以及构成每条边的两个节点。
构造图:

要存储上面的图,需要h[N], e[N], ne[N]来表示
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| # include <iostream> # include <cstring>
using namespace std;
const int N = 100010; int h[N]; int e[N]; int ne[N]; int idx;
void add(int a, int b){ e[idx] = b; ne[idx] = h[a]; h[a] = idx++; }
int main(){ memset(h, -1, sizeof(h)); int n,m; cin>>n>>m; int a,b; for(int i=0; i<m; i++){ cin>>a>>b; add(a,b); } for(int i=1; i<=n; i++){ cout<<"以节点"<<i<<"为起始点,与其相邻的边有:"; for(int j = h[i]; j!=-1; j = ne[j]){ int eb = e[j]; cout<<eb<<" "; } cout<<endl; } }
|

拓扑排序
拓扑排序:
若一个由图中所有点构成的序列 A 满足:对于图中的每条边 (𝑥,𝑦),𝑥 在 𝐴 中都出现在 𝑦 之前,则称 𝐴 是该图的一个拓扑序列。
如:下面的图,能找到序列:1 —— 2 —— 4 —— 3 ——5构成一条拓扑序列

判断方法:
- 删除一个入度为0的节点,加入结果集合
- 将上述节点对应的有向边都删除,重复第一步
- 直到最后没有节点,则该图可找出拓扑序列
代码实现重点:
- 现把入度为0的节点加到集合的,后面删除该节点对应的边时要先删除:可以使用队列存储
- 删除节点a对应的有向边:可以遍历a为起始的连接边,将这些对应的点的入度-1即可
- 直到最后没有节点:队列为空时,结果集为整个图的节点个数
实现
用一个d[N]数组来存储每个点的入度数
队列q存储所有入度为0的节点
数组v存储答案
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
| # include <iostream> # include <queue> # include <vector> # include<cstring> # include <algorithm>
using namespace std;
const int N = 100010; queue<int> q; vector<int> v;
int e[N], ne[N],h[N]; int d[N]; int idx; int n,m; int sum;
void add(int a, int b){ e[idx] = b; ne[idx] = h[a]; h[a] = idx++; }
void topsort(){ for(int i =1; i<=n; i++){ if(d[i]==0){ q.push(i); } } while(!q.empty()){ int u = q.front(); v.push_back(u); sum++; q.pop(); for(int j = h[u]; j!=-1; j=ne[j]){ int c = e[j]; d[c]--; if(d[c]==0){ q.push(c); } } } if(sum == n){ for(auto i : v){ cout<<i<<" "; } } else{ cout<<-1; } }
int main(){ memset(h, -1, sizeof(h)); cin>>n>>m; int a,b; for(int i =0 ;i<m ;i++){ cin>>a>>b; add(a,b); d[b]++; } topsort(); }
|