用C语言实现用广度优先遍历求无权图的单源最短路径,要求写出详细的注释
时间: 2024-05-06 15:18:12 浏览: 21
以下是用C语言实现用广度优先遍历求无权图的单源最短路径的代码,注释已经详细说明了每一步的操作:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
// 邻接表的定义
typedef struct node{
int vertex; // 顶点
struct node *next; // 指向下一个结点的指针
}Node;
typedef struct graph{
Node *adjList[MAX_VERTEX_NUM]; // 邻接表
int vertexNum; // 顶点数
}Graph;
// 初始化图
void initGraph(Graph *g, int vertexNum){
g->vertexNum = vertexNum;
int i;
for(i = 0; i < g->vertexNum; i++){
g->adjList[i] = NULL; // 所有结点初始化为空
}
}
// 添加边
void addEdge(Graph *g, int u, int v){
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = v;
newNode->next = g->adjList[u];
g->adjList[u] = newNode;
// 如果是无向图,还需要反向添加一条边
newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = u;
newNode->next = g->adjList[v];
g->adjList[v] = newNode;
}
// 广度优先遍历
void bfs(Graph *g, int start, int *dist){
int visited[MAX_VERTEX_NUM] = {0}; // 标记结点是否被访问过
int queue[MAX_VERTEX_NUM]; // 队列
int front = 0, rear = 0; // 队头和队尾指针
visited[start] = 1; // 标记起点已经访问过
queue[rear++] = start; // 将起点入队
dist[start] = 0; // 起点到自己的距离为0
while(front != rear){ // 队列不为空
int u = queue[front++]; // 取出队头元素
Node *p = g->adjList[u];
while(p != NULL){ // 遍历u的所有邻接点
int v = p->vertex;
if(!visited[v]){ // 如果v没有访问过
visited[v] = 1; // 标记v已经访问过
queue[rear++] = v; // 将v入队
dist[v] = dist[u] + 1; // 更新v到起点的距离
}
p = p->next; // 访问下一个邻接点
}
}
}
int main(){
Graph g;
initGraph(&g, 6); // 初始化一个有6个顶点的图
addEdge(&g, 0, 1);
addEdge(&g, 0, 2);
addEdge(&g, 1, 3);
addEdge(&g, 2, 3);
addEdge(&g, 2, 4);
addEdge(&g, 3, 5);
addEdge(&g, 4, 5);
int dist[MAX_VERTEX_NUM]; // 存储各个顶点到起点的距离
int start = 0; // 起点为0
bfs(&g, start, dist);
int i;
for(i = 0; i < g.vertexNum; i++){
printf("Vertex %d: distance = %d\n", i, dist[i]);
}
return 0;
}
```
在这个示例代码中,我们初始化了一个有6个顶点的无向图,并添加了一些边。我们通过广度优先遍历算法求出了从起点0到各个顶点的最短距离,并打印出来。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)