用c语言写一个图的遍历,深度优先
时间: 2024-05-15 14:12:10 浏览: 16
以下是使用邻接矩阵表示图的深度优先遍历的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct {
int vertex[MAX_VERTEX_NUM]; // 顶点数组
int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vertex_num; // 顶点数
int arc_num; // 弧数
} Graph;
int visited[MAX_VERTEX_NUM] = {0}; // 标记是否已经访问
// 创建图
void CreateGraph(Graph *G) {
int i, j, k;
printf("请输入顶点数和弧数:");
scanf("%d %d", &G->vertex_num, &G->arc_num);
printf("请输入%d个顶点:", G->vertex_num);
for (i = 0; i < G->vertex_num; i++) {
scanf("%d", &G->vertex[i]);
}
for (i = 0; i < G->vertex_num; i++) {
for (j = 0; j < G->vertex_num; j++) {
G->arc[i][j] = 0; // 初始化为0
}
}
printf("请输入%d条弧,格式为:起点 终点\n", G->arc_num);
for (k = 0; k < G->arc_num; k++) {
scanf("%d %d", &i, &j);
G->arc[i][j] = 1;
G->arc[j][i] = 1; // 无向图需要反向也要赋值
}
}
// 深度优先遍历
void DFS(Graph G, int v) {
int i;
visited[v] = 1; // 标记顶点v已被访问
printf("%d ", G.vertex[v]); // 输出顶点v的值
for (i = 0; i < G.vertex_num; i++) {
if (G.arc[v][i] && !visited[i]) { // 顶点v和i之间有连通关系且i未被访问
DFS(G, i); // 递归访问顶点i
}
}
}
int main() {
Graph G;
CreateGraph(&G);
printf("深度优先遍历结果:");
DFS(G, 0); // 从第一个顶点开始遍历
printf("\n");
return 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)