06-图1 列出连通集（25 分）

给定一个有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 }

代码实现

C语言

#include<stdio.h>
#include<stdlib.h>
#define MaxVertexNum 11
typedef int Vertex;
Vertex Visited[MaxVertexNum];

typedef struct GNode *PtrToGNode;   // 图节点
struct GNode {
    int Nv;
    int Ne;
    int G[MaxVertexNum][MaxVertexNum];
};
typedef PtrToGNode MGraph;

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;
}

typedef struct ENode *PtrToENode;
struct ENode {  // 边节点
    Vertex V1, V2;
    int Weight;
};
typedef PtrToENode Edge;

void InsertEdge( MGraph Graph, Edge E ) {   // 给边赋权重
    Graph->G[E->V1][E->V2] = E->Weight;
    Graph->G[E->V2][E->V1] = E->Weight;
}

MGraph BuildGraph() {   // 根据题目建立图
    MGraph Graph;
    Edge E;
    Vertex V;
    int Nv, i;

    scanf("%d", &Nv);
    Graph = CreateGraph(Nv);
    scanf("%d", &(Graph->Ne));
    if ( Graph->Ne != 0 ) {
        E = (Edge)malloc(sizeof(struct ENode));
        for ( i=0; i<Graph->Ne; i++ ) {
            scanf("%d %d", &E->V1, &E->V2);
            E->Weight = 1;
            InsertEdge( Graph, E );
        }
    }
    return Graph;
}

void DFS ( MGraph Graph , Vertex V) {   // 深度遍历
    Visited[V] = 1;
    printf("%d ", V);
    for ( Vertex j=0; j<Graph->Nv; j++ ) {
        if ( Graph->G[V][j] == 1 && Visited[j] == 0 ) {
            DFS(Graph, j);
        }
    }   
}

struct {    // 创建队列节点
    Vertex Vert[MaxVertexNum];
    int rear;
    int front;
} Q;

void CreateQ() {    // 初始化队列
    Q.rear = 0;
    Q.front = 0;
    for ( int i=0; i<MaxVertexNum; i++ ) {
        Q.Vert[i] = -1;
    }
}

void AddQ(Vertex V) {   // 队列push节点
    if ( (Q.rear+1) % MaxVertexNum == Q.front ) {
        printf("The queue is full.\n");
    } else {
        Q.rear = (Q.rear+1) % MaxVertexNum;
        Q.Vert[Q.rear] = V;
    }
}

Vertex DelQ() { // 队列pop节点
    if ( Q.front == Q.rear ) {
        printf("The queue is empty.\n");
        return -1;
    } else {
        Q.front = (Q.front+1) % MaxVertexNum;
        return Q.Vert[Q.front];
    }
}


void BFS ( MGraph Graph , Vertex V ) {  // 广度遍历
    Vertex T;
    AddQ(V);
    Visited[V] = 1;
    while ( Q.front != Q.rear ) {
        T = DelQ();
        printf("%d ", T);
        for ( Vertex j=0; j<Graph->Nv; j++ ) {
            if ( Graph->G[T][j] == 1 && Visited[j] == 0 ) {
                AddQ(j);
                Visited[j] = 1;
            }
        }
    }
}

void InitVisit() {  // 标记节点是否被访问过。此为初始化。
    for ( int i=0; i<MaxVertexNum; i++ ) Visited[i] = 0;
}

int main() {
    MGraph Graph;
    Graph = BuildGraph();

    Vertex V = 0;
    InitVisit();
    for ( V=0; V<Graph->Nv; V++ ) {
        if ( Visited[V] == 0 ) {
            printf("{ ");
            DFS ( Graph, V);
            printf("}\n");
        }
    }

    CreateQ();
    InitVisit();
    for ( V=0; V<Graph->Nv; V++ ) {
        if ( Visited[V] == 0 ) {
            printf("{ ");
            BFS ( Graph, V);
            printf("}\n");
        }
    }

    return 0;
}