Page 291 Exercise 11


The modification appears below.  The function extends dfs() so that it prints out all of the connected components of a graph.  The traverse() function is the original dfs() function.  Itstops when it reaches the first node in a different subgraph.  The main() function checks to see if the current node is not NULL and has not been visited.  If both of these conditions prevail, it restarts traverse with the new node.  It continues in
this fashion until all of the nodes have been examined.The code appears below:

int main ()
{

  int i,n;
  create_list(graph, &n);
  for (i=0; i< MAX_VERTICES;i++)
      visited[i]=FALSE;
   printf("CONNECTED SUBGRAPHS\n"); 
   i = 0;
    while (graph[i]) {
      /*start the next subgraph*/
        if (!visited[i]){
           printf("%3d", i);
           traverse(i);
           printf("\n"); 
         }
        i++;
      }
}

void traverse(int x1)
{/*visit each of the vertices that are connected through x1*/
   node_pointer temp;
      visited[x1]=TRUE;
      temp= graph[x1];
      while (temp) 
	  {/*visit all vertices adjacent to x1*/
        if (visited[temp->vertex] == FALSE) {
          traverse(temp->vertex);
		  printf("%3d ",temp->vertex);
        }
        temp=temp->link;  
      }
} /*traverse*/