• 欢迎光临~

【笔记】DAG图与拓扑排序

开发技术 开发技术 2022-07-17 次浏览

参考博客:(7条消息) 图论--DAG与拓扑排序_信奥教练Andy的博客-CSDN博客

 

(1)DAG有向无环图

易证,只有有向无环图才存在拓扑排序。

一个图G的拓扑排序大多情况下是不唯一的。

 

(2)卡恩算法(BFS)

  1. 统计图中每个点的入度(即连向该点的边数)
  2. 将入度为0的点放入队列
  3. 每次从队列中取出一个点 u,遍历从这个点出发的所有出边(u− > v) ,删除 u− > v这条边(代码实现上仅表现为让v 的入度-1),若v 的入度变为0,则将v 放入队列
  4. 重复(3)直到队列为空
  5. 若所有点都进出过队列,则点的出队顺序即为这张图的拓扑序,否则说明该图不存在拓扑排序(存在有向环)

 

(3)DFS算法

  理解困难,但实现更简单。

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;

vector <int > son[N]; 
int topo[N];//拓扑排序后的顺序,如1-4点,排序后为2341,则数组中为2 3 4 1 
int c[N]; //0表示未遍历过,-1表示是此次dfs中遇到的点,1表示是以前dfs路径中遇到的点 

int n,t;

bool dfs(int x)
{
    c[x] = -1;
    int sz=son[x].size();
    for(int i=0;i<sz;i++)
    {
        int nx=son[x][i];
        if(c[nx] == -1 )
            return false; //如果遇到这次遍历路上的节点,则肯定有环
        
        if(!c[nx] && !dfs(nx) )
            return false; 
    }
    
    c[x]=1;
    topo[--t]=u; 
} 

bool toposort()
{
    t=n;
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;i++) //点的序号为1-n
    {
        if(!c[i] && !dfs(c) ) //!c[i]则进入,返回值为false则有环 
            return false;    
    } 
    return true;
}

int main()
{
    if(!toposort() )
    {
        printf("不是DAG有向无环图");
        return 0; 
    }
    
    return 0;
}

 

(3)DAG的判定——判断一张有向图是否有环?  

  考虑一张有向无环图,从任意点u出发,对这张图进行遍历时,如果点u被经过了多于一次(尽管没有再次将这个点放入队列),则说明我们找到了一个有向环(从点u出发有一条路径回到点u)。

  不难想到,可以使用BFS来搜索图中的环,复杂度为O(n*m)。

  所以适宜使用O(n)算法——拓扑排序来验证这个问题。

程序员灯塔
转载请注明原文链接:【笔记】DAG图与拓扑排序
喜欢 (0)