2016 August 20

拓扑排序

拓扑排序是对一个有向图的所有顶点进行排序，使得每一条有向边(u,v)对应的u都排在v的前面。

基于BFS实现的算法流程：

  1. 读图，记录每个顶点的入度和邻接点；
  2. 扫描所有顶点，将入度为0的顶点加入队列；
  3. 依次从队列中取出已排好序的顶点输出并计数，对于每个出队顶点，将它所有邻接点的入度减1，如果减1后邻接点的入度变为0，则将它加入队列；
  4. 重复步骤3直到队空为止；
  5. 检查已输排好序顶点的数量是否等于总顶点数，是则排序正常完成，否则该有向图存在环。

以下是上述算法的C++实现。

int n, m, d[100005], u, v;
vector<int> g[100005], ans;
queue<int> q;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        d[v] += 1;
        g[u].push_back(v);
    }
    for (int i = 1; i <= n; i++)
        if (d[i] == 0) q.push(i);
    while (!q.empty()) {
        u = q.front(); q.pop();
        ans.push_back(u);
        for (auto i : g[u])
            if (--d[i] == 0) q.push(i);
    }
    if (ans.size() < n) puts("Cycle");
    else for (auto i : ans)
        printf("%d\n", i);
    return 0;
}

另一种做法基于DFS，思路大致是对各点做后序遍历，得到结果的逆序即为拓扑排序结果。如果遍历时后续点又依赖前边的点，则存在环，可以通过vis数组来表示，取0表示未访问，取-1表示在访问中，取1则为已访问完。

为了避免逆序输出，可以考虑反向建图，这样似乎更符合DFS的思想。

int n, m, vis[100005], u, v, cycle;
vector<int> g[100005], ans;
bool dfs(int x) {
    vis[x] = -1;
    for (size_t i = 0; i < g[x].size(); i++) {
    for (auto i : g[x]) {
        if (vis[i] == -1) return true;
        if (vis[i] == 0 && dfs(g[i]))
            return true;
    }
    ans.push_back(x);
    vis[x] = 1;
    return false;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i]) cycle |= dfs(i);
    if (cycle) puts("Cycle");
    else for (auto i : ans)
        printf("%d\n", i);
    return 0;
}

如果要取字典序最小的满足要求的排列，可以在基于BFS的实现可以将队列换成优先队列。

Table of Contents