CODEWITHSUNDEEP
javaarraysgraph
jack
jack

Reputation: 45

Check if graph is fully connected - java

I want to check if a graph is fully connected - that is if each node is connected to each other node.

I take input from a graph file and place it in a two-dimensional array. An example of a fully-connected 2D array looks like this:

{{0, 1, 1, 1, 1}
 {1, 0, 1, 1, 1}
 {1, 1, 0, 1, 0}
 {1, 1, 1, 0, 1}
 {1, 1, 1, 1, 0}}

How to I write a boolean method that checks if this is fully connected? I am a bit lost of ideas, so any tips, suggestions and help are quite welcome.

Upvotes: 2

Views: 4307

Answers (3)

elias
elias

Reputation: 15480

Basically, a matrix representation of a directed graph is fully connected if only the main diagonal contains zeros, because the main diagonal represents the connection of each vertex with itself.
Anything different from this represents a not fully connected graph. So, in a very very simple way:

boolean isFullyConnected(int[][]m)
    for (int i = 0; i < m.length; i++) //iterate over rows
        for (int j = 0; j < m[i].length; j++) //iterate over columns
            if(i != j && m[i][j] == 0) //if not in main diag. and not connected
                return false;
    return true;
}

If it's not directed (you can say that a vertex is connected to another if there's a link in just one direction), you can change the algorithm simply adding the reverse condition && m[j][i] == 0:

boolean verify(int[][]m){
    for (int i = 0; i < m.length; i++) 
        for (int j = 0; j < m[i].length; j++) 
            if(i != j && m[i][j] == 0 && m[j][i] == 0) //there's the difference
                return false;
    return true;
}

It is because, imagining folding the matrix by line of the main diagonal, each overlap of index will represent the connection between two vertex in both directions, and you just need one.

Upvotes: 3

vacsora
vacsora

Reputation: 207

First of all your graph in your 2d array implies directed graph because (5 and 3) is connected with an edge but (3 and 5) is not. For the same reason it is not fully connected.

Java code to check full connectivity:

public boolean checkFullConn( int[][] grid ) {
    boolean fully = true;
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 5; i++)
            if (i<>j)
                if (grid[i,j]==0)
                    fully = false;
    return fully;
}

To check simple connectivity (not full), the following Java code basically checks wether all other nodes eventually connect to node1.

public boolean checkConn( int[][] grid ) {
    boolean conn1[5];
    for (int i = 1; i <= 5; i++)
        conn1[i] = false;
    conn1[1] = true;

    for (int k = 1; k <= 5; k++)
        for (int i = 1; i <= 5; i++)
            if conn1[i]
                for (int j = 1; j <= 5; i++)
                    if (grid[i,j]==1) || grid(j,i))
                        conn1[j] = true;

    boolean conn = true;
    for (int i = 2; i <= 5; i++)
        conn = conn && conn1[i];
    return conn;
}

Upvotes: 1

Tsung-Ting Kuo
Tsung-Ting Kuo

Reputation: 1170

One plausible (but slow) way is to do matrix multiplication to itself for k times, where k is the number of nodes (in your example k = 5). That is, suppose the matrix in your example is A, then do A = A x A for 5 times. Afterwards, you can simply check any one row if it - if the row are all non-zeros, then the graph is fully connected. Please refer to this link for more information.

Upvotes: 2

Related Questions