C语言完成图的深度优先遍历
时间: 2023-10-30 11:15:39 浏览: 37
C语言实现图的深度优先遍历需要使用图的邻接表存储结构和递归算法。具体步骤为:首先定义一个visited数组记录节点是否被访问过,将起始节点标记为已访问。然后从起始节点开始遍历其邻接表,对于未访问过的相邻节点进行递归调用,直到所有节点都被访问为止。实现代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20 // 图的最大节点数为20
typedef struct EdgeNode { // 边表节点
int adjvex; // 指向邻接点的下标
struct EdgeNode* next; // 指向下一个边表节点
} EdgeNode;
typedef struct VertexNode { // 顶点表节点
int data; // 顶点数据
EdgeNode* first_edge; // 指向第一个邻接点的指针
} VertexNode;
typedef struct { // 图结构体
VertexNode adjlist[MAX_VERTEX_NUM]; // 存放顶点表的数组
int vertex_num, edge_num; // 图的顶点数和边数
} Graph;
int visited[MAX_VERTEX_NUM] = {0}; // 记录节点是否被访问过
void create_graph(Graph* G) { // 建立图的邻接表存储结构
printf("请输入图的顶点数和边数:");
scanf("%d%d", &G->vertex_num, &G->edge_num);
for (int i = 0; i < G->vertex_num; i++) { // 初始化顶点表
G->adjlist[i].first_edge = NULL;
printf("请输入第%d个顶点的数据:", i + 1);
scanf("%d", &G->adjlist[i].data);
}
for (int i = 0; i < G->edge_num; i++) { // 建立边表
int u, v;
printf("请输入第%d条边的两个端点下标:", i + 1);
scanf("%d%d", &u, &v);
EdgeNode* e = (EdgeNode*)malloc(sizeof(EdgeNode));
e->adjvex = v;
e->next = G->adjlist[u].first_edge;
G->adjlist[u].first_edge = e;
// 无向图需要建立另一条反向边
e = (EdgeNode*)malloc(sizeof(EdgeNode));
e->adjvex = u;
e->next = G->adjlist[v].first_edge;
G->adjlist[v].first_edge = e;
}
}
void dfs(Graph* G, int i) { // 深度优先遍历
visited[i] = 1;
printf("%d ", G->adjlist[i].data);
EdgeNode* e = G->adjlist[i].first_edge;
while (e) { // 遍历相邻节点
int j = e->adjvex;
if (!visited[j]) {
dfs(G, j); // 递归调用
}
e = e->next;
}
}
int main() {
Graph G;
create_graph(&G);
printf("深度优先遍历的结果为:");
dfs(&G, 0);
printf("\n");
return 0;
}
```