C语言实现图的遍历之深度优先搜索实例
时间: 2023-11-08 09:07:08 浏览: 54
好的,关于C语言实现图的遍历之深度优先搜索实例,以下是一个简单的代码示例,仅供参考:
```
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTEX_NUM 100 // 定义顶点的最大数量
bool visited[MAX_VERTEX_NUM]; // 定义顶点是否被访问的数组
typedef struct {
int vertices[MAX_VERTEX_NUM]; // 顶点数组
int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vertex_num; // 顶点数
int edge_num; // 边数
} Graph;
// 初始化一个没有边的图
void init_graph(Graph *graph, int vertex_num) {
int i, j;
graph->vertex_num = vertex_num;
graph->edge_num = 0;
for (i = 0; i < graph->vertex_num; i++) {
graph->vertices[i] = i;
for (j = 0; j < graph->vertex_num; j++) {
graph->edges[i][j] = 0;
}
}
}
// 添加一条边
void add_edge(Graph *graph, int start, int end) {
graph->edges[start][end] = 1;
graph->edges[end][start] = 1;
graph->edge_num++;
}
// 深度优先遍历
void dfs(Graph *graph, int vertex) {
int i;
visited[vertex] = true;
printf("%d ", vertex);
for (i = 0; i < graph->vertex_num; i++) {
if (graph->edges[vertex][i] == 1 && visited[i] == false) {
dfs(graph, i);
}
}
}
int main() {
Graph graph;
int i;
// 初始化一个有5个顶点,没有边的图
init_graph(&graph, 5);
// 添加边
add_edge(&graph, 0, 1);
add_edge(&graph, 0, 2);
add_edge(&graph, 1, 3);
add_edge(&graph, 2, 3);
add_edge(&graph, 2, 4);
add_edge(&graph, 3, 4);
// 初始化visited数组
for (i = 0; i < graph.vertex_num; i++) {
visited[i] = false;
}
// 从第一个顶点开始遍历
dfs(&graph, 0);
return 0;
}
```
以上就是一个简单的C语言实现图的深度优先遍历的代码实例,具体实现细节可以参照代码注释来理解。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![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)