C/C++浅析邻接表拓扑排序算法的实现

什么是拓扑排序

在图论中，若存在一种拓扑序列，使得对于任意的有向边(u,v)，u在序列中都在v的前面，则称该图为拓扑排序，该序列称为拓扑序列。拓扑排序是一个有向无环图（DAG, Directed Acyclic Graph）的一种线性序列。

拓扑排序算法的实现

拓扑排序算法的实现一般基于邻接表，其核心思路为：先将所有入度为0的点入队，扫描队列中的点，把该点所指向的点的入度减1，若减为0，则将该点入队。最后，若可入队的点数小于图中点数，则该图不存在拓扑序列。

关键代码实现

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 10005;

struct Edge {
    int to, next;
} edges[MAXN];
int head[MAXN], degree[MAXN];
int cnt;

void addEdge(int u, int v) {
    edges[cnt].to = v;
    edges[cnt].next = head[u];
    head[u] = cnt++;
    degree[v]++;
}

bool topsort(int n) {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (!degree[i]) q.push(i);
    }

    int cnt = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cnt++;
        for (int i = head[u]; ~i; i = edges[i].next) {
            int v = edges[i].to;
            degree[v]--;
            if (!degree[v]) {
                q.push(v);
            }
        }
    }

    return cnt == n;
}

int main()
{
    int n, m;
    cin >> n >> m;
    memset(head, -1, sizeof(head));
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
    }

    if (!topsort(n)) {
        cout << "No topsort!" << endl;
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

示例说明

示例1

输入：

7 9
7 6
7 5
6 4
6 3
5 4
5 2
4 1
3 1
2 1

输出：

7 6 5 4 3 2 1 

示例2

输入：

6 6
1 2
1 3
2 4
2 5
3 6
4 6

输出：

No topsort!

性能分析

时间复杂度：O(V+E)。其中，V为图中点数，E为图中边数。因为算法需要遍历每一个点和边。

空间复杂度：O(V+E)。其中，V为点数，E为边数。因为需要存储每个点的边列表以及每个点的入度。