dfs算法c语言
时间: 2023-07-16 15:16:49 浏览: 52
以下是DFS算法的C语言实现:
```c
#include <stdio.h>
#define MAX_VERTICES 50
int visited[MAX_VERTICES];
int adj_matrix[MAX_VERTICES][MAX_VERTICES];
int n;
void dfs(int vertex);
int main() {
int i, j;
printf("Enter the number of vertices: ");
scanf("%d", &n);
printf("Enter the adjacency matrix:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &adj_matrix[i][j]);
}
}
// Initialize visited array to 0
for (i = 0; i < n; i++) {
visited[i] = 0;
}
printf("DFS Traversal: ");
dfs(0); // Start from vertex 0
printf("\n");
return 0;
}
void dfs(int vertex) {
int i;
visited[vertex] = 1;
printf("%d ", vertex);
for (i = 0; i < n; i++) {
if (adj_matrix[vertex][i] && !visited[i]) {
dfs(i);
}
}
}
```
这个实现使用邻接矩阵表示图,并在DFS遍历中使用递归。`visited`数组用于跟踪哪些顶点已经被访问过。首先将起始顶点标记为已访问,并打印其值。然后,对于每个与该顶点相邻且未被访问的顶点,递归调用`dfs()`函数。