java 中图表的连通性

Question

我已经从我的课本中实现了 BFS 算法，我正在尝试修改它以在发现非连接图时抛出异常。我的 BFS 使用布尔数组来存储是否已到达节点。在运行来自根节点的 BFS 之后，我认为我可以遍历数组并检查是否到达了每个节点。我的代码每次都会抛出异常，我不知道为什么。任何指导将不胜感激谢谢！

代码：

private int bfs(Graph G, int s) {
    int d = 0;
    Queue<Integer> q = new Queue<>();
    int distTo[] = new int[G.V()], max = 0;
    boolean[] marked = new boolean[G.V()];
    int[] edgeTo = new int[G.V()];
    for(int v = 0; v < G.V(); v++) {
        distTo[s] = Integer.MAX_VALUE;
        marked[s] = true;
        distTo[s] = 0;
        q.enqueue(s);
    }
    
    while(!q.isEmpty()) {
        d = q.dequeue();
        for(int w : G.adj(d)) {
            if(!marked[w]) {
                edgeTo[w] = d;
                distTo[w] = distTo[d] + 1;
                marked[w] = true;
                q.enqueue(w);
            }
        }
        for(boolean x : marked) {
            if(x == false) throw new RuntimeException("not a connected graph.");
        }
    }
    return d;
}

Answer 1

您在处理每个顶点后检查连通性。只有在最简单的图中，第一个顶点后测试才会成功。

相反，您应该使用一个顶点作为队列的种子，并将 for 循环测试的连通性移出 while 循环。

java 中图表的连通性

Connectivity of a graph in java

java

algorithm

data-structures

tree

breadth-first-search