<pre><small><small>
给定一个有 N 个顶点和 E 条边的无向图，
请用 DFS 和 BFS 分别列出其所有的连通集。
假设顶点从 0 到 N−1 编号。
进行搜索时，假设我们总是从编号最小的顶点出发，
按编号递增的顺序访问邻接点。
输入格式:
输入第 1 行给出 2 个整数 N(0< N≤10) 和 E，
分别是图的顶点数和边数。
随后 E 行，每行给出一条边的两个端点。
每行中的数字之间用 1 空格分隔。
输出格式:
按照 "{ v​1​​ v​2​​ ... v​k​​ }" 的格式，
每行输出一个连通集。
先输出 DFS 的结果，
再输出 BFS 的结果。
</small></small></pre>
<pre><small><small>
输入样例:
8 6
0 7
0 1
2 0
4 1
2 4
3 5
</small></small></pre>
<pre><small><small>
输出样例:
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }
</small></small></pre>
<pre><small><small>

include <stdio.h>

include <stdlib.h>

define MaxVertexNum 10

define TRUE 1

define FALSE 0

typedef int Vertex; //用顶点下标表示顶点,为整型
typedef int WeightType; //边的权值设为整型
typedef char DataType; //顶点存储的数据类型设为字符型

typedef struct GNode *PtrToGNode;
struct GNode{
int Nv; //顶点数
int Ne; //边数
WeightType G[MaxVertexNum][MaxVertexNum];
DataType Data[MaxVertexNum];
};
typedef PtrToGNode MGraph; //以邻接矩阵存储的图类型

typedef struct ENode *PtrToENode;
struct ENode{
Vertex V1, V2; //有向边V1，V2
WeightType Weight; //权重
};
typedef PtrToENode Edge;

MGraph CreateGraph (int VertexNum);
void InsertEdge (MGraph Graph, Edge E);
MGraph BuildGraph(void);
int FirstAdjV(MGraph G, int V);
int NextAdjV(MGraph G, int V, int W);
void ListDFS(MGraph G);
void DFS(MGraph G, int V);
void ListBFS(MGraph G);
void BFS(MGraph G, int V);

int Visited[MaxVertexNum];

int main(){
MGraph G = BuildGraph();
ListDFS(G);
ListBFS(G);
return 0;
}

MGraph CreateGraph (int VertexNum){
Vertex V, W;
MGraph Graph;

Graph = (MGraph)malloc(sizeof(struct GNode));
Graph->Nv = VertexNum;
Graph->Ne = 0;

for(V=0; V<Graph->Nv; ++V){
    for(W=0; W<Graph->Nv; ++W){
        Graph->G[V][W] = 0; 
    } 
}

return Graph;

}

void InsertEdge (MGraph Graph, Edge E){
// Graph->G[E->V1][E->V2] = E->Weight;
// Graph->G[E->V2][E->V1] = E->Weight;
Graph->G[E->V1][E->V2] = 1;
Graph->G[E->V2][E->V1] = 1;
}

MGraph BuildGraph(void){
MGraph Graph;
Edge E;
Vertex V;
int Nv;
scanf("%d", &Nv);
Graph = CreateGraph(Nv);
scanf("%d", &(Graph->Ne));
if(Graph->Ne!=0){
E = (Edge)malloc(sizeof(struct ENode));
for(int i=0; i<Graph->Ne; ++i){
// scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
scanf("%d %d", &E->V1, &E->V2);
InsertEdge(Graph, E);
}
}
// for(V=0; V<Graph->Nv; ++V){
// scanf(" %c", &(Graph->Data[V]));
// }
return Graph;
}

int FirstAdjV(MGraph G, int V){
int i;
for(i=0; i<G->Nv; ++i){
if(G->G[V][i]==TRUE) return i;
}
if(i==(G->Nv-1)) return -1;
return -1;
}

int NextAdjV(MGraph G, int V, int W){
int i;
for(i=W+1; i<G->Nv; ++i){
if(G->G[V][i]==TRUE) return i;
}
if(i==(G->Nv-1)) return -1;
return -1;
}

void ListDFS(MGraph G){
for(int i=0; i<G->Nv; ++i) Visited[i] = FALSE;
for(int V=0; V<G->Nv; ++V){
if(!Visited[V]){
printf("{ ");
DFS(G, V);
printf("}\n");
}
}
}

void DFS(MGraph G, int V){
Vertex W;
Visited[V] = TRUE;
printf("%d ", V);
for(W=FirstAdjV(G,V); W!=-1; W=NextAdjV(G,V,W)){
if(!Visited[W]) DFS(G,W);
}
}

void ListBFS(MGraph G){
for(int i=0; i<G->Nv; ++i) Visited[i] = FALSE;
for(int V=0; V<G->Nv; ++V){
if(!Visited[V]){
printf("{ ");
BFS(G, V);
printf("}\n");
}
}
}

void BFS(MGraph G, int V){
Vertex W;
Visited[V] = TRUE;
printf("%d ", V);
Vertex Queue[MaxVertexNum];
for(int i=0; i< MaxVertexNum; ++i) Queue[i] = -1;
int front = 0, rear = 0;
Queue[rear] = V;
++rear;
while(front!=rear){
V = Queue[front];
++front;
for(W=FirstAdjV(G,V); W!=-1; W=NextAdjV(G,V,W)){
if(!Visited[W]){
Visited[W] = TRUE;
printf("%d ", W);
Queue[rear] = W;
++rear;
}
}
}
}
</small></small></pre>