用c语言实现邻接矩阵深度优先遍历
时间: 2023-07-24 10:04:40 浏览: 71
邻接矩阵深度优先遍历是一种图遍历算法,它可以遍历一个图中所有的节点,并且保证不会重复遍历同一个节点。下面是一个用C语言实现邻接矩阵深度优先遍历的例子:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
int visited[MAX_VERTICES];
int adjacency_matrix[MAX_VERTICES][MAX_VERTICES];
int vertices_count;
void dfs(int vertex) {
int i;
printf("%d ", vertex);
visited[vertex] = 1;
for (i = 0; i < vertices_count; i++) {
if (adjacency_matrix[vertex][i] && !visited[i]) {
dfs(i);
}
}
}
int main() {
int i, j;
scanf("%d", &vertices_count);
for (i = 0; i < vertices_count; i++) {
visited[i] = 0;
for (j = 0; j < vertices_count; j++) {
adjacency_matrix[i][j] = 0;
}
}
for (i = 0; i < vertices_count; i++) {
for (j = 0; j < vertices_count; j++) {
scanf("%d", &adjacency_matrix[i][j]);
}
}
dfs(0);
return 0;
}
```
在这个程序中,我们首先定义了一个 `visited` 数组,用于记录每个节点是否被访问过。然后定义了一个邻接矩阵 `adjacency_matrix`,用于存储图的边信息。接着我们定义了一个 `dfs` 函数,用于进行深度优先遍历。最后在 `main` 函数中,我们读入了图的节点数量和邻接矩阵,然后调用 `dfs` 函数进行遍历。
在 `dfs` 函数中,我们首先输出当前节点的编号,并将其标记为已访问。然后遍历与该节点相邻的所有节点,如果该节点未被访问过,则递归调用 `dfs` 函数进行遍历。这样就可以完成邻接矩阵深度优先遍历了。