無方向図の連通成分

無方向図の連通成分
一、無方向図を遍歴する
(一)連通図については、図中のいずれかの頂点から深さ優先探索または広さ優先探索を行うだけで、図中のすべての頂点にアクセスすることができる.
(二)非連通図の場合、複数の頂点から探索する必要があり、新しい開始点から探索するたびに得られる頂点アクセスシーケンスは、その各連通成分の頂点セットである.
 
二、連通成分例
(a)無方向図G 3(b)G 3の深さ優先探索森林
図7-13
図7−13 aの無方向図G 3については、Aからアクセス可能な頂点シーケンスがA、L、M、J、B、F、Cの順である場合、深度優先探索DFS[cl]法を用いて巡回する.このプロセスはDFSを1回呼び出した.次にDから残りの頂点を巡り,Dからアクセス可能な頂点シーケンスはD,Eである.このプロセスはまたDFSを呼び出した.最後に、図中の残りの頂点K、H、IをGから巡回し、DFSを3回目に呼び出す.
従って、無方向図に対してDFSループを行い、DFSが呼び出されるたびにこの非連通図の連通成分が得られ、DFSが呼び出される回数が連通成分の個数となる.

/*
        
  ：   @    http://www.cnblogs.com/yanlingyin/
2011-12-26 

*/
#include 
#include 

struct node                       /*             */
{
   int vertex;                    /*              */
   struct node *nextnode;         /*            */
};
typedef struct node *graph;       /*            */
struct node head[9];              /*              */
int visited[9];                   /*              */
int id[9];                        /*         */
int count = 0;					  /*      */
/********************            ********************/
void creategraph(int node[20][2],int num)/*num       */
{
   graph newnode;                 /*          */
   graph ptr;
   int from;                      /*               */
   int to;                        /*               */
   int i;
   for ( i = 0; i < num; i++ )    /*       ，     */
   {
      from = node[i][0];         /*                     */
      to = node[i][1];           /*                     */
      
   /*       */
      newnode = ( graph ) malloc(sizeof(struct node));
      newnode->vertex = to;        /*              */
      newnode->nextnode = NULL;    /*              */
      ptr = &(head[from]);         /*                */
      while ( ptr->nextnode != NULL ) /*          */
         ptr = ptr->nextnode;     /*               */
      ptr->nextnode = newnode;    /*             */
   }
}

/**********************           ********************/
void dfs(node head[9],int current){/*           */
	node* p;
	node* stack[9];
	int top=-1,vertex;
	printf("%d
",current);
	visited[current] = 1;
	stack[++top] = head[current].nextnode;
	id[current] = count;
	while(top > -1){
		p = stack[top];
		while(p != NULL){
			vertex = p->vertex;
			if(visited[vertex] == 0){
				printf("%d
",vertex);
				visited[vertex] = 1;
				id[vertex] = count;
				stack[++top] = head[vertex].nextnode;
			}
			p = p->nextnode;
		}
		if(p == NULL){
			top--;
		}
	}
}
/**********************        ********************/
bool connect(int v ,int w){         /**/
	return id[v] == id[w];
}
/**********************    ********************/
int _id(int v){
	return id[v];
}
/**********************      ********************/
int _count(){
	return count;
}
/******************************    ******************************/
int main()
{
   graph ptr;
   int node[20][2] = { {1, 2}, {2, 1},  /*          */
                       {1, 3}, {3, 1},
                       {1, 4}, {4, 1},
                       {2, 5}, {5, 2},
                       {2, 6}, {6, 2},
                       {3, 7}, {7, 3},
                       {4, 7}, {4, 4},
                       {5, 8}, {8, 5},
                       {6, 7}, {7, 6},
                       {7, 8}, {8, 7} };
   int i;
   //clrscr();
   for ( i = 1; i <= 8; i++ )      /*            */
   {
      head[i].vertex = i;         /*               */
      head[i].nextnode = NULL;    /*                */
      visited[i] = 0;             /*            */
   }
   creategraph(node,20);          /*               */
   printf("Content of the gragh's ADlist is:
");
   for ( i = 1; i <= 8; i++ )
   {
      printf("vertex%d ->",head[i].vertex); /*        */
      ptr = head[i].nextnode;             /*        */
      while ( ptr != NULL )       /*              */
      {
         printf(" %d ",ptr->vertex);  /*          */
         ptr = ptr->nextnode;         /*           */
      }
      printf("
");               /*                  */
   }
   printf("
The end of the dfs are:
");
   for(i=1;i<=8;i++){
   		if(visited[i] == 0){
   		dfs(head,1);                        /*            */
   		count++;
   	}
   }
   printf("
");    
   printf("
The end of the dfs are:
");              /*                  */
  // getch();
}

参照先:http://www.edushanghai.org/Item/7807.aspx