CODEWITHSUNDEEP
javarecursionmultidimensional-arraydepth-first-searchadjacency-matrix
JohnMurphy27
JohnMurphy27

Reputation: 35

Depth First Search using Adjacency Matrix?

I am trying to use recursion and a 2D array to implement a Depth First Search on an adjacency matrix and having issues. I'm still new to this, sorry if my mistake is too obvious.

My code does not read the row if all the numbers are all 0 and doesn't show the components visited.

For example a 10x10 martrix that only has 1s on row, column (9,6) and also (6,9) respectively. Everything else is 0.

It should output 

Component: 1
Component: 2
Component: 3
Component: 4
Component: 5
Component: 6 9
Component: 7
Component: 8
Component: 10
Total number of Components: 9

Here is my method so far.

public static void dfs(int i, int[][] G) {
    boolean [] visited = new boolean[10];

    if(!visited[i]){        
        visited[i] = true; // Mark node as "visited"
        System.out.println("Compnent: " );
        System.out.println( i+1 + " ");

        for (int j = 0; j < G[i].length-1; j++) {
            if (G[i][j]==1 && !visited[j]) {   
                dfs(j, G); // Visit node
            }
        }
    }   
}

THe only thing that the above displays is Component 1 and then the method stops.

Upvotes: 2

Views: 9701

Answers (1)

Phi Luu
Phi Luu

Reputation: 192

In your example, there is no connect between the first node and other nodes. Hence, we can't go anywhere from the first node.

The code should be something like this:

public static void dfs(int i, int[][] graph, boolean[] visited) {
    if(!visited[i]){        
        visited[i] = true; // Mark node as "visited"
        System.out.print(i+1 + " ");

        for (int j = 0; j < graph[i].length; j++) {
            if (graph[i][j]==1 && !visited[j]) {   
                dfs(j, graph, visited); // Visit node
            }
        }
    }   
}

public static void main(String[] args) {
    // your matrix declare
    boolean [] visited = new boolean[10];
    int count = 0;
    for(int i = 0; i < graph.length; i++) {
        if(!visited[i]) {
            System.out.println("Compnent: " );
            dfs(i,graph,visited);
            ++count;
        }
    }
    System.out.println("Total number of Components: " + count);
}

Upvotes: 4

Related Questions