1
$\begingroup$

I have an adjacency matrix of an undirected graph (the main diagonal contains 0's) and I need an algorithm in psuedocode that will check whether the graph is fully connected (i.e. that one can walk from any node to any other node along the links). I currently have one but its not working properly.

Can anyone suggest/describe one? The simplest would be preferable, I'm not worried about any kind of speed up.

Thanks!

ADDITION:

This is the c code im using (it is meant to work like http://wiki.answers.com/Q/Design_an_algorithm_to_check_if_a_given_graph_is_connected):

void checkifgraphpercolates(int N, int sampleindex){

int randomnodenumber;
int randomelementink, rndvertex;
int kelement;
int done = 0;
int i,j,l,m,n,jj,w,q;
int numberofelementsink=0;
int sizeofk;
int sizeofl;
int K[N]; // K is the list of nodes that need to be checked
int L[N]; // L is a 1D array which contains a number of 1's and 0's: should the number of 1's
         // = N then the graph is fully connected.





int qq;
for(qq=0;qq<N;qq++){
    K[qq] = 0;
    L[qq] = 0;
}




rndvertex = (rand()%N);




L[rndvertex] = 1;





for(l=0;l<N;l++){

        if(adjacencymatrix[rndvertex][l] == 1){


            K[l] = 1;
            L[l] = 1;


        }

    }





numberofelementsink = 0;


for(j=0;j<N;j++){
    if(K[j] == 1){
        numberofelementsink++;
        //printf("\n node %i is in k\n, ",j);
        //getchar();
    }
}


done = 0;

while(numberofelementsink>0){

    while(done==0){

        randomelementink = (rand()%N);



        if(K[randomelementink] == 1){
            kelement = randomelementink;

            done = 1;
        }
        else{
            done = 0;
        }

    }

    done = 0;

    K[kelement] = 0;


    for(l=0;l<N;l++){

        if(adjacencymatrix[kelement][l] == 1){

            if(L[l] == 0){
                L[l] = 1;
                K[l] = 1;
            }

        }

    }



    //printf("\nOne round done\n");


numberofelementsink = 0;

for(jj=0;jj<N;jj++){
    if(K[jj] == 1){
        numberofelementsink++;
        //printf("%i, ",jj);
    }
}



}

// Check if mag(L) = N

int sl = 0;


for(m=0;m<N;m++){

    if(L[m] == 1){
        sl++;
    }

}

if(sl == N){
        graphstatus[sampleindex] = 1;
        totalfcgraphs++;
    }
    else{       
        graphstatus[sampleindex] = 0;
    }



//printf("\n\n\nGraph %i status = %i\n[Hit Enter...]\n\n",sampleindex,graphstatus[sampleindex]);

//getchar();



for(q=0;q<N;q++){
    K[q] = 0;
    L[q] = 0;
}


numberofelementsink = 0;

}

where N is the number of nodes

$\endgroup$
6
  • 1
    $\begingroup$ possible duplicate of Powers of Adjacency Matrix (Determination of connection in Graph) $\endgroup$
    – Xoque55
    Nov 4, 2013 at 18:56
  • $\begingroup$ this is not the same question as that at all $\endgroup$
    – apg
    Nov 4, 2013 at 19:02
  • 1
    $\begingroup$ Computing the powers of a potentially large sparse matrix is not a good way to do this in practice. @AlexanderGiles Can you please post your (nonworking) attempt? It will give a hint on what kind of a solution is expected. $\endgroup$ Nov 4, 2013 at 19:16
  • 1
    $\begingroup$ As a matter of fact, it is: Let $G$ be a graph of $k$ vertices which is fully connected. Then for every pair of vertices $a$ and $b$, there is a path of length at most $k$ edges between these vertices (why?). The powers-of-the-adjency matrix gives you paths of a given length quickly. $\endgroup$ Nov 4, 2013 at 19:18
  • $\begingroup$ im using wiki.answers.com/Q/… $\endgroup$
    – apg
    Nov 4, 2013 at 19:38

2 Answers 2

3
$\begingroup$

Suppose that the graph $G$ contains $n$ vertices. Then the largest number of steps it could take to go from a vertex to any other vertex is $n$ steps. If you can calculate the powers of the adjacency matrix $A$, then you should produce $S = A + A^2 + \cdots + A^n$. If there are any zeroes in the matrix $S$, it is impossible for some pair of vertices to connect in $n$ steps or less, so this pair will never connect, and the graph is not connected.

There are ways to compute larger powers of $A$ by keeping track of the power of $A$ with an exponent that is a power of 2. Examples: $$A^3 = A^2A \\ A^6=A^4A^2 \\ A^{27}=A^{16}A^8A^2A^1$$ I recommend looking into the binary representation of your original exponent to find the powers of the corresponding "powers of 2" adjacency matrices. Then add them all up and see if the resulting matrix contains any zeros! If not, it is fully connected.

$\endgroup$
1
$\begingroup$

One can also use Breadth First Search (BFS).

The BFS algorithm searches the graph from a random starting point, and continues to find all its connected components. If there is only one, the graph is fully connected.

Also, in graph theory, this property is usually referred to as "connected". i.e. "the graph is connected".

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .