思想

拓扑排序: 就是按照逻辑上先后发生的顺序进行排序。

所以只有 有向图 才有拓扑序。

根据定义,如果图中有环则不能拓扑排序。

常用的方法有两种,一种是dfs,一种是根据度来bfs(可以字典序)。

这里主要介绍第二种方法。

  1. 把每一个事件都看作一个点。如果a事件在b事件后面发生,则连一条a到b的有向边。
  2. 如果一个点的入度为0,那么说明没有事件早于它发生,则将它入队。所以我们要先将所有入度为0的点入队。
  3. 每次取队头元素记为u, 将所有与u相连的点的入度减一,如果入度为0了,则入队。
  4. 如果原图中存在环,则最后topo数组内元素的数量一定小于n。

优点:

这种方法是以点为重心,dfs是以边为重心。那么如果有删边的操作,最好就用第二种方法 : 直接入度减一即可。

可以保证拓扑序是按照字典序的。

如果想要输出是字典序的话,需要将队列改为优先队列。( 如果用邻接矩阵实现,需要去重边

注意 : 判环的时候,如果是邻接矩阵实现,则要判重边!

模板

vector<int> G[maxn],topo;   //存图; 记录拓扑序。
int deg[maxn];

void addedge(int u,int v){
    G[u].push_back(v);
}

bool Topo(int n){
    queue<int> Q;
    topo.clear();
    for(int i=1;i<=n;i++) if(deg[i] == 0) Q.push(i);
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        topo.push_back(u);
        for(int i=0;i<G[u].size();i++){
            int v = G[u][i];
            if(deg[v] > 0){
                deg[v]--;
                if(deg[v] == 0) Q.push(v);
            }
        }
    }
    if(topo.size() != n) return false;     //存在环
    return true;
}
最后修改:2020 年 07 月 30 日 10 : 18 PM