06-图1 列出连通集 (25分)

给定一个有NN个顶点和EE条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N-1N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。

输入格式:

输入第1行给出2个整数NN(0<N/le 100<N≤10)和EE，分别是图的顶点数和边数。随后EE行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。

输出格式:

按照"{ v_1v​1​​ v_2v​2​​ ... v_kv​k​​ }"的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。

输入样例:

8 60 70 12 04 12 43 5
输出样例:
{ 0 1 4 2 7 }{ 3 5 }{ 6 }{ 0 1 2 7 4 }{ 3 5 }{ 6 }
思路:
开始的时候我认为邻接表和邻接矩阵都是ok的，于是就先码了邻接表的代码，如下：
/* 邻接表 */#include <queue> #include <stdlib.h> #include <stdio.h> #define MaxVertexNum 100    /* 最大顶点数设为100 */typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */typedef int WeightType;        /* 边的权值设为整型 */typedef char DataType;        /* 顶点存储的数据类型设为字符型 */using namespace std;/* 边的定义 */typedef struct ENode *PtrToENode;struct ENode{    Vertex V1, V2;      /* 有向边<V1, V2> */    WeightType Weight;  /* 权重 */};typedef PtrToENode Edge; /* 邻接点的定义 */typedef struct AdjVNode *PtrToAdjVNode; struct AdjVNode{    Vertex AdjV;        /* 邻接点下标 */    WeightType Weight;  /* 边权重 */    PtrToAdjVNode Next;    /* 指向下一个邻接点的指针 */};/* 顶点表头结点的定义 */typedef struct Vnode{    PtrToAdjVNode FirstEdge;/* 边表头指针 */    DataType Data;            /* 存顶点的数据 */    /* 注意：很多情况下，顶点无数据，此时Data可以不用出现 */} AdjList[MaxVertexNum];    /* AdjList是邻接表类型 */ /* 图结点的定义 */typedef struct GNode *PtrToGNode;struct GNode{      int Nv;     /* 顶点数 */    int Ne;     /* 边数   */    AdjList G;  /* 邻接表 */};typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */void CreatEdge(LGraph Graph,int V,int W){	//令下标为V的头节点的指针域指向W 	PtrToAdjVNode p=(PtrToAdjVNode)malloc(sizeof(AdjVNode));	p->AdjV=W;	p->Next=Graph->G[V].FirstEdge;	Graph->G[V].FirstEdge=p;		//令下标为W的头节点的指针域指向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为出发点对邻接矩阵存储的图Graph进行BFS搜索 */	queue<int> q;	q.push(S);/* S入队列 */	printf("%d ",S);	Visited[S]=true;/* 标记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类型数组，记录对应下标的端点是否访问过 	{		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数组 	{		Visited[i]=false;	}		for(int i=0;i<Graph->Nv;i++)	{		if(!Visited[i])		{			printf("{ ");			BFS(Graph,i,Visited);			printf("}/n");		}	}		return 0;} 但是经过运行，发现尽管输出的数值顺序不合要求。经过观察，发现BFS的输出是有顺序的，按照从小到大的顺序排序。因此更改了部分代码，改为用邻接矩阵的方式来实现。
/* 图的邻接矩阵表示法 */#include <queue> #include <stdlib.h> #include <stdio.h> #define MaxVertexNum 100    /* 最大顶点数设为100 */#define INFINITY 65535        /* ∞设为双字节无符号整数的最大值65535*/typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */typedef int WeightType;        /* 边的权值设为整型 */typedef char DataType;        /* 顶点存储的数据类型设为字符型 */using namespace std;/* 边的定义 */typedef struct ENode *PtrToENode;struct ENode{	Vertex V1,V2;		/* 有向边<V1, V2> */	WeightType Weight;	/* 权重 */};typedef PtrToENode Edge;/* 图结点的定义 */typedef struct GNode *PtrToGNode;struct GNode{	int Nv;				/* 顶点数 */	int Ne;				/* 边数   */	WeightType G[MaxVertexNum][MaxVertexNum];	/* 邻接矩阵 */	DataType Data[MaxVertexNum];		/* 存顶点的数据 */    /* 注意：很多情况下，顶点无数据，此时Data[]可以不用出现*/};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;}