c语言实现图的广度优先算法最短路径
时间: 2023-11-10 10:11:24 浏览: 40
广度优先搜索(BFS)可以用来求解无权图的最短路径。以下是用C语言实现BFS算法的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXV 1000 // 最大顶点数
#define INF 0x3f3f3f3f // 无穷大
typedef struct {
int adj[MAXV][MAXV]; // 邻接矩阵
int n; // 顶点数
int visited[MAXV]; // 标记是否已访问
int dist[MAXV]; // 记录最短距离
} Graph;
typedef struct {
int data[MAXV];
int front, rear;
} Queue;
// 初始化队列
void initQueue(Queue* q) {
q->front = q->rear = 0;
}
// 判断队列是否为空
int isEmpty(Queue* q) {
return q->front == q->rear;
}
// 入队
int enQueue(Queue* q, int x) {
if ((q->rear + 1) % MAXV == q->front) // 队列已满
return 0;
q->data[q->rear] = x;
q->rear = (q->rear + 1) % MAXV;
return 1;
}
// 出队
int deQueue(Queue* q, int* x) {
if (q->front == q->rear) // 队列为空
return 0;
*x = q->data[q->front];
q->front = (q->front + 1) % MAXV;
return 1;
}
// 初始化图
void initGraph(Graph* g, int n) {
g->n = n;
memset(g->adj, 0, sizeof(g->adj));
}
// 添加边
void addEdge(Graph* g, int u, int v) {
g->adj[u][v] = g->adj[v][u] = 1;
}
// BFS遍历
void bfs(Graph* g, int s) {
int i, v, u;
Queue q;
initQueue(&q);
memset(g->visited, 0, sizeof(g->visited));
memset(g->dist, INF, sizeof(g->dist));
g->visited[s] = 1;
g->dist[s] = 0;
enQueue(&q, s);
while (!isEmpty(&q)) {
deQueue(&q, &u);
for (v = 0; v < g->n; v++) {
if (g->adj[u][v] && !g->visited[v]) {
g->visited[v] = 1;
g->dist[v] = g->dist[u] + 1;
enQueue(&q, v);
}
}
}
}
// 输出最短路径
void printPath(Graph* g, int s, int t) {
if (s == t) {
printf("%d", s);
return;
}
if (g->dist[t] == INF) {
printf("无法到达!");
return;
}
int path[MAXV], i, j = 0;
path[j++] = t;
i = t;
while (i != s) {
for (int k = 0; k < g->n; k++) {
if (g->adj[i][k] && g->dist[k] == g->dist[i] - 1) {
path[j++] = k;
i = k;
break;
}
}
}
printf("%d", path[--j]);
for (i = j - 1; i >= 0; i--)
printf("->%d", path[i]);
}
int main() {
Graph g;
int n, m, s, t, u, v;
printf("请输入顶点数和边数:");
scanf("%d%d", &n, &m);
initGraph(&g, n);
printf("请输入边的起点和终点:\n");
for (int i = 0; i < m; i++) {
scanf("%d%d", &u, &v);
addEdge(&g, u, v);
}
printf("请输入起点和终点:");
scanf("%d%d", &s, &t);
bfs(&g, s);
printf("最短距离:%d\n最短路径:", g.dist[t]);
printPath(&g, s, t);
return 0;
}
```
该代码通过邻接矩阵实现图的存储,并使用BFS算法求解最短路径。其中,`initQueue`、`enQueue`、`deQueue`、`isEmpty`为队列相关操作,`initGraph`、`addEdge`为图的初始化和添加边操作,`bfs`为BFS算法的具体实现,`printPath`为输出最短路径的函数。