用一个C语言文件完成图的深度和广度优先遍历,要求任意给定起始点,输出结果;并完成图的单源最短路径的算法,要求任意给定原点,输出结果。
时间: 2024-06-11 20:03:57 浏览: 120
掌握图的两种遍历算法深度优先搜索和广度优先搜索算.docx
由于题目中没有明确说明图的表示方式,我们假设图是以邻接矩阵的形式存储的。下面是完整的程序代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> // 用于定义bool类型
#define MAX_VERTICES 100 // 图中最多有100个顶点
typedef struct {
int edges[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
int num_vertices; // 图中顶点的个数
} Graph;
// 初始化图
void init_graph(Graph *g, int num_vertices) {
g->num_vertices = num_vertices;
for (int i = 0; i < num_vertices; i++) {
for (int j = 0; j < num_vertices; j++) {
g->edges[i][j] = 0;
}
}
}
// 向图中添加一条边
void add_edge(Graph *g, int src, int dest) {
g->edges[src][dest] = 1;
g->edges[dest][src] = 1; // 无向图,需要添加反向边
}
// 深度优先遍历
void dfs(Graph *g, int start, bool visited[]) {
visited[start] = true;
printf("%d ", start);
for (int i = 0; i < g->num_vertices; i++) {
if (g->edges[start][i] && !visited[i]) {
dfs(g, i, visited);
}
}
}
// 广度优先遍历
void bfs(Graph *g, int start) {
bool visited[MAX_VERTICES] = {false};
int queue[MAX_VERTICES];
int front = 0, rear = 0;
visited[start] = true;
printf("%d ", start);
queue[rear++] = start;
while (front < rear) {
int curr = queue[front++];
for (int i = 0; i < g->num_vertices; i++) {
if (g->edges[curr][i] && !visited[i]) {
visited[i] = true;
printf("%d ", i);
queue[rear++] = i;
}
}
}
}
// 单源最短路径算法
void dijkstra(Graph *g, int start) {
int dist[MAX_VERTICES];
bool visited[MAX_VERTICES] = {false};
for (int i = 0; i < g->num_vertices; i++) {
dist[i] = g->edges[start][i]; // 初始化距离数组
}
visited[start] = true;
for (int i = 1; i < g->num_vertices; i++) {
int min_dist = MAX_VERTICES;
int min_vertex = -1;
for (int j = 0; j < g->num_vertices; j++) {
if (!visited[j] && dist[j] < min_dist) {
min_dist = dist[j];
min_vertex = j;
}
}
visited[min_vertex] = true;
for (int j = 0; j < g->num_vertices; j++) {
if (!visited[j] && g->edges[min_vertex][j]) {
int new_dist = dist[min_vertex] + g->edges[min_vertex][j];
if (new_dist < dist[j]) {
dist[j] = new_dist;
}
}
}
}
printf("Vertex Distance from %d\n", start);
for (int i = 0; i < g->num_vertices; i++) {
printf("%6d %6d\n", i, dist[i]);
}
}
int main() {
Graph g;
init_graph(&g, 7);
add_edge(&g, 0, 1);
add_edge(&g, 0, 2);
add_edge(&g, 1, 3);
add_edge(&g, 2, 3);
add_edge(&g, 2, 4);
add_edge(&g, 3, 5);
add_edge(&g, 4, 5);
printf("深度优先遍历:");
bool visited[MAX_VERTICES] = {false};
dfs(&g, 0, visited);
printf("\n");
printf("广度优先遍历:");
bfs(&g, 0);
printf("\n");
printf("单源最短路径:\n");
dijkstra(&g, 0);
return 0;
}
```
程序中先定义了一个结构体`Graph`,用于存储图的相关信息。其中`edges`数组表示邻接矩阵,`num_vertices`表示图中顶点的个数。
`init_graph`函数用于初始化图,将所有边的权值设置为0。
`add_edge`函数用于向图中添加一条边。由于是无向图,需要同时添加两条边。
`dfs`函数实现了图的深度优先遍历。它接受三个参数:一个指向图的指针,起始顶点的编号和一个数组用于记录已经访问过的顶点。函数首先将起始顶点标记为已访问,并输出该顶点的编号。接着遍历该顶点的所有邻接点,如果邻接点未被访问过,则递归调用`dfs`函数。
`bfs`函数实现了图的广度优先遍历。它也接受三个参数:一个指向图的指针,起始顶点的编号和一个数组用于记录已经访问过的顶点。函数首先将起始顶点标记为已访问,并输出该顶点的编号。接着使用一个队列来存储待访问的顶点。将起始顶点入队后,不断取出队列头部的顶点,遍历该顶点的所有邻接点,如果邻接点未被访问过,则将其标记为已访问并入队。直到队列为空为止。
`dijkstra`函数实现了图的单源最短路径算法。它接受两个参数:一个指向图的指针和起始顶点的编号。函数首先初始化一个距离数组,将起始顶点到所有顶点的距离都初始化为该顶点到邻接点的距离。接着使用一个布尔型数组来记录哪些顶点已经被访问过,将起始顶点标记为已访问。然后在剩余的顶点中选择距离起始顶点最近的未访问顶点,标记为已访问。接着更新距离数组,计算起始顶点到所有未访问顶点的距离,并将距离数组中的值更新。不断重复上述步骤,直到所有顶点都被访问过为止。
在主函数中,我们定义了一个图,并向其中添加了若干条边。接着分别调用了深度优先遍历、广度优先遍历和单源最短路径算法,并输出结果。
阅读全文