计算有向图中的循环数

Question

问题：

编写一个程序，为我们提供有向图中的循环数。

方法一：

我知道我们可以使用深度优先搜索检测图中的循环，return 根据简单的布尔值得到答案。我在下面为此编写了代码。但是，我试图在这段代码中实现一个计数器，每次检测到一个周期时它都会递增。但是无论我在哪里实施计数器，我似乎都没有得到正确的答案！（我在评论里写了增量语句）

我也担心 DFS 不是为这个问题选择的正确方法，因为循环之间可能存在一些共同点。

循环检测算法取自：https://www.geeksforgeeks.org/detect-cycle-in-a-graph/

下面给出的代码产生一个输出：

图表：

（这里说的是0个周期，因为注释的计数是递增的）

代码：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Graph 
{   
    static int count = 0; //counter initialised
    private final int V;
    private final List<List<Integer>> adj;

    public Graph(int V)
    {
        this.V = V;
        adj = new ArrayList<>(V);
        
        for (int i = 0; i < V; i++)
            adj.add(new LinkedList<>());
    }
    
    private boolean isCyclicUtil(int i, boolean[] visited,boolean[] recStack)
    {
        if (recStack[i])
            return true; //count++;

        if (visited[i])
            return false;
            
        visited[i] = true;

        recStack[i] = true;
        List<Integer> children = adj.get(i);
        
        for (Integer c: children)
            if (isCyclicUtil(c, visited, recStack))
                return true; 
                
        recStack[i] = false;

        return false;
    }

    private void addEdge(int source, int dest) {
        adj.get(source).add(dest);
    }
    
    private boolean isCyclic()
    {
        boolean[] visited = new boolean[V];
        boolean[] recStack = new boolean[V];
        for (int i = 0; i < V; i++)
            if (isCyclicUtil(i, visited, recStack))
                return true; //count++;
        return false;
    }
    
    public static void main(String[] args)
    {
        Graph graph = new Graph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);
        
        if(graph.isCyclic())
            System.out.println("Graph contains cycles");
        else
            System.out.println("Graph doesn't contains "+count+" cycles");
    }
}

我也想知道用图形着色法能不能找到答案，这就是我能挖掘出来的代码来自：https://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

方法 2：

算法：

创建一个递归函数，它接受边缘和颜色数组（这也可以作为全局变量保存）
将当前节点标记为灰色。
遍历所有相邻节点，如果有节点标记为GRAY则
return 正确，因为循环必然存在。
如果任何相邻顶点为白色，则调用递归函数那个节点。
如果函数 return 为真。 Return 正确。
如果没有相邻节点是灰色的或者没有 returned true 然后标记当前节点为 BLACK 且 return false.

代码：

import java.io.*;
import java.util.*;

class GFG
{

    // A DFS based approach to find if there is a cycle
    // in a directed graph. This approach strictly follows
    // the algorithm given in CLRS book.
    static int WHITE = 0, GRAY = 1, BLACK = 2;

    // Graph class represents a directed graph using
    // adjacency list representation
    static class Graph
    {
            int V;
            LinkedList<Integer>[] adjList;
            
            // Constructor
            Graph(int ver)
            {
                V = ver;
                adjList = new LinkedList[V];
                for (int i = 0; i < V; i++)
                    adjList[i] = new LinkedList<>();
            }
    }

    // Utility function to add an edge
    static void addEdge(Graph g, int u, int v)
    {
            g.adjList[u].add(v); // Add v to u's list.
    }

    // Recursive function to find if there is back edge
    // in DFS subtree tree rooted with 'u'
    static boolean DFSUtil(Graph g, int u, int[] color)
    {
            // GRAY : This vertex is being processed (DFS
            // for this vertex has started, but not
            // ended (or this vertex is in function
            // call stack)
            color[u] = GRAY;
            
            // Iterate through all adjacent vertices
            for (Integer in : g.adjList[u])
            {
                // If there is
                if (color[in] == GRAY)
                    return true;

                // If v is not processed and there is a back
                // edge in subtree rooted with v
                if (color[in] == WHITE && DFSUtil(g, in, color) == true)
                    return true;
            }

            // Mark this vertex as processed
            color[u] = BLACK;
            return false;
    }

