图的深度优先遍历C代码
时间: 2023-10-30 17:09:28 浏览: 41
以下是图的深度优先遍历的C代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义图的最大节点数
#define MAX_NODE_NUM 100
// 定义邻接矩阵存储图
int graph[MAX_NODE_NUM][MAX_NODE_NUM];
// 定义节点访问标记数组
int visited[MAX_NODE_NUM];
// 定义深度优先遍历函数
void DFS(int node, int node_num)
{
int i;
// 标记节点已访问
visited[node] = 1;
// 输出当前节点
printf("%d ", node);
// 遍历当前节点的邻居节点
for (i = 0; i < node_num; i++)
{
if (graph[node][i] && !visited[i])
{
// 递归访问邻居节点
DFS(i, node_num);
}
}
}
int main()
{
int node_num, edge_num, i, j, start_node;
// 输入节点数和边数
printf("输入节点数和边数:");
scanf("%d%d", &node_num, &edge_num);
// 初始化邻接矩阵
for (i = 0; i < node_num; i++)
{
for (j = 0; j < node_num; j++)
{
graph[i][j] = 0;
}
}
// 输入边的信息
printf("输入边的信息(格式:起点 终点):\n");
for (i = 0; i < edge_num; i++)
{
int start, end;
scanf("%d%d", &start, &end);
graph[start][end] = 1;
graph[end][start] = 1; // 无向图需要加上这一行
}
// 输入起始节点
printf("输入起始节点:");
scanf("%d", &start_node);
// 深度优先遍历
printf("深度优先遍历结果:");
DFS(start_node, node_num);
return 0;
}
```
其中,visited数组用于标记节点是否已经被访问过,DFS函数用于递归遍历节点及其邻居节点。主函数中,先输入节点数和边数,然后根据输入边的信息构造邻接矩阵,最后输入起始节点,调用DFS函数进行深度优先遍历。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)