一、拓扑排序介绍
拓扑排序是对有向无环图(DAG)中的节点进行排序的一种算法。它的核心就是思想是通过寻找入度(指向该节点的边的数量)为0的节点,从而遵循有向图的前后依赖关系,构建一个有序的节点序列。
二、拓扑排序的操作
1.根据实际的问题构建一个有向无环图
2.统计每个节点的入度,将依赖关系表示为有向边。
3.我们初始化一个队列q,然后将入度为0的节点加入队列,再初始化一个储存结果的数组ans。
4.当队列不为空的时候我们进行循环遍历
- 先取出一个节点,将其放入ans中。
- 遍历这个节点的所有邻居节点,并将其邻居节点的入度减1。
- 如果邻居节点的入度变为了0,那么久将其加入队列中。
5.我们比较ans中的节点数,如果和图中的节点数相同则表示排序完成,小于则代表图中是有环存在的。
三、具体实现
1.构建一个图以及一些初始化
int sumNode = 7;//假设我们有七个节点 vector<vector<int>> Graph(sumNode);//二维数组用于构建图 vector<int> Degree(sumNode, 0);//用于记录每个节点的入度 vector<int> ans;//记录排好序的答案 queue<int> q;//初始化的一个队列用于遍历、 //建图,这里我们手动输入 Graph[0].push_back(1); Graph[0].push_back(2); Graph[1].push_back(3); Graph[2].push_back(3); Graph[2].push_back(4); Graph[3].push_back(5); Graph[4].push_back(5); Graph[5].push_back(6); Graph[6].push_back(7);
2.我们统计每个节点的入度
for (int i = 0; i < sumNode; i++){ for(int neighbour : Graph[i]){ Degree[neighbour]++; } }
3.我们将入度为0的节点入队列,并且开始循环
//将入度为0的节点入队列 for (int i = 0; i < sumNode; i++){ if(Degree[i] == 0){ q.push(i); } } //当队列不为空的时候进行遍历 while(!q.empty()){ //定义一个变量t等于队列的头结点 int t = q.front(); //出队列 q.pop(); //加入到ans中 ans.push_back(t); //对这个节点t开始遍历它的相邻节点,再将入度为0的节点入队列 for(int neighbour : Graph[t]){ //将邻居节点的入度减一 Degree[neighbour]--; if(Degree[neighbour] == 0){ q.push(neighbour); } } } if (ans.size() < sumNode){ cout << "该图存在一个环"; return 0; } else{ cout << "拓扑排序后的结果为:"; for (int node : ans) cout << node << " "; }
4.最后我们汇总一下
#include <iostream> #include <vector> #include <queue> using namespace std; int main(){ int sumNode = 7;//假设我们有七个节点 vector<vector<int>> Graph(sumNode);//二维数组用于构建图 vector<int> Degree(sumNode, 0);//用于记录每个节点的入度 vector<int> ans;//记录排好序的答案 queue<int> q;//初始化的一个队列用于遍历、 //建图,这里我们手动输入 Graph[0].push_back(1); Graph[0].push_back(2); Graph[1].push_back(3); Graph[2].push_back(3); Graph[2].push_back(4); Graph[3].push_back(5); Graph[4].push_back(5); Graph[5].push_back(6); Graph[6].push_back(7); for (int i = 0; i < sumNode; i++){ for(int neighbour : Graph[i]){ Degree[neighbour]++; } } //将入度为0的节点入队列 for (int i = 0; i < sumNode; i++){ if(Degree[i] == 0){ q.push(i); } } //当队列不为空的时候进行遍历 while(!q.empty()){ //定义一个变量t等于队列的头结点 int t = q.front(); //出队列 q.pop(); //加入到ans中 ans.push_back(t); //对这个节点t开始遍历它的相邻节点,再将入度为0的节点入队列 for(int neighbour : Graph[t]){ //将邻居节点的入度减一 Degree[neighbour]--; if(Degree[neighbour] == 0){ q.push(neighbour); } } } if (ans.size() < sumNode){ cout << "该图存在一个环"; return 0; } else{ cout << "拓扑排序后的结果为:"; for (int node : ans) cout << node << " "; } return 0; }