給定一個有NN個頂點和EE條邊的無向圖，請用DFS和BFS分別列出其所有的連通集。假設(shè)頂點從0到N-1N?1編號。進行搜索時，假設(shè)我們總是從編號最小的頂點出發(fā)，按編號遞增的順序訪問鄰接點。

輸入格式:

輸入第1行給出2個整數(shù)NN(0<N/le 100<N≤10)和EE，分別是圖的頂點數(shù)和邊數(shù)。隨后EE行，每行給出一條邊的兩個端點。每行中的數(shù)字之間用1空格分隔。

輸出格式:

按照"{ v_1v?1?? v_2v?2?? ... v_kv?k?? }"的格式，每行輸出一個連通集。先輸出DFS的結(jié)果，再輸出BFS的結(jié)果。

輸入樣例:

8 60 70 12 04 12 43 5
輸出樣例:
{ 0 1 4 2 7 }{ 3 5 }{ 6 }{ 0 1 2 7 4 }{ 3 5 }{ 6 }
思路:
開始的時候我認(rèn)為鄰接表和鄰接矩陣都是ok的，于是就先碼了鄰接表的代碼，如下：
/* 鄰接表 */#include <queue> #include <stdlib.h> #include <stdio.h> #define MaxVertexNum 100    /* 最大頂點數(shù)設(shè)為100 */typedef int Vertex;         /* 用頂點下標(biāo)表示頂點,為整型 */typedef int WeightType;        /* 邊的權(quán)值設(shè)為整型 */typedef char DataType;        /* 頂點存儲的數(shù)據(jù)類型設(shè)為字符型 */using namespace std;/* 邊的定義 */typedef struct ENode *PtrToENode;struct ENode{    Vertex V1, V2;      /* 有向邊<V1, V2> */    WeightType Weight;  /* 權(quán)重 */};typedef PtrToENode Edge; /* 鄰接點的定義 */typedef struct AdjVNode *PtrToAdjVNode; struct AdjVNode{    Vertex AdjV;        /* 鄰接點下標(biāo) */    WeightType Weight;  /* 邊權(quán)重 */    PtrToAdjVNode Next;    /* 指向下一個鄰接點的指針 */};/* 頂點表頭結(jié)點的定義 */typedef struct Vnode{    PtrToAdjVNode FirstEdge;/* 邊表頭指針 */    DataType Data;            /* 存頂點的數(shù)據(jù) */    /* 注意：很多情況下，頂點無數(shù)據(jù)，此時Data可以不用出現(xiàn) */} AdjList[MaxVertexNum];    /* AdjList是鄰接表類型 */ /* 圖結(jié)點的定義 */typedef struct GNode *PtrToGNode;struct GNode{      int Nv;     /* 頂點數(shù) */    int Ne;     /* 邊數(shù)   */    AdjList G;  /* 鄰接表 */};typedef PtrToGNode LGraph; /* 以鄰接表方式存儲的圖類型 */void CreatEdge(LGraph Graph,int V,int W){	//令下標(biāo)為V的頭節(jié)點的指針域指向W 	PtrToAdjVNode p=(PtrToAdjVNode)malloc(sizeof(AdjVNode));	p->AdjV=W;	p->Next=Graph->G[V].FirstEdge;	Graph->G[V].FirstEdge=p;		//令下標(biāo)為W的頭節(jié)點的指針域指向V 	PtrToAdjVNode q=(PtrToAdjVNode)malloc(sizeof(AdjVNode));	q->AdjV=V;	q->Next=Graph->G[W].FirstEdge;	Graph->G[W].FirstEdge=q;	}void DFS(LGraph Graph,int V,bool Visited[]){	PtrToAdjVNode W;		PRintf("%d ",V);	Visited[V]=true;		for(W=Graph->G[V].FirstEdge;W!=NULL;W=W->Next)	{		if(!Visited[W->AdjV])		{			DFS(Graph,W->AdjV,Visited);		}	}}void BFS(LGraph Graph,int S,bool Visited[]){ /* 以S為出發(fā)點對鄰接矩陣存儲的圖Graph進行BFS搜索 */	queue<int> q;	q.push(S);/* S入隊列 */	printf("%d ",S);	Visited[S]=true;/* 標(biāo)記S已訪問 */		int V;	while(!q.empty())	{		V=q.front();		q.pop();/* 彈出V */		PtrToAdjVNode p=Graph->G[V].FirstEdge;		for(;p!=NULL;p=p->Next)		//對于所有與點V相連接的點 		{			if(!Visited[p->AdjV])			{				q.push(p->AdjV);				printf("%d ",p->AdjV);				Visited[p->AdjV]=true;			}		}			}}int main(){		LGraph Graph=(LGraph)malloc(sizeof(GNode));	scanf("%d",&Graph->Nv); 	scanf("%d",&Graph->Ne);	for(int i=0;i<Graph->Nv;i++)	{		Graph->G[i].FirstEdge=NULL;	//鄰接表頭指針初始化為NULL 	}		int V=0,W=0;	for(int i=0;i<Graph->Ne;i++)//輸入邊的端點信息 	{		scanf("%d",&V); 		scanf("%d",&W);		CreatEdge(Graph,V,W);	}		bool Visited[Graph->Nv];	for(int i=0;i<Graph->Nv;i++)//建一個bool類型數(shù)組，記錄對應(yīng)下標(biāo)的端點是否訪問過 	{		Visited[i]=false;//初始化 	}		for(int i=0;i<Graph->Nv;i++)	{		if(!Visited[i])		{			printf("{ ");			DFS(Graph,i,Visited);			printf("}/n");		}	}			for(int i=0;i<Graph->Nv;i++)//重置Visited數(shù)組 	{		Visited[i]=false;	}		for(int i=0;i<Graph->Nv;i++)	{		if(!Visited[i])		{			printf("{ ");			BFS(Graph,i,Visited);			printf("}/n");		}	}		return 0;} 但是經(jīng)過運行，發(fā)現(xiàn)盡管輸出的數(shù)值順序不合要求。經(jīng)過觀察，發(fā)現(xiàn)BFS的輸出是有順序的，按照從小到大的順序排序。因此更改了部分代碼，改為用鄰接矩陣的方式來實現(xiàn)。
/* 圖的鄰接矩陣表示法 */#include <queue> #include <stdlib.h> #include <stdio.h> #define MaxVertexNum 100    /* 最大頂點數(shù)設(shè)為100 */#define INFINITY 65535        /* ∞設(shè)為雙字節(jié)無符號整數(shù)的最大值65535*/typedef int Vertex;         /* 用頂點下標(biāo)表示頂點,為整型 */typedef int WeightType;        /* 邊的權(quán)值設(shè)為整型 */typedef char DataType;        /* 頂點存儲的數(shù)據(jù)類型設(shè)為字符型 */using namespace std;/* 邊的定義 */typedef struct ENode *PtrToENode;struct ENode{	Vertex V1,V2;		/* 有向邊<V1, V2> */	WeightType Weight;	/* 權(quán)重 */};typedef PtrToENode Edge;/* 圖結(jié)點的定義 */typedef struct GNode *PtrToGNode;struct GNode{	int Nv;				/* 頂點數(shù) */	int Ne;				/* 邊數(shù)   */	WeightType G[MaxVertexNum][MaxVertexNum];	/* 鄰接矩陣 */	DataType Data[MaxVertexNum];		/* 存頂點的數(shù)據(jù) */    /* 注意：很多情況下，頂點無數(shù)據(jù)，此時Data[]可以不用出現(xiàn)*/};typedef PtrToGNode MGraph; void CreatEdge(MGraph Graph,int V,int W){	Graph->G[V][W]=1;	Graph->G[W][V]=1;	}void DFS(MGraph Graph,int V,bool Visited[]){	int W;		printf("%d ",V);	Visited[V]=true;		for(W=0;W<Graph->Nv;W++)	{		if(!Visited[W]&&Graph->G[V][W]==1)		{			DFS(Graph,W,Visited);		}	}}void BFS(MGraph Graph,int S,bool Visited[]){	queue<int> q;	int V;	q.push(S);	printf("%d ",S);	Visited[S]=true;		while(!q.empty())	{		V=q.front();		q.pop();		for(int W=0;W<Graph->Nv;W++)		{			if(!Visited[W]&Graph->G[V][W]==1)			{				q.push(W);				printf("%d ",W);				Visited[W]=true;			}		}			}}int main(){		MGraph Graph=(MGraph)malloc(sizeof(GNode));	scanf("%d",&Graph->Nv); 	scanf("%d",&Graph->Ne);	for(int i=0;i<Graph->Nv;i++)	{		for(int j=0;j<Graph->Nv;j++)		{			Graph->G[i][j]=INFINITY;				}			}		int V=0,W=0;	for(int i=0;i<Graph->Ne;i++)	{		scanf("%d",&V); 		scanf("%d",&W);		CreatEdge(Graph,V,W);	}			bool Visited[Graph->Nv];	for(int i=0;i<Graph->Nv;i++)	{		Visited[i]=false;	}		for(int i=0;i<Graph->Nv;i++)	{		if(!Visited[i])		{			printf("{ ");			DFS(Graph,i,Visited);			printf("}/n");		}	}		for(int i=0;i<Graph->Nv;i++)	{		Visited[i]=false;	}		for(int i=0;i<Graph->Nv;i++)	{		if(!Visited[i])		{			printf("{ ");			BFS(Graph,i,Visited);			printf("}/n");		}	}		return 0;}