CODEWITHSUNDEEP
algorithmdata-structuresgraphdepth-first-search
Coding247
Coding247

Reputation: 29

Finding Connectivity in a Graph

I watched this Princeton University connected components tutorial and tried to run the code given on my computer (skip to 13 mins for code). The code should figure out all the different connected components of the graph and assign each vertex an 'id' which identifies which component it belongs to. I made a sample graph to test it, see here for:

![visual representation][1]

When I run the code below, it prints out the ids to be 0,0,1,2,3 but they should be 0,0,0,1,1. Any ideas what I'm doing wrong?

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]);
        }
    }

}

https://i.sstatic.net/vhTxD.jpg

Upvotes: 0

Views: 88

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65437

Because of the implementation of addEdge, your DFS is effectively operating on a directed graph. Change it to add the reverse edges.

Upvotes: 1

Related Questions