拓扑排序原理及代码实现经典例题（邻接矩阵加邻接表实现）

柔光的暖阳◎ 2023-02-11 03:08 18阅读 0赞

#### 一、拓扑排序 ####

**定义：** 拓扑排序是将一个**有向无环图**的所有顶点排成一个线性队列，并且保证队中的所有点不会指向其前面的点，即所有边只能是某个点指向其队列后面的点。  
**排序原理：** 首先存下所有点的入度（有几条边的终点是该点），若某点入度为0，将该点加入拓扑序，然后删除该点为起点的所有边（就是将所有该点为起点的边的终点的入度减一），然后重复此操作，直到所有顶点进入拓扑序即可。若有点未进入拓扑序，说明该图存在环。

#### 二、代码实现 ####

1、邻接矩阵的拓扑排序

#include<iostream>
    #include<vector>
    #include<queue>
    
    using namespace std;
    const int N = 110;
    
    int n,m;	//顶点数和边数
    int e[N][N],d[N];	//e为邻接矩阵数组，d为顶点入度数组
    vector<int> ans;	//ans为拓扑序数组即为最终答案
    queue<int> q;	//队列q存入度为0的点
    
    void topsort()
    { 
    	for(int i = 1;i <= n;i++)	//找出初始所有入度为0的点
    		if(d[i] == 0)
    			q.push(i);	//入队q
    	
    	while(!q.empty())
    	{ 
    		int t = q.front();	//记录队首顶点，处理以他为起点的边
    		q.pop();
    		ans.push_back(t);	//q的队首进入拓扑序
    
    		for(int j = 1;j <= n;j++)	//遍历其他所有点
    		{ 
    			if(e[t][j] == 1)	//若存在以他为起点的边
    			{ 
    				d[j]--;		//删除此边，其终点的入度-1
    				if(d[j] == 0)	//如果终点的入度为0，入队
    					q.push(j);
    			}
    		}
    	}
    }
    
    int main()
    { 
    	int a,b;
    	cin >> n >> m;
    	for(int i = 0;i < m;i++)
    	{ 
    		cin >> a >> b;	//输入边
    		e[a][b] = 1;	//存图
    		d[b]++;		//终点的入度+1
    	}
    
    	topsort();	//拓扑排序
    
    	for(int i = 0;i < ans.size();i++)
    		cout << ans[i] << endl;
    
    	return 0;
    }

2、邻接表的拓扑排序

#include<iostream>
    #include<queue>
    #include<vector>
    #include<cstring>
    
    using namespace std;
    const int N = 110;
    
    int n,m;	//顶点数和边数
    int h[N],e[N],ne[N],idx;	//用数组模拟邻接表
    int d[N];	//入度数组
    vector<int> ans;	//拓扑序数组，即为答案
    
    void add(int a,int b)	//加边函数，存一条a到b的边
    { 
    	e[idx] = b;
    	ne[idx] = h[a];
    	h[a] = idx++;
    }
    
    void topsort()
    { 
    	queue<int> q;
    	for(int i = 1;i <= n;i++)	//找到初始时所有入度为0的点
    		if(d[i] == 0)
    			q.push(i);	//入队q
    
    	while(!q.empty())
    	{ 
    		int t = q.front();	//记录队首元素
    		q.pop();
    		ans.push_back(t);	//入拓扑序
    
    		for(int i = h[t]; ~i;i = ne[i])	//找到所有以该点为起点的边
    		{ 
    			int k = e[i];	//寻找以该点为起点的下一个点
    			d[k]--;		//删去此边，即此点入度-1
    			if(d[k] == 0)	//若入度为0，入队
    				q.push(k);
    		}
    	}
    }
    
    int main()
    { 
    	int a,b;
    	cin >> n >> m;
    	memset(h,-1,sizeof h);
    	for(int i = 0;i < m;i++)
    	{ 
    		cin >> a >> b;	//输入边
    		d[b]++;		//终点的入度+1
    		add(a,b);	//存边
    	}
    
    	topsort();	//拓扑排序
    	
    	for(int i = 0;i < ans.size();i++)
    		cout << ans[i] << endl;
    
    	return 0;
    }

#### 三、经典例题 ####

1、可达性统计  
给定一张N个点M条边的有向无环图，分别统计从每个点出发能够到达的点的数量。（1≤N,M≤30000）

计算a点可到达点的数量只需计算a点所能到达的所有点的可达点之和再加上自己（1）。所以先将所有点拓扑排序，然后从后往前计算每个点能到达的点的可达点数量之和，再+1即可。  
由于点的数量太大达到30000，直接计算肯定会超时，所以这里用状态压缩将所有点压缩成二进制，每一位的0或1代表能否到达该点，这里直接使用stl的bitset比较方便，对bitset不熟悉的可以[看这][Link 1]

#include<iostream>
    #include<queue>
    #include<vector>
    #include<cstring>
    #include<bitset>
    
    using namespace std;
    const int N = 30010;
    
    int n,m;	//n点m边
    int h[N],e[N],ne[N],idx;	//邻接表存图
    int d[N];	//入度数组
    vector<int> ans;	//拓扑序数组
    bitset<N> f[N];		//二进制数组，f的每一个元素均为一个n位的二进制数
    
    void add(int a,int b)	//加边函数
    { 
    	e[idx] = b;
    	ne[idx] = h[a];
    	h[a] = idx++;
    }
    
    void topsort()		//拓扑排序
    { 
    	queue<int> q;
    	for(int i = 1;i <= n;i++)
    		if(d[i] == 0)
    			q.push(i);
    
    	while(!q.empty())
    	{ 
    		int t = q.front()
    		ans.push_back(t);
    		q.pop();
    
    		for(int i = h[t]; ~i;i = ne[i])
    		{ 
    			int j = e[i];
    			d[j]--;
    			if(d[j] == 0)
    				q.push(j);
    		}
    	}
    }
    
    void calc()	//计算可达点
    { 
    	for(int i = ans.size()-1;i >= 0;i--)	//从后往前计算
    	{ 
    		int k = ans[i];
    		f[k][k] = 1;	//表示f[k]的第k位为1，k到k先记为1
    		for(int j = h[k];~j;j = ne[j])	//列举所有k能到达的点
    		{ 
    			f[k] |= f[e[j]];	//k点的可达点数量就是k点所有可达点的可达点数量和，将k点和其所有可达点按位或，即该点的某位为1则都为1
    		}
    	}
    }
    
    int main()
    { 
    	int a,b;
    	cin >> n >> m;
    	for(int i = 0;i < m;i++)
    	{ 
    		cin >> a >> b;
    		d[b]++;
    		add(a,b);
    	}
    
    	topsort();
    	calc();
    
    	for(int i = 1;i <= n;i++)
    		cout << f[i].count() << endl;	//f[i].count()表示f[i]的按位1的个数
    
    	return 0;
    }

--------------------

2、优先关系  
B：Chess Tournament  
[具体题解见此处][Link 2]

--------------------

[Link 1]: https://blog.csdn.net/qq_45735851/article/details/106273675
[Link 2]: https://blog.csdn.net/qq_45735851/article/details/108093958