题目：
给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。
输入格式
输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。
输出格式
按照"{ v1 v2 … vk }"的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。
输入样例
8 6
0 7
0 1
2 0
4 1
2 4
3 5
输出样例
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }
算法
算法描述
建邻接表图列出连通集子集（DFS）列出连通集子集（BFS）
提示：邻接表中插入边时，要根据邻接点的大小排序插入
代码实现
int main()
{
int N
,E
;
scanf("%d%d",&N
,&E
);
LGraph G
=CreatGraph(N
,E
);
{
Edge edge
=(PtrToENode
)malloc(sizeof(struct ENode
));
int i
;
for(i
=0;i
<E
;i
++){
scanf("%d %d",&(edge
->V
),&(edge
->W
));
InsertEdge(G
,edge
);
}
free(edge
);
}
ListComponent(G
,DFS
);
{
int i
;
for(i
=0;i
<G
->vertexNumber
;i
++){
visited
[i
]=0;
}
}
ListComponent(G
,BFS
);
FreeGraph(G
);
return 0;
}
图的基本操作：图的创建、边的插入、释放图空间
#define MAXVERTEXNUM 10
typedef int Vertex
;
int visited
[MAXVERTEXNUM
];
int queue
[MAXVERTEXNUM
];
int rear
=-1,head
=-1;
typedef struct ENode
* PtrToENode
;
struct ENode
{
Vertex V
;
Vertex W
;
};
typedef PtrToENode Edge
;
typedef struct AdjVNode
* PtrToAdjVNode
;
struct AdjVNode
{
Vertex AdjV
;
PtrToAdjVNode Next
;
};
typedef struct HNode
{
PtrToAdjVNode FirstAdjV
;
}AdjList
[MAXVERTEXNUM
];
typedef struct Graph
* LGraph
;
struct Graph
{
int vertexNumber
;
int edgeNumber
;
AdjList GraphList
;
};
LGraph
CreatGraph(int N
,int E
)
{
LGraph G
=(LGraph
)malloc(sizeof(struct Graph
));
G
->vertexNumber
=N
;
G
->edgeNumber
=E
;
Vertex i
;
for(i
=0;i
<N
;i
++){
G
->GraphList
[i
].FirstAdjV
=NULL;
}
return G
;
}
void InsertEdge(LGraph G
,PtrToENode E
)
{
PtrToAdjVNode VAdjNode
=(PtrToAdjVNode
)malloc(sizeof(struct AdjVNode
));
VAdjNode
->AdjV
=E
->W
;
PtrToAdjVNode L
=G
->GraphList
[E
->V
].FirstAdjV
;
if(L
==NULL||L
->AdjV
>E
->W
){
VAdjNode
->Next
=L
;
G
->GraphList
[E
->V
].FirstAdjV
=VAdjNode
;
}else{
for(;L
->Next
&&L
->Next
->AdjV
<E
->W
;L
=L
->Next
);
VAdjNode
->Next
=L
->Next
;
L
->Next
=VAdjNode
;
}
PtrToAdjVNode AdjVNode
=(PtrToAdjVNode
)malloc(sizeof(struct AdjVNode
));
AdjVNode
->AdjV
=E
->V
;
L
=G
->GraphList
[E
->W
].FirstAdjV
;
if(L
==NULL||L
->AdjV
>E
->V
){
AdjVNode
->Next
=L
;
G
->GraphList
[E
->W
].FirstAdjV
=AdjVNode
;
}else{
for(;L
->Next
&&L
->Next
->AdjV
<E
->V
;L
=L
->Next
);
AdjVNode
->Next
=L
->Next
;
L
->Next
=AdjVNode
;
}
}
void FreeGraph(LGraph G
)
{
Vertex i
=0;
PtrToAdjVNode AdjNode
;
PtrToAdjVNode T
;
for(i
=0;i
<G
->vertexNumber
;i
++){
AdjNode
=G
->GraphList
[i
].FirstAdjV
;
if(AdjNode
!=NULL){
T
=AdjNode
->Next
;
while(AdjNode
){
free(AdjNode
);
AdjNode
=T
;
if(T
){
T
=T
->Next
;
}
}
}
}
}
DFS
void DFS(LGraph G
,int V
)
{
if(visited
[V
]==0){
visited
[V
]=1;
printf(" %d",V
);
PtrToAdjVNode W
=G
->GraphList
[V
].FirstAdjV
;
for(;W
;W
=W
->Next
){
if(visited
[W
->AdjV
]==0){
DFS(G
,W
->AdjV
);
}
}
}
}
BFS
void BFS(LGraph G
,int V
)
{
if(visited
[V
]==0){
visited
[V
]=1;
printf(" %d",V
);
queue
[++rear
]=V
;
while(rear
>head
){
int T
=queue
[++head
];
PtrToAdjVNode N
=G
->GraphList
[T
].FirstAdjV
;
for(;N
;N
=N
->Next
){
if(visited
[N
->AdjV
]==0){
visited
[N
->AdjV
]=1;
printf(" %d",N
->AdjV
);
queue
[++rear
]=N
->AdjV
;
}
}
}
}
}
ListComponent：列出连通集同时控制输出格式
void ListComponent(LGraph G
,void (*Function
)(LGraph
,int) )
{
int i
=0;
for(i
=0;i
<G
->vertexNumber
;i
++){
if(visited
[i
]==1)continue;
printf("{");
Function(G
,i
);
printf(" }\n");
}
}
