邻接表存储图的广度优先遍历C语言代码实现
时间: 2023-11-05 07:08:37 浏览: 101
以下是邻接表存储图的广度优先遍历的C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20
// 邻接表中的边结构体
typedef struct ArcNode {
int adjvex; // 该边所连接的顶点的位置
struct ArcNode *next; // 指向下一条边的指针
} ArcNode;
// 邻接表中的顶点结构体
typedef struct VNode {
char data; // 顶点的数据域
ArcNode *firstarc; // 指向第一条依附该顶点的边的指针
} VNode, AdjList[MAX_VERTEX_NUM];
// 邻接表结构体
typedef struct {
AdjList vertices; // 邻接表
int vexnum, arcnum; // 图的顶点数和边数
} ALGraph;
// 初始化邻接表
void InitGraph(ALGraph *G) {
printf("请输入图的顶点数和边数:\n");
scanf("%d %d", &(G->vexnum), &(G->arcnum));
getchar(); // 吃掉换行符
printf("请输入各个顶点的名称(每个名称只能是一个字符):\n");
for (int i = 0; i < G->vexnum; i++) {
scanf("%c", &(G->vertices[i].data));
getchar(); // 吃掉换行符
G->vertices[i].firstarc = NULL;
}
printf("请输入各个边的信息(每个边包括两个顶点之间的信息):\n");
for (int k = 0; k < G->arcnum; k++) {
char v1, v2;
int i, j;
printf("请输入第%d条边所连接的两个顶点的名称:\n", k + 1);
scanf("%c %c", &v1, &v2);
getchar(); // 吃掉换行符
// 找到顶点在邻接表中的位置
for (i = 0; i < G->vexnum; i++) {
if (G->vertices[i].data == v1) {
break;
}
}
for (j = 0; j < G->vexnum; j++) {
if (G->vertices[j].data == v2) {
break;
}
}
// 创建一条边并将其插入到邻接表中
ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->next = G->vertices[i].firstarc;
G->vertices[i].firstarc = p;
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = i;
p->next = G->vertices[j].firstarc;
G->vertices[j].firstarc = p;
}
}
// 广度优先遍历
void BFS(ALGraph G, int v, int visited[]) {
int queue[MAX_VERTEX_NUM]; // 存放待遍历的顶点的队列
int front = 0, rear = 0; // 队头和队尾指针
printf("%c ", G.vertices[v].data);
visited[v] = 1;
queue[rear++] = v;
while (front != rear) {
int w = queue[front++]; // 取出队头元素
// 遍历该顶点的所有邻接点
for (ArcNode *p = G.vertices[w].firstarc; p != NULL; p = p->next) {
int u = p->adjvex;
if (visited[u] == 0) {
printf("%c ", G.vertices[u].data);
visited[u] = 1;
queue[rear++] = u;
}
}
}
}
int main() {
ALGraph G;
InitGraph(&G);
int visited[MAX_VERTEX_NUM] = {0}; // 初始化为0,表示所有顶点都未被访问
printf("广度优先遍历结果为:\n");
for (int i = 0; i < G.vexnum; i++) {
if (visited[i] == 0) {
BFS(G, i, visited);
}
}
return 0;
}
```
其中,`InitGraph`函数用于初始化邻接表;`BFS`函数用于进行广度优先遍历;`main`函数调用这两个函数,并打印出广度优先遍历的结果。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)