拓扑排序

2019-08-08

概述

对一个 有向无环图（Directed Acyclic Graph, DAG） G 进行拓扑排序，是将 G 中的所有顶点排成一个线性序列，使得图中任意一对顶点 u 和 v，若边 <u,v> $\in E(G)$，则 u 在线性序列中出现在 v 之前。通常，这样的线性序列称为满足 拓扑次序（Topological Order） 的序列，简称 拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为 拓扑排序。

**在有环的情况下会出现有一些点没有访问到的情况 => ** 可以通过拓扑排序算法判断一个有向图有没有环

拓扑排序每个点一定只会被访问1遍: 每个点的入度只有在一个时刻变为0, 要么一开始就时0, 要么在某个时刻减小为 0, 不可能多次变成 0

算法流程

拓扑排序算法主要由以下两步循环执行，直到不存在入度为 0 的顶点为止。

选择一个入度为 0 的顶点并将它输出；
删除图中从顶点连出的所有边。

循环结束，若输出的顶点数小于图中的顶点数，则表示该图中存在回路，也就是无法进行拓扑排序；否则输出的顶点序列就是一个拓扑序列。

基于邻接表的 C++ 示例代码如下：

// 使用邻接表存储，若对此数据结构不熟悉，请学习邻接表相关的课程内容
struct edge {
    int v, next;
} e[MAX_M];
int p[MAX_N], eid;
...
int topo() {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
          if (indegree[i] == 0) {  // 将所有入度为零的顶点入队
            q.push(i);
        }
    }
    while (!q.empty()) {
        int now = q.front();
        cout << "visiting " << now << endl;
        q.pop();
        for (int i = p[now]; i != -1; i = e[i].next) {
            int v = e[i].v;
            indegree[v]--;
            if (indegree[v] == 0) {  // 将入度新变成零的顶点入队
                q.push(v);
            }
        }
    }
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int N = 100;
const int M = 10000;

struct edge {
    int v, next;
    edge() {}
    edge(int _v, int _next): v(_v), next(_next) {}
} E[M];

int p[N];
int eid;

void init() {
    memset(p, -1, sizeof p);
    eid = 0;
}

void insert(int u, int v) {
    E[eid] = edge(v, p[u]);
    p[u] = eid++;
}

int n, m;
int indegree[N];
queue<int> q;

void topo() {
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int now = q.front();
        q.pop();
        cout << now;
        for (int e = p[now]; e != -1; e = E[e].next) {
            int v = E[e].v;
            indegree[v]--;
            if (indegree[v] == 0) {
                q.push(v);
            }
        }
    }
}


int main() {
    init();
    memset(indegree, 0, sizeof indegree);
    cin >> n >> m;
    int u, v;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        insert(u, v);
        indegree[v]++;
    }
    topo();
    return 0;
}