algorithm - 在图中寻找连通性

Question

我看了this Princeton University connected components tutorial并尝试运行我电脑上给出的代码(跳到 13 分钟的代码)。代码应该找出图中所有不同的连接组件，并为每个顶点分配一个“id”，以标识它属于哪个组件。我做了一个示例图来测试它，请看这里:

![视觉呈现][1]

当我运行下面的代码时，它打印出 ids 为 0,0,1,2,3 但它们应该是 0,0,0,1,1。知道我做错了什么吗？

public class ConnectedComponents {
    public boolean[] marked;
    public int[] id;
    public int count;


    public ConnectedComponents() {
        //Make a Graph with 5 vertices, and 4 edges
        Graph g = new Graph(5, false, false);
        g.addEdge(0, 1); g.addEdge(0, 2);g.addEdge(1, 2); 
        g.addEdge(3, 4);

        int numVertices = g.getNumberOfVertices();
        marked = new boolean[numVertices];
        id = new int[numVertices];
        for(int v = 0; v < numVertices; v++) {
            if(!marked[v]) {
                dfs(g, v);
                count++;
            }
        }
    }

    public void dfs(Graph g, int v) {
        marked[v] = true;
        id[v] = count;
        // loops through each vertex that's connected to v
        for(int w: g.getEdgeMatrix()[v]) {
            if(!marked[w]) {
                dfs(g, w);
            }
        }
    }

    public int id(int v) {
        return id[v];
    }

    public static void main(String [] args){
        ConnectedComponents cc = new ConnectedComponents();
        for(int i = 0; i < cc.id.length; i++) {
            System.out.println(cc.id[i]);
        }
    }

}

/image/vhTxD.jpg

Answer 1

由于 addEdge 的实现，您的 DFS 有效地在有向图上运行。更改它以添加反向边缘。