[Math] Checking if a graph is fully connected

graph theoryrandom-graphs

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

Best Answer

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.

Related Question