图的深度优先遍历c语言实现
时间: 2023-10-16 09:14:30 浏览: 39
以下是图的深度优先遍历的 C 语言实现:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
int adj[MAX_VERTICES][MAX_VERTICES];
bool visited[MAX_VERTICES];
void dfs(int v, int num_vertices) {
visited[v] = true;
printf("%d ", v);
for (int i = 0; i < num_vertices; ++i) {
if (adj[v][i] && !visited[i]) {
dfs(i, num_vertices);
}
}
}
int main() {
int num_vertices, num_edges;
printf("Enter the number of vertices: ");
scanf("%d", &num_vertices);
printf("Enter the number of edges: ");
scanf("%d", &num_edges);
// initialize the adjacency matrix
for (int i = 0; i < num_vertices; ++i) {
for (int j = 0; j < num_vertices; ++j) {
adj[i][j] = 0;
}
}
// read in the edges
for (int i = 0; i < num_edges; ++i) {
int u, v;
printf("Enter edge %d: ", i + 1);
scanf("%d %d", &u, &v);
adj[u][v] = adj[v][u] = 1;
}
// start DFS from vertex 0
printf("DFS traversal starting from vertex 0: ");
dfs(0, num_vertices);
return 0;
}
```
该代码段通过邻接矩阵存储图,并使用一个布尔数组 `visited` 来跟踪已访问过的顶点。`dfs()` 函数从指定的顶点开始递归遍历,并对访问的每个顶点进行打印和标记。在主函数中,用户输入图的顶点和边数以及每个边的两个端点。然后,从顶点0开始进行深度优先遍历并打印结果。