对于一个有向图,可以通过拓扑排序(Topological Sort)来判断是否是有向无环图(Directed Acyclic Graph,DAG)。
我总结了一下拓扑排序的思想,下面来说一说。

拓扑排序的算法思想是:

  1. 每次从图中取出入度为 0 的节点
  2. 删除该节点发出的所有边,进行(1)步骤
    邻接表的实现方式如下:
    toposort
    初始的时候建立两个表,一个邻接表,以及另外一个表存储出度为0的节点,每次将入度表中入度为 0 的点加入容器中,然后从容器中取出节点,去邻接表中查询,根据邻接表修改入度表,发现入度为 0 的点加入容器中,如此反复,直至容器为空。
    如果最终入度表中有入度不为 0 的节点,则该图有环,否则该图无环。若该图为偏序关系,则某一时刻容器中的元素多于一个,取出的元素可能是随机的,造成拓扑排序的结果不唯一,与容器的选取有关。若该图为全序关系,则容器中的元素始终只有一个,结果唯一,与容器的选取无关。
    下面以题为例说明:
    HDU 3342
    题意:有一个 ACM 日常 QQ 交流群,群内存在一些师徒关系,若存在某个人的徒弟是自己的师傅的情况则不合法,输出 NO,否则输出 YES。此题有 trick,即要判断重边,代码如下
    #include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <set>
    using namespace std;
    int main()
    {
    int n, m, x, y, cnt, table[105];
    bool vis[105][105]; //防止出现重边
    while(scanf("%d%d", &n, &m) && n && m)
    {
    cnt = 0;
    memset(vis, 0, sizeof(vis));
    memset(table, 0, sizeof(table));
    vector<int> v[105]; //邻接表
    set<int> st; //存储入度为0的节点
    set<int>::iterator it;
    for(int i = 0; i < m; i++)
    {
    scanf("%d%d", &x, &y);
    if(!vis[x][y])
    {
    v[x].push_back(y);
    table[y]++;
    vis[x][y] = true;
    }
    }
    for(int i = 0; i < n; i++)
    if(table[i] == 0)
    cnt++, st.insert(i);
    while(!st.empty())
    {
    it = st.begin();
    for(unsigned int i = 0; i < v[*it].size(); i++)
    {
    table[v[*it][i]]--;
    if(table[v[*it][i]] == 0)
    cnt++, st.insert(v[*it][i]);
    }
    st.erase(*it);
    }
    printf(cnt == n ? "YES\n" : "NO\n");
    }
    return 0;
    }
文档信息

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
本文链接:www.snovey.com/2016/06/toposort.html