Sillywa's Blog
0%

列出连通集

发表于 更新于 分类于

题目描述

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

输入格式

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

输出格式

按照”{ v1 v2 … vk }”的格式，每行输出一个连通集。先输出 DFS 的结果，再输出 BFS 的结果。

输入样例

1
2
3
4
5
6
7
8 6
0 7
0 1
2 0
4 1
2 4
3 5

输出样例

1
2
3
4
5
6
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }

C语言实现

首先我们需要分别定义图和边，这里我们使用邻接矩阵来存储图:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define MaxVertex 10        /* 定义最大顶点数 */

/* 使用邻接矩阵来存储图 */
typedef struct GNode* MGraph;
struct GNode{
    int Nv;                             /* 顶点数 */
    int Ne;                             /* 边数 */
    int data[MaxVertex][MaxVertex];     /* 邻接矩阵 */
};

/* 边的定义 */
typedef struct ENode* Edge;
struct ENode {
    int V1,V2;
};

然后我们需要三个方法，分别来创建一个有 Vertex 个顶点，但没有边的图，然后需要一个方法来将边插入图中，最后用一个方法来创建图。

1
2
3
4
5
6
7
/* 图的方法 */
MGraph CreateGraph(int Vertex);

void InsertEdge(MGraph Graph,Edge E);

MGraph BuildGraph();

图创建完成之后，我们需要分别实现 DFS 和 BFS，因此：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int Visited[MaxVertex];   /* 首先定义一个数组用于标记图中的每个顶点是否被访问 */
/* 由于 BFS 需要用到队列，因此我们还得定义队列及其方法 */
/* 队列的定义 */
typedef struct QNode* Queue;
struct QNode {
    int front;
    int rear;
    int MaxSize;
    int* data;
};

void DFS(MGraph Graph, int V);

void BFS(MGraph Graph, int V);

/* 队列的方法 */
Queue CreateQueue(int MaxSize);
void AddQ(Queue Q, int X);
int DeleteQ(Queue Q);
int IsEmpty(Queue Q);

接下来就依次实现这些方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

MGraph CreateGraph(int Vertex) {
    MGraph Graph = (MGraph)malloc(sizeof(struct GNode));
    Graph->Nv = Vertex;

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

    return Graph;

}

void InsertEdge(MGraph Graph,Edge E) {
    /* 插入无向边<V1,V2> */
    Graph->data[E->V1][E->V2] = 1;
    Graph->data[E->V2][E->V1] = 1;

}

MGraph BuildGraph() {
    int Nv;

    scanf("%d",&Nv);

    MGraph Graph = CreateGraph(Nv);

    scanf("%d",&Graph->Ne);

    if(Graph->Ne != 0) {

        Edge E = (Edge)malloc(sizeof(struct ENode));

        for(int i = 0;i < Graph->Ne;i++) {
            scanf("%d %d",&E->V1,&E->V2);

            InsertEdge(Graph, E);
        }
    }

    return Graph;
}

void DFS(MGraph Graph, int V){
    Visited[V] = 1;
    printf("%d ", V);

    /* 遍历所有节点 */
    for(int i = 0;i < Graph->Nv;i++) {
        /* 找到V和i的邻接点 ,如果该邻接点没有被访问，则访问之 */
        if(Graph->data[V][i] == 1  && Visited[i] == -1) {
            DFS(Graph, i);
        }
    }
}
void BFS(MGraph Graph, int V){

    Queue Q = CreateQueue(MaxVertex);

    Visited[V] = 1;


    /* 将顶点V入队 */
    AddQ(Q, V);

    while(!IsEmpty(Q)) {
        int W = DeleteQ(Q);
        printf("%d ", W);
        /* 找到W的所有邻接点，如果该邻接点没有被访问则将其入队 */
        for(int i = 0;i < Graph->Nv;i++) {
            if(Graph->data[W][i] == 1  && Visited[i] == -1) {
                Visited[i] = 1;
                AddQ(Q, i);
            }
        }
    }

}
Queue CreateQueue(int MaxSize) {
    Queue Q = (Queue)malloc(sizeof(struct QNode));
    Q->front = -1;
    Q->rear = -1;
    Q->MaxSize = MaxSize;
    Q->data = (int*)malloc(MaxSize*sizeof(int));
    return Q;
}
void AddQ(Queue Q, int X) {

    Q->rear = (Q->rear +1)%(Q->MaxSize);
    Q->data[Q->rear] = X;
}
int DeleteQ(Queue Q) {
    Q->front = (Q->front+1)%(Q->MaxSize);
    return Q->data[Q->front];
}
int IsEmpty(Queue Q) {
    return Q->front == Q->rear ? 1 : 0;
}

最后在 main 函数里面依次输出连通集即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

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

    /* 初始化Visited */
    for(int i = 0;i < Graph->Nv;i++) {
        Visited[i] = -1;
    }
    /* 当还有邻接点未访问时，访问之 */
    for(int V = 0;V < Graph->Nv; V++){
        if(Visited[V] == -1) {
            printf("{ ");
            DFS(Graph,V);
            printf("}");
            printf("\n");
        }

    }

    /* 初始化Visited */
    for(int i = 0;i < Graph->Nv;i++) {
        Visited[i] = -1;
    }
    for(int V = 0;V < Graph->Nv; V++){
        if(Visited[V] == -1) {
            printf("{ ");
            BFS(Graph,V);
            printf("}");
            printf("\n");
        }

    }

    return 0;
}