CODEWITHSUNDEEP
javaalgorithmrecursiongraphdepth-first-search
Arvind
Arvind

Reputation: 1247

How to check if Graph is connected

I have a un-directed graph, and wanted to know a node is connected to another node or not?

for example 

0 1 0
1 0 1 
0 1 0

In this node 1 is connected to node 3 ( because there is a path from 1 to 2 and 2 to 3 hence 1-3 is connected )

I have written programs which is using DFS, but i am unable to figure out why is is giving wrong result.

I don't want to keep any global variable and want my method to return true id node are connected using recursive program

public static boolean isConnectedGraph(int[][] graph, int start, int end,
        int visited[]) {
    visited[start] = 1;
    if (graph[start][end] == 1) {
        System.out.println("Yes connected....");
        return true;
    }
    for (int i = 0; i < graph[0].length; i++) {
        if (graph[start][i] == 1 && visited[i] == 0) {
            visited[i] =1;
            isConnectedGraph(graph, i, end, visited);

        }
    }
    return false;
}

Upvotes: 2

Views: 11935

Answers (1)

amit
amit

Reputation: 178521

You don't do anything with the result of the recursive call isConnectedGraph(graph, i, end, visited);. You should assign it to a variable, and if it is true - return true.

Change the main loop to something like:

for (int i = 0; i < graph[0].length; i++) {
    if (graph[start][i] == 1 && visited[i] == 0) {
        visited[i] =1;
        if (isConnectedGraph(graph, i, end, visited)) return true;

    }
}

Upvotes: 3

Related Questions