怎么判断图有环？_有环图

因为疫情在家，没事情干，脑子里突然迸发出了一个想法，图是程序员非常熟悉的数据结构，而且也被广泛地应用与生活日常，机器人，航天工程等各种领域。但是如果我们如果只是围着一个图去绕圈，那可能没什么意义。而且会陷入迷宫当中出不来。所以就想写一写，如何判断 图到底有没有环呢？

我们以有向图为例（假设图肯定是连通的）：

                              图1 、有向无环图                                                         图2 、有向有环图

 

一、dfs迷宫式走法：

如果我们通过普通的dfs对图1进行 遍历时候，我们可能得到的结果的 ：A-->B-->E-->C-->F-->D

伪代码：

struct graph{
    int to;
    int weight;
};
vector<graph> g[n];//邻接表的图结构
bool visit[n]={false};
void dfs(int s){
    visit[s]=true; //设置s顶点已经被访问过
    //输出s
    for(int i=0;i<g[s].size();i++){ //访问s的邻接点
        if(!visit[g[s][i].to])
            dfs(g[s][i].to);
    }
 
}

当我们使用如上代码去遍历图2时，经过大脑的运算应该是：A-->B-->E-->C-->F-->D

emmm，虽然路径一样，但是程序猿er肯定都知道他走的路线是不一样的。

这都不重要，至关重要的是：这nm不能看出有没有环啊。。。。

但是我们只要将代码稍微改动一下就可以判断了。

那稍微改动，究竟要改哪儿呢，，，我们先分析一下为什么上面的dfs不能判断是否有环，因为我们维护了一个数组visit，这个数组用来存储点有没有被访问的状态。如果点被访问过，visit[点]=true，所以即便是有环也不会再次访问了。

如上图，我们从A点出发，到达C点后，因为A已经被标记，所以不会再次访问A，也就无法判断图是否有环。

所以通过分析我们发现，我们只要改一下，visit这个数组（也就是存储点状态的这个数组就可以解决问题）。

那么我们要怎么设计呢？

上述的visit有两个状态（访问过和未访问过），如果我们扩展一个状态是不是就好了呢？

如果把visit改成三维的（访问过、未访问过、正在访问中）。

struct graph{
    int to;
    int weight;
};
vector<graph> g[n];//邻接表的图结构
int visit[n]={-1};//-1表示未访问过
bool dfs(int s){
    visit[s]=0; //设置s顶点正在被访问
    //输出s
    for(int i=0;i<g[s].size();i++){ //访问s的邻接点
        if(visit[g[s][i].to]==0){//如果正在访问的点又被访问到则代表有环
            return false;
        }
        else if(visit[g[s][i].to]==-1){
            return dfs(g[s][i].to);
        }   
    }
    visit[s]=1;//s结点访问完毕
 
}

通过这个方法，一开始我也是 半明白半糊涂，但是只要按照这个方法，跑一下上面的图，我们就会发现这个方法的神奇。

如果转过一圈又回到了这个点，那么就说明有环。

 

二、拓扑排序法

我们可以在图的初始化以及插入边的时候，确定每个顶点的入度。

我们可以把入度看作是 一件事情的完成顺序。

下图中A和B的入度都是0，表示A,B没有前提事件，而C的入读是2，也就是必须A和B完成之后才能完成C。

那么我们怎么通过这种方法来判断图中是否有环呢？

还以这幅图为例，我们可以看到，A,B,C三点的入度都是1。没有入度为0的点，所以这三件事情互相为前提，以至于这三件事情都不能完成。这就判断出了环。

如果更复杂一点儿的图呢？

如上图，我们可以这么看，S的入度为0，所以我们可以先把S完成，S完成后删除这个节点，此时剩下的ABC三个节点中入度都是0，又陷入了刚才之前的循环中。所以此图有环。转换为伪代码就是：

int indegree[n]={0};//在图初始化或者插入边时记录入度
int visit[n]={0};
void is_circle(){
    while(存在入读为0的点){
        //找出图中入度为0的点
        //把visit[入度为0的点]设为1，表示已经访问过
        for(;;){
            //遍历这个点的邻接点，把他们的入度 减一
        }
    }
    //如果出循环说明不存在入读为0的点。
    //那么看visit是否都访问过。如果有节点未访问过。说明图中有环。
}

 

 

emmm，这就是我想到的两个方法，判断的方法肯定有很多。以后 慢慢思考哈哈哈