CONNECTED COMPONENT OF A GRAPH

Write a function dfs(v) to traverse a graph in a depth-first manner starting from vertex v. Use this function to find connected components in the graph. Modify dfs() to produce a list of newly visited vertices. The graph is represented as adjacency lists.

#include <stdio.h>

#define MAXVERTICES 20
#define MAXEDGES 20

typedef enum {FALSE, TRUE, TRISTATE} bool;
typedef struct node node;

struct node {
   int dst;
   node *next;
};

void printGraph( node *graph[], int nvert ) {
   /*
    * prints the graph.
    */
   int i, j;
   for( i=0; i<nvert; ++i ) {
       node *ptr;
       for( ptr=graph[i]; ptr; ptr=ptr->next )
           printf( "[%d] ", ptr->dst );
       printf( "\n" );
   }
}

void insertEdge( node **ptr, int dst ) {
    /*
     * insert a new node at the start.
     */
    node *newnode = (node *)malloc( sizeof(node) );
    newnode->dst = dst;
    newnode->next = *ptr;
    *ptr = newnode;
}

void buildGraph( node *graph[], int edges[2][MAXEDGES], int nedges ) {
    /*
     * fills graph as adjacency list from array edges.
     */
    int i;
    for( i=0; i<nedges; ++i ) {
        insertEdge( graph+edges[0][i], edges[1][i] );
        insertEdge( graph+edges[1][i], edges[0][i] ); // undirected graph.
    }
}

void dfs( int v, int *visited, node *graph[] ) {
    /*
     * recursively traverse graph from v using visited.
     * and mark all the vertices that come in dfs path to TRISTATE.
     */
    node *ptr;

    visited[v] = TRISTATE;
    //printf( "%d \n", v );
    for( ptr=graph[v]; ptr; ptr=ptr->next )
       if( visited[ ptr->dst ] == FALSE )
           dfs( ptr->dst, visited, graph );
}
void printSetTristate( int *visited, int nvert ) {
    /*
     * prints all vertices of visited which are TRISTATE.
     * and set them to TRUE.
     */
    int i;

    for( i=0; i<nvert; ++i )
       if( visited[i] == TRISTATE ) {
           printf( "%d ", i );
           visited[i] = TRUE;
       }
    printf( "\n\n" );
}

void compINC(node *graph[], int nvert) {
    /*
     * prints all connected components of graph represented using INC lists.
     */
    int *visited;
    int i;

    visited = (int *)malloc( nvert*sizeof(int) );
    for( i=0; i<nvert; ++i )
        visited[i] = FALSE;

    for( i=0; i<nvert; ++i )
        if( visited[i] == FALSE ) {
            dfs( i, visited, graph );
            // print all vertices which are TRISTATE.
            // and mark them to TRUE.
            printSetTristate( visited, nvert );
       }
   free( visited );
}

int main() {
    int edges[][MAXEDGES] = { {0,2,4,5,5,4},
                              {1,1,3,4,6,6}
                           };
    int nvert = 7; // no of vertices.
    int nedges = 6; // no of edges in the graph.
    node **graph = (node **)calloc( nvert, sizeof(node *) );

    buildGraph( graph, edges, nedges );
    printGraph( graph, nvert );
    compINC( graph, nvert );

    return 0;
}