Connectivity of a Graph

Question

int dfs(int graph[MAXNODES][MAXNODES],int visited[],int start) {
int stack[MAXNODES];
    int top=-1,i;
    visited[start]=1;
    stack[++top]=start;
    while(top!=-1)
    {
  start=stack[top];
        for(i=0;i<MAXNODES;i++) {
   if(graph[start][i]&&visited[i]==0) {
                stack[++top]=i;
                printf("%d-",i);
                visited[i]=1;
                break;
            }
        }
  if(i==MAXNODES)
            top--;
    }
    return 0;
}

The above code implements the dfs on a Graph stored as an Adjacency Matrix, I request a suggestion, what change should i be doing to know whether the generated graph is connected or not.

Answer 1

You'd need to store the edges generated by travelling from one node to the next. Then you could verify that all the nodes in the graph are connected by edges.

Answer 2

See my answer to an earlier question about strongly connected components.

Your dfs is also very inefficient as written, because you start over scanning at i=0 repeatedly; your stack should remember where you left off and continue from there. Recursion is more natural, but if you have bounded call stack size, then an explicit stack is best (for huge trees only).

Here's a recursive dfs. If you're not interested in storing the dfs tree, you can just store 1 in predecessor[] instead of the node you reached it from):

const unsigned MAXNODES=100;

/* predecessor must be 0-initialized by the caller; nodes graph[n] that are
 reached from start will have predecessor[n]=p+1, where graph[pred] is the
 predecessor via which n was reached from graph[start].
 predecessor[start]=MAXNODES+1 (this is the root of the tree; there is NO
 predecessor, but instead of 0, I put a positive value to show that it's
 reached).

 graph[a][b] is true iff there is a directed arc from a->b

 */

void dfs(bool graph[MAXNODES][MAXNODES],unsigned predecessor[]
         ,unsigned start,unsigned pred=MAXNODES) 
{
    if (predecessor[start]) return;
    predecessor[start]=pred+1;
    for (unsigned i=0;i<MAXNODES;++i)
        if (graph[start][i])
            dfs(graph,predecessor,i,start);
}

Here's a non-recursive dfs patterned on the above, but using the same stack variable for pred and i (in general you'd have a stack variable for every local variable and parameter that can change in your recursion):

void dfs_iter(bool graph[MAXNODES][MAXNODES],unsigned predecessor[]
              ,unsigned start)
{
    unsigned stack[MAXNODES]; // node indices
    unsigned n,pred;
    int top=0;
    stack[top]=start;
    for(;;) {
    recurse:
        // invariant: stack[top] is the next (maybe reached) node
        n=stack[top];
        if (!predecessor[n]) { // not started yet
            pred=top>0?stack[top-1]:MAXNODES;
            //show(n,pred);
            predecessor[n]=pred+1;
            // the first thing we can reach from n
            for (unsigned i=0;i<MAXNODES;++i)
                if (graph[n][i] && !predecessor[i]) {
                    stack[++top]=i; goto recurse; // push
                }
        }
        if (top>0) {
            pred=stack[top-1];
            // the next thing we can reach from pred after n
            for (unsigned i=n+1;i<MAXNODES;++i)
                if (graph[pred][i]) {
                    stack[top]=i; goto recurse; // replace top
                }
            --top;
        } else
            return;
    }
}

This could be structured without the goto (it's just a named continue to the outmost loop), but without any more real clarity in my opinion.

Anyway, recursive calls are far simpler. There's recursive pseudocode for Tarjan's strongly connected components algorithm you can transcribe fairly directly. If you need help making it non-recursive (explicit stack), ask.

Answer 3

Run Dijkstra's algorithm. If at the end your queue is empty and some of the vertices aren't colored your graph isn't connected. This is guaranteed linear time, the dfs approach has a worst case analysis of quadratic.