一个图是否存在环

问题描述：给一个图G=<V,E>，问如何判断这个图中是否存在回路？请给出至少3种方法

分析：

方法1：利用减枝的方法，

      如果G为有向图：

       1）首先删除入读为0的点，并且将对应的和该点相连的点的入读-1。（可以用一个数组表示节点被删除的状态）

       2）重复过程1），直到没有入读为0的点，如果还有没被删除的节点，则该有向图一定存在回路

      如果G为无向图：

       1）首先删除所有度数<=1的点，然后将与这些点相连的所有点的度数-1，然后将所有度数为1的点加入队列中

       2）对队列中的每个点，重复过程1），如果还有没被删除的节点，那么证明该图一定存在回路。

方法2：（有向图）利用拓扑排序

      1）首先利用DFS[深度优先搜索算法]进行拓扑排序，最后生成一个拓扑序链表，然后为每个节点设置一个是否被访问过标记，用Visit数组

      2) 遍历这个链表，对每个节点v，设置visit[v]=1,如果判断如果存在与该节点相邻的节点u，使得Visit[u]=1，那么证明存在回边，这图中一定存在圈。

public class DirectedDepthFirstTopoWithCircleDetection  
{  
    private boolean[] visited;  
    // 用于记录dfs方法的调用栈，用于环路检测  
    private boolean[] onStack;  
    // 用于当环路存在时构造之  
    private int[] edgeTo;  
    private Stack<Integer> reversePost;  
    private Stack<Integer> cycle;  
  
    /** 
     * Topological Sorting Constructor 
     */  
    public DirectedDepthFirstTopoWithCircleDetection(Digraph di)  
    {  
        this.visited = new boolean[di.getV()];  
        this.onStack = new boolean[di.getV()];  
        this.edgeTo = new int[di.getV()];  
        this.reversePost = new Stack<Integer>();  
  
        for (int i = 0; i < di.getV(); i++)  
        {  
            if (!visited[i])  
            {  
                dfs(di, i);  
            }  
        }  
    }  
  
    private void dfs(Digraph di, int v)  
    {  
        visited[v] = true;  
        // 在调用dfs方法时，将当前顶点记录到调用栈中  
        onStack[v] = true;  
  
        for (int w : di.adj(v))  
        {  
            if(hasCycle())  
            {  
                return;  
            }  
            if (!visited[w])  
            {  
                edgeTo[w] = v;  
                dfs(di, w);  
            }  
            else if(onStack[w])  
            {  
                // 当w已经被访问，同时w也存在于调用栈中时，即存在环路  
                cycle = new Stack<Integer>();  
                cycle.push(w);  
                for(int start = v; start != w; start = edgeTo[start])  
                {  
                    cycle.push(v);  
                }  
                cycle.push(w);  
            }  
        }  
  
        // 在即将退出dfs方法时，将顶点添加到拓扑排序结果集中，同时从调用栈中退出  
        reversePost.push(v);  
        onStack[v] = false;  
    }  
  
    private boolean hasCycle()   
    {  
        return (null != cycle);  
    }  
      
    public Iterable<Integer> getReversePost()  
    {  
        if(!hasCycle())  
        {  
            return reversePost;  
        }  
        else   
        {  
            throw new IllegalArgumentException("Has Cycle: " + getCycle());  
        }  
    }  
      
    public Iterable<Integer> getCycle()   
    {  
        return cycle;  
    }  
}

 

 

方法3：（无向图而言）利用BFS[广度优先搜索]（利用算法导论上BFS的版本，每个节点有一个color属性，标记节点的颜色：“白”、“灰”、“黑”）

      1）直接利用BFS进行遍历，在判断当前节点的相邻的节点时，附加一个判断：如果这个节点的颜色为“灰色”，则return false，即存在环。

      2）遍历完所有的节点，返回true。

广度优先搜索算法示例，找V0到V6的最短路径：

 

 

方法4：（无向图而言）还是利用BFS，在遍历过程中，为每个节点标记一个深度deep[]，如果存在某个节点为v，除了其父节点u外，还存在与v相邻的节点w使得deep[v]<=deep[w]的，那么该图一定存在回路。

 

方法5：（无向图而言）用BFS或DFS遍历，最后判断对于每一个连通分量当中，如果边数m>=节点个数n，那么改图一定存在回路。因此在DFS或BFS中，我们可以统计每一个连通分量的顶点数目n和边数m，如果m>=n则return false；直到访问完所有的节点，return true.