有向和断开图中的循环检测

Question

我正在尝试确定图形是否包含循环。我已经申请了dfs。问题是我的代码将任何图形分类为循环图形。

这是我的代码：

public class Graph {
    public static int nodeno;
    public static int edgeno;
    public static int graph[][];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        nodeno = in.nextInt();
        edgeno = in.nextInt();
        graph = new int[nodeno][nodeno];
        for (int i = 0; i < edgeno; i++) {
            int from = in.nextInt();
            int to = in.nextInt();
            graph[from][to] = 1;
        }
        if (isCyclic())
            System.out.println("Contain cycle");
        else
            System.out.println("No Cycle");

    }

    private static boolean isCyclic() {
        boolean[] visit = new boolean[nodeno];
        boolean[] recStack = new boolean[nodeno];
        for (int i = 0; i < nodeno; i++) {
            if (isCyclicUtil(i, visit, recStack))
                return true;
        }
        return false;
    }

    private static boolean isCyclicUtil(int s, boolean[] visit, boolean[] recStack) {
        if (visit[s] == false) {
            visit[s] = true;
            recStack[s] = true;
            for (int i = 0; i < nodeno; i++) {
                if (graph[s][i] == 1) {
                    if (!visit[i] && isCyclicUtil(i, visit, recStack))
                        return true;
                    else if (recStack[i])
                        return true;
                }
            }

        }
        recStack[s] = false;
        return false;

    }
}

我的示例输入是

这里的输出应该是 No cycle 但它显示的是 contain cycle。找不到我的错。任何人都可以帮助我吗？

Answer 1

示例输入与 reader 格式不匹配。 reader 需要边列表而不是邻接矩阵。根据您使用的格式，提供的图实际上是循环的：边为 0->1、1->0 ..

可能你的意思是：

有向和断开图中的循环检测

cycle detection in a directed & disconnected graph

java

graph

depth-first-search