用C语言以邻接矩阵或邻接表定义无向图,其中每个元素的数据类型为int。实现图的深度优先,打印所有的节点并给出注释。
时间: 2024-02-12 17:04:16 浏览: 92
数据结构(visualc++)用邻接矩阵表示给定无向图并进行深度遍历.doc
好的,以下是实现无向图深度优先遍历的 C 语言代码,其中邻接矩阵实现:
```c
#include <stdio.h>
#define MAX 100
int visited[MAX];
int vertexNum, edgeNum;
int matrix[MAX][MAX];
void DFS(int i) {
int j;
visited[i] = 1;
printf("%d ", i);
for(j = 0; j < vertexNum; j++) {
if(matrix[i][j] == 1 && visited[j] == 0) {
DFS(j);
}
}
}
int main() {
int i, v1, v2;
scanf("%d %d", &vertexNum, &edgeNum);
// 初始化邻接矩阵
for(i = 0; i < vertexNum; i++) {
visited[i] = 0;
for(j = 0; j < vertexNum; j++) {
matrix[i][j] = 0;
}
}
// 读入边
for(i = 0; i < edgeNum; i++) {
scanf("%d %d", &v1, &v2);
matrix[v1][v2] = matrix[v2][v1] = 1;
}
// 深度优先搜索
for(i = 0; i < vertexNum; i++) {
if(visited[i] == 0) {
DFS(i);
}
}
return 0;
}
```
其中,`visited` 数组用于记录每个节点是否被访问过,`matrix` 数组用于存储邻接矩阵,`DFS` 函数用于深度优先遍历图。
在主函数中,我们首先读入节点数和边数,然后初始化邻接矩阵并读入边。接着,我们遍历所有节点,对于未被访问过的节点,调用 `DFS` 函数进行深度优先遍历。
在 `DFS` 函数中,我们首先将当前节点标记为已访问,并打印节点编号。然后,我们遍历所有与当前节点相邻的节点,如果一个节点未被访问过,则递归调用 `DFS` 函数遍历该节点。
这样,我们就能深度优先遍历无向图,并打印所有的节点。
阅读全文