java - 计算无向图中的循环数

Question

问题

编写一个 JAVA 程序来计算无向图中的循环数。

我的做法：

我尝试使用深度优先搜索来解决这个问题。

我在网上找到了一个程序，可以计算无向连通图中长度为 n 的循环。

代码来自：https ://www.geeksforgeeks.org/cycles-of-length-n-in-an-undirected-and-connected-graph/

我通过创建函数 count() 对其进行了修改。它使用 for 循环检查图中不同长度的循环数。到目前为止我得到的代码附在下面。

对于下图，

我得到的输出是

但是，答案不应该是3吗？

遵循 3 个独特的周期

0 -> 1 -> 2 -> 3 -> 0

0 -> 1 -> 4 -> 3 -> 0

1 -> 2 -> 3 -> 4 -> 1

public class Main 
{
    public static final int V = 5;
    static int count = 0;
    static void DFS(int graph[][], boolean marked[],int n, int vert, int start) 
    {
        marked[vert] = true;
        if (n == 0) 
        {
            marked[vert] = false;
            if (graph[vert][start] == 1) 
            {
                count++;
                return;
            } 
            else
                return;
        }
        for (int i = 0; i < V; i++)
            if (!marked[i] && graph[vert][i] == 1)
                DFS(graph, marked, n-1, i, start);
        marked[vert] = false;
    }
    static int countCycles(int graph[][], int n) 
    {
        boolean marked[] = new boolean[V];
        for (int i = 0; i < V - (n - 1); i++) 
        {
            DFS(graph, marked, n-1, i, i);
            marked[i] = true;
        }
        
        return count / 2;
    }
    
   
    public static int count(int graph[][]) 
    {
        int count=0;
        for(int i=3;i<6;i++)    //i starts at 3 because the minimum length of a cycle is 3.
            count+=countCycles(graph,i);
        return count;
    }
    
    // driver code
    public static void main(String[] args) 
    {
        int graph[][] = {{0, 1, 0, 1, 0},
                        {1, 0, 1, 0, 1},
                        {0, 1, 0, 1, 0},
                        {1, 0, 1, 0, 1},
                        {0, 1, 0, 1, 0}};
        System.out.println("Total cycles are "+count(graph));
    }
}

Answer 1

我终于找到了使用 DFS 和图形着色方法的解决方案。

//Program to count the number of cycles in an Undirected Graph

import java.util.*;
class Graph
{
    static final int N = 100000;
    @SuppressWarnings("unchecked")
    static Vector<Integer>[] graph = new Vector[N];
    @SuppressWarnings("unchecked")
    static Vector<Integer>[] cycles = new Vector[N];
    static int cyclenumber;
    
    // Function to mark the vertex with
    // different colors for different cycles
    static void dfs_cycle(int u, int p, int[] color,int[] mark, int[] par)
    {
        // already (completely) visited vertex.
        if (color[u] == 2)
        {
            return;
        }
        // seen vertex, but was not completely visited -> cycle detected.
        // backtrack based on parents to find the complete cycle.
        if (color[u] == 1)
        {
            cyclenumber++;
            int cur = p;
            mark[cur] = cyclenumber;
             // backtrack the vertex which are
            // in the current cycle thats found
            while (cur != u)
            {
                cur = par[cur];
                mark[cur] = cyclenumber;
            }
            return;
        }
        par[u] = p;
        // partially visited.
        color[u] = 1;
        // simple dfs on graph
        for (int v : graph[u])
        {
            // if it has not been visited previously
            if (v == par[u])
            {
                continue;
            }
            dfs_cycle(v, u, color, mark, par);
        }
        // completely visited.
        color[u] = 2;
    }
    
    // add the edges to the graph
    static void addEdge(int u, int v)
    {
        graph[u].add(v);
        graph[v].add(u);
    }

    //Driver code
    public static void main(String[] args)
    {

        for (int i = 0; i < N; i++)
        {
            graph[i] = new Vector<>();
            cycles[i] = new Vector<>();
        }
        
        //Modify edges accordingly
        addEdge(1, 2);
        addEdge(2, 4);
        addEdge(4, 3);
        addEdge(1, 3);
        addEdge(3, 5);
        addEdge(4, 5);
        addEdge(4, 6);

        int[] color = new int[N];
        int[] par = new int[N];
        int[] mark = new int[N];

        cyclenumber = 0;

        dfs_cycle(1, 0, color, mark, par);

        if(cyclenumber>0)
        {
            System.out.println("CYCLE DETECTED!");
            System.out.println("Number of cycles: "+cyclenumber);
        }
        else
        {
            System.out.println("CYCLE NOT DETECTED");
        }
    }
}