使用广度优先搜索算法检测无向图中的循环

Question

Using this algorithm I am getting wrong answers but my testcases are giving correct answers. Let me know where I am going wrong. In this algorithm I have used Breadth First Search(BFS) technique to find to detect the cycle.

// Using bfs approach
class Solution{
    public boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj){
        Queue<Integer> q=new LinkedList<>();
        boolean vis[]=new boolean[V];
        int parent[]=new int[V];
        parent[0]=-1;
        q.add(0);
        vis[0]=true;
        while(!q.isEmpty()){
            int cur=q.poll();
            for(int  i:adj.get(cur)){
                // if(vis[i]==true) return true;
                if(!vis[i]){
                    q.add(i);
                    parent[i]=cur;
                    vis[i]=true;
                }
                else if(parent[cur]!=i) return true;
            }
        }
        return false;
    }
}

Answer 1

假设

该方法假定输入无向图是连通的。

请检查它是否是问题域所有可能输入的有效假设。

可能的解决方案

现有方法适用于单个森林
向现有方法添加额外的 startNode 和 visited 参数
添加另一个包装器方法，它将为每个未访问的节点（森林）调用现有方法。


  boolean hasCycle(final int N, final List<List<Integer>> graph) {
    final boolean[] visited = boolean[N];

    for (int vertex = 0; vertex < N; vertex++) {
      if (!visited[vertex] && hasCycle(N, vertex, visited, graph)) {
        return true;
      }
    }

    return false;
  }

两种方法

  boolean hasCycle(final int N, final int start, final boolean[] visited, final List<List<Integer>> graph) {
    visited[start] = true;

    final int parent[] = new int[N];
    parent[start] = -1;

    final Queue<Integer> q = new LinkedList<>();
    q.add(start);

    while(!q.isEmpty()) {
      final int node = q.poll();

      // assumes for nodes without edges, an empty list will be returned
      for(int adj : graph.get(node)) {
        if (!visited[adj]) {
          q.add(adj);
          parent[adj] = node;
          visited[adj] = true;
        } else if (parent[node] != adj) {
          return true;
        }
      }
    }

    return false;
  }

  boolean hasCycle(final int N, final List<List<Integer>> graph) {
    final boolean[] visited = boolean[N];

    for (int vertex = 0; vertex < N; vertex++) {
      if (!visited[vertex] && hasCycle(N, vertex, visited, graph)) {
        return true;
      }
    }

    return false;
  }

免责声明

这是未经测试和编译的代码（在 SO 中键入）

使用广度优先搜索算法检测无向图中的循环

Detect Cycle in an undirected graph using Breadth First Search Algorithm

java

algorithm

graph

dsa

假设

可能的解决方案

两种方法

免责声明