数据结构_广度优先搜索(C语言)_c语言广度优先搜索算法

广度优先搜索

1. 图文解析

广度优先搜索(Breadth First Search，BFS)，是图的一种遍历算法。

广度优先搜索的遍历过程类似于二叉树的层序遍历，，BFS遍历过程如下：

1. 访问图中的任意顶点《A》，并将该顶点入队
2. 若队列不为空，则出队获取出队顶点《A》
3. 遍历出队顶点《A》的相邻顶点《E， B》，访问其中未被访问的相邻顶点并入队
4. 循环第（2）（3）步骤，直到队列为空即可完成遍历。

例如访问到顶点《F》时，访问并入队其所有未被访问的顶点《G，C》

2. 源代码

#include<stdio.h>
#include<stdlib.h>
#define MaxVex 20

typedef int EdgeType;
typedef char VertexType;

typedef struct EdgeNode
{
    int adjvex;         
    EdgeType edgeData;  
    struct EdgeNode *next;
}EdgeNode, *EdgeList;

typedef struct
{
    VertexType vextexData; 
    EdgeList edgeList;       
}VertexNode, *VertexList;

// 邻接表结构
typedef struct
{
    VertexList vertexList; 
    int numVertexs, numEdges;     
}ALGraph;

// 队列结构
typedef struct
{
    int *base;          // 存储顶点下标
    int front, rear;    // 分别代表队头和队尾下标
}SqQueue;

void InitALGraph(ALGraph *G)
{

    G->numVertexs = 0;
    G->numEdges = 0;
    G->vertexList = (VertexNode *)malloc(MaxVex * sizeof(VertexNode));

    int i;
    for (i = 0; i < MaxVex; i++)
    {   
        G->vertexList[i].edgeList = (EdgeNode *)malloc(sizeof(EdgeNode));
        G->vertexList[i].edgeList->next = NULL;
    }
    printf("已初始化邻接表\n\n");
}

void CreateALGraph(ALGraph *G)
{
    printf("请输入顶点数和边数:");
    scanf("%d %d", &G->numVertexs, &G->numEdges);
    
    int i, j, k;
    EdgeType w;
    // 输入顶点数据
    for (i = 0; i < G->numVertexs; i++)
    {
        fflush(stdin);
        printf("请输入第%d个顶点数据:", i + 1);
        scanf("%c", &G->vertexList[i].vextexData);
    }
    // 输入边的权值
    for (k = 0; k < G->numEdges; k++)
    {
        printf("请输入边(vi, vj)上的顶点序号及权值:");
        scanf("%d %d %d", &i, &j, &w);

        EdgeNode *p1, *p2;
        p1 = (EdgeNode *)malloc(sizeof(EdgeNode));
        p2 = (EdgeNode *)malloc(sizeof(EdgeNode));

        // 链表头插法 插入 顶点（vi -> vj）的边
        p1->edgeData = w;
        p1->next = G->vertexList[i - 1].edgeList->next;
        G->vertexList[i - 1].edgeList->next = p1;
        p1->adjvex = j - 1; 
        
        // 对于无向图，同时还需要插入顶点（vj -> vi）的边
        p2->edgeData = w;
        p2->next = G->vertexList[j - 1].edgeList->next;
        G->vertexList[j - 1].edgeList->next = p2;
        p2->adjvex = i - 1;     
    }
    printf("已创建邻接表!\n\n");
}

void InitQueue(SqQueue *Q)      //初始化队列
{
    Q->base = (int *)malloc(MaxVex * sizeof(int));
    Q->front = Q->rear = 0;
}

void EnQueue(SqQueue *Q, int x) // 入队
{
    if ((Q->rear + 1) % MaxVex != Q->front)
    {
        Q->base[Q->rear] = x;
        Q->rear = (Q->rear + 1) % MaxVex;
    }
    
}

int DeQueue(SqQueue *Q)     // 出队
{
    int x;
    if (Q->front != Q->rear)
    {
        x = Q->base[Q->front];
        Q->front = (Q->front + 1) % MaxVex;
    }
    return x;
}

int isEmpty(SqQueue Q)      //判断队空
{
	return Q.front == Q.rear ? 1 : 0;
}

// 广度优先搜索
void BFS(ALGraph G, int *visited, int v)
{
    // 访问第一个结点， 并设置访问状态
    printf("%c ", G.vertexList[v].vextexData);
    visited[v] = 1;
    // 创建队列，入队第一个顶点下标
    SqQueue Q;
    InitQueue(&Q);
    EnQueue(&Q, v);
    
    int u;
    EdgeNode *p;
    while (!isEmpty(Q))
    {
        // 出队队头顶点下标u
        u = DeQueue(&Q);
        p = G.vertexList[u].edgeList;
    
        // 遍历该顶点相邻的所有顶点
        while (p->next)
        {
             p = p->next;
            // 访问未被访问的相邻顶点并入队
            if (!visited[p->adjvex])    
            {
                printf("%c ", G.vertexList[p->adjvex].vextexData);
                visited[p->adjvex] = 1;
                EnQueue(&Q, p->adjvex);
            }
        }
    }
}

void BFSTraverse(ALGraph G)
{
    int i, *visited;
    // 创建一个用于标识顶点是否被访问的数组
    visited = (int *)malloc(G.numVertexs * sizeof(int));
    // 初始化访问数组
    for (i = 0; i < G.numVertexs; i++)
    {
        visited[i] = 0;
    }
    printf("广度优先遍历:");
    for (i = 0; i < G.numVertexs; i++)
    {
        if (!visited[i])
        {
            BFS(G, visited, i);
        }
    }
    printf("\n");
}

int main()
{
    ALGraph G;
    InitALGraph(&G);
    CreateALGraph(&G);
    BFSTraverse(G);
    system("pause");
    return 0;
}
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185

3. 测试结果