c语言使用广度优先遍历实现无向图的最短路径
时间: 2023-11-25 15:08:21 浏览: 109
实现无向图的最短路径可以使用BFS(广度优先搜索)算法。以下是使用C语言实现BFS算法的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
typedef struct ArcNode {
int adjvex; // 邻接点的下标
struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;
typedef struct VNode {
int data; // 顶点的数据
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices; // 邻接表
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
void BFS(ALGraph G, int start, int end) {
int visited[G.vexnum]; // 标记顶点是否被访问过
int queue[MAX_VERTEX_NUM]; // 存放待遍历的顶点
int front = 0, rear = 0; // 队列的头尾指针
int path[G.vexnum]; // 存放路径
int i, j, k, flag = 0;
ArcNode *p;
for (i = 0; i < G.vexnum; i++) {
visited[i] = 0;
path[i] = -1;
}
visited[start] = 1;
queue[rear++] = start;
while (front < rear) {
i = queue[front++];
p = G.vertices[i].firstarc;
while (p != NULL) {
j = p->adjvex;
if (!visited[j]) {
visited[j] = 1;
path[j] = i; // 记录路径上的前驱结点
queue[rear++] = j;
}
if (j == end) {
flag = 1;
break;
}
p = p->nextarc;
}
if (flag) {
break;
}
}
if (path[end] == -1) {
printf("No path from %d to %d\n", start, end);
} else {
printf("Shortest path from %d to %d: ", start, end);
k = end;
while (k != start) {
printf("%d <- ", k);
k = path[k];
}
printf("%d\n", start);
}
}
int main() {
int i, j, k, n, m, u, v;
ALGraph G;
ArcNode *p;
printf("Enter the number of vertices and edges: ");
scanf("%d %d", &n, &m);
G.vexnum = n;
G.arcnum = m;
for (i = 0; i < n; i++) {
G.vertices[i].data = i; // 顶点编号
G.vertices[i].firstarc = NULL; // 初始化第一个邻接点指针
}
printf("Enter the edges:\n");
for (k = 0; k < m; k++) {
scanf("%d %d", &u, &v);
p = (ArcNode *) malloc(sizeof(ArcNode));
p->adjvex = v;
p->nextarc = G.vertices[u].firstarc; // 将新边插入到邻接点链表的头部
G.vertices[u].firstarc = p;
p = (ArcNode *) malloc(sizeof(ArcNode));
p->adjvex = u;
p->nextarc = G.vertices[v].firstarc;
G.vertices[v].firstarc = p;
}
printf("Enter the start and end vertices: ");
scanf("%d %d", &u, &v);
BFS(G, u, v);
return 0;
}
```
这段代码实现了BFS算法,其中`ALGraph`结构体表示无向图,`BFS`函数用于搜索无向图中的最短路径。在`main`函数中,先读入图的顶点数和边数,再读入每条边的起点和终点,最后读入起点和终点,并调用`BFS`函数搜索最短路径。
阅读全文