MENU

拓扑排序

May 26, 2019 • 算法

一:前言

在有向无环图(DAG,即 Directed Acyclic Graph)中,拓扑排序(Topological Sorting)是其顶点的线性排序,使得对于从顶点 $u$ 到顶点 $v$ 的每个有向边,在排序中 $u$ 都在 $v$ 之前。

有向无环图(DAG)才有拓扑排序,非 DAG 图是没有拓扑排序这个概念的。

例如,下面这个图,是一个 DAG,

二:算法实现

拓扑排序的实现非常之简单,下面介绍一个常用的实现算法 - 卡恩算法(Kahn's algorithm),

  1. 从 DAG 中选择一个没有前驱(即入度为 0)的顶点并输出;
  2. 从图中删除该顶点和所有以它为起点的有向边;
  3. 重复 1 和 2 直到当前的 DAG 为空或当前图中不存在无前驱的顶点为止。后一种情况说明该图中必然存在环,可以以此判断该图是否能生成拓扑排序序列。

代码如下:

#include <iostream>
#include <queue>

using namespace std;

int n;                /* 顶点数(<=100) */
int m;                /* 边数 */
int matrix[105][105]; /* 邻接矩阵 */
int inDegree[105];    /* 入度 */

void TopologicalSort()
{
    int num = 0; /* 已被拓扑排序的顶点的个数 */
    queue<int> q;

    /* 找到所有入度为 0 的顶点,并入队列 */
    for (int i = 1; i <= n; ++i)
    {
        if (inDegree[i] == 0)
        {
            num++;
            inDegree[i]--;
            q.push(i);
            cout << i << " ";
        }
    }

    while (!q.empty())
    {
        int u = q.front();
        q.pop();

        for (int v = 1; v <= n; ++v)
        {
            if (matrix[u][v])
            {
                inDegree[v]--;
                if (inDegree[v] == 0)
                {
                    num++;
                    q.push(v);
                    cout << v << " ";
                }
            }
        }
    }

    /* 说明有环 */
    if (num != n)
        cout << "有环,无法生成拓扑序列";

    cout << endl << endl;
}

int main()
{
    while (1)
    {
        memset(matrix, 0, sizeof(matrix));
        memset(inDegree, 0, sizeof(inDegree));

        cout << "请输入顶点数(<=100):";
        cin >> n;
        cout << "请输入边数:";
        cin >> m;

        cout << "请输入 " << m << " 条有向边:" << endl;
        int u, v;
        for (int i = 0; i < m; ++i)
        {
            cin >> u >> v;
            matrix[u][v] = 1;
            inDegree[v]++;
        }

        cout << "拓扑序列为:";
        TopologicalSort();
    }
    return 0;
}

输出如下:

请输入顶点数(<=100):5
请输入边数:7
请输入 7 条有向边:
1 2
1 4
2 4
2 3
4 3
3 5
4 5
拓扑序列为:1 2 4 3 5

请输入顶点数(<=100):3
请输入边数:3
请输入 3 条有向边:
1 2
2 3
3 1
拓扑序列为:有环,无法生成拓扑序列

三:参考链接

最后编辑于: May 26, 2019 13:11
Archives QR Code Tip
QR Code for this page
Tipping QR Code