c 语言 实现图的深度优先遍历
时间: 2023-10-30 11:15:14 浏览: 31
图的深度优先遍历可以用递归或栈实现。以下是使用递归实现深度优先遍历的 C 语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点个数
typedef struct {
int vertex; // 顶点编号
int visited; // 是否被访问过
} Vertex;
typedef struct {
Vertex vertices[MAX_VERTEX_NUM]; // 顶点数组
int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vertex_num; // 顶点个数
int edge_num; // 边个数
} Graph;
void dfs(Graph *graph, int vertex) {
graph->vertices[vertex].visited = 1; // 标记为已访问
printf("%d ", vertex); // 输出顶点编号
for (int i = 0; i < graph->vertex_num; i++) {
if (graph->edges[vertex][i] == 1 && graph->vertices[i].visited == 0) {
dfs(graph, i); // 递归访问相邻未访问过的顶点
}
}
}
int main() {
Graph graph = {
.vertices = {
{0, 0}, {1, 0}, {2, 0}, {3, 0}, {4, 0},
},
.edges = {
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 1},
{1, 0, 0, 1, 0},
{0, 1, 1, 0, 1},
{0, 1, 0, 1, 0},
},
.vertex_num = 5,
.edge_num = 7,
};
dfs(&graph, 0); // 从顶点0出发进行深度优先遍历
return 0;
}
```
代码中使用了邻接矩阵来表示图,`edges[i][j]` 表示顶点 `i` 和顶点 `j` 是否有边相连。`dfs` 函数用来实现递归遍历相邻未访问过的顶点,输出顶点编号,并标记为已访问。在 `main` 函数中,从顶点0出发进行深度优先遍历。