    // Returns true if there is a cycle in graph
    static boolean isCyclic(Graph g)
    {
            // Initialize color of all vertices as WHITE
            int[] color = new int[g.V];
            for (int i = 0; i < g.V; i++)
            {
                color[i] = WHITE;
            }

            // Do a DFS traversal beginning with all
            // vertices
            for (int i = 0; i < g.V; i++)
            {
                if (color[i] == WHITE)
                {
                    if(DFSUtil(g, i, color) == true)
                        return true;
                }
            }
            return false;

    }

    // Driver code to test above
    public static void main(String args[])
    {
            // Create a graph given in the above diagram
            Graph g = new Graph(4);
            addEdge(g, 0, 1);
            addEdge(g, 0, 2);
            addEdge(g, 1, 2);
            addEdge(g, 2, 0);
            addEdge(g, 2, 3);
            addEdge(g, 3, 3);
            if (isCyclic(g))
                System.out.println("Graph contains cycle");
            else
                System.out.println("Graph doesn't contain cycle");
    }
}

Answer 1

我认为问题在于单个节点可以属于多个圈子，而您在第一个圈子之后设置为“已访问”。我会使用 DFS，然后使用回溯算法来查找圆圈数。

Answer 2

我花了一段时间，但我终于找到了使用 DFS 和图形着色方法解决这个问题的方法。我仍在研究如何简化它，但这段代码有效！

//Program to count the number of cycles in a Directed Graph.

import java.util.*;
class dir
{

    public static int WHITE = 0, GRAY = 1, BLACK = 2;
    public static int count=0;
    // Graph class represents a directed graph using
    // adjacency list representation
    public static class Graph
    {
            int V;
            LinkedList<Integer>[] adjList;
            @SuppressWarnings("unchecked")
            Graph(int ver)
            {
                V = ver;
                adjList = new LinkedList[V];
                for (int i = 0; i < V; i++)
                    adjList[i] = new LinkedList<>();
            }
    }
    
    //function to add an edge
    public static void addEdge(Graph g, int u, int v)
    {
            g.adjList[u].add(v); 
    }

    // Recursive function to find if there is back edge
    // in DFS subtree tree rooted with 'u'
    public static boolean DFSUtil(Graph g, int u, int[] color)
    {
            color[u] = GRAY;
            // Iterate through all adjacent vertices
            for (Integer in : g.adjList[u])
            {
                // If there is
                if (color[in] == GRAY)
                    return true;
                //If v is not processed and there is a back
                // edge in subtree rooted with v
                if (color[in] == WHITE && DFSUtil(g, in, color) == true)
                    return true;
            }
            // Mark this vertex as processed
            color[u] = BLACK;
            return false;
    }

    // Returns number of cycles.
    public static int isCyclic(Graph g)
    {
            // Initialize color of all vertices as WHITE
            int[] color = new int[g.V];
            for (int i = 0; i < g.V; i++)
            {
                color[i] = WHITE;
            }
            
            // Do a traversal beginning with all vertices
            for (int i = 0; i < g.V; i++)
            {
                if (color[i] == WHITE)
                {
                    if(DFSUtil(g, i, color) == true)
                        count++; 
                }
            }
            return count;

    }

    //Driver Code
    public static void main(String args[])
    {
            //Modify edges accordingly
            Graph g = new Graph(7);
            addEdge(g, 0, 1);
            addEdge(g, 4, 0);
            addEdge(g, 4, 1);
            addEdge(g, 4, 3);
            addEdge(g, 3, 4);
            addEdge(g, 1, 3);
            addEdge(g, 2, 1);
            addEdge(g, 3, 2);
            if (isCyclic(g)>0)
            {
                System.out.println("Cycle detected");
                System.out.println("Graph contains "+count+" cycles");
            }
            else
                {
                System.out.println("Graph doesn't contain cycle");
                }
    }
}

计算有向图中的循环数

Count number of cycles in a Directed graph

java

graph

cycle-detection

问题：

方法一：

代码：

方法 2：

代码：