526互联

拓扑排序

发布时间 2023-11-21 19:08:47作者: clinx000

一、拓扑排序介绍

拓扑排序是对有向无环图(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;
}