使用给定图中的邻接矩阵实现 DFS 遍历的 C 程序
简介
图论使我们能够研究和可视化对象或实体之间的关系。在当前的计算机科学技术中，图遍历在探索和分析不同类型的数据结构中起着至关重要的作用。在图上执行的关键操作之一是遍历 - 访问所有顶点或节点，遵循特定路径。基于深度优先方法的 DFS 遍历使我们能够在回溯和探索其他分支之前探索图的深度。在本文中，我们将涉及使用 C 中的邻接矩阵表示实现 DFS 遍历。
使用邻接矩阵的 DFS 遍历
图由两个主要组件组成，即表示实体或元素的顶点或节点，以及连接这些顶点的边，描述它们之间的关系。
表示加权或非加权图中顶点之间关系的唯一方法是使用邻接矩阵。它通常采用方阵的形式，其中行表示源顶点，列表示目标顶点，每个单元格包含有关相应对之间的边存在或权重的信息。
示例
输入由使用图的四个顶点的一组特定元素给出。输入为:
1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
设图的起始顶点为 2。图将从顶点"2"开始遍历。顶点"2"的相邻顶点显然是 1 和 3。由于起始顶点是 2，因此在遍历过程中不能再次访问它。在顶点 2 之后访问了顶点 3，那么我们需要查看顶点 3 的邻接顶点，即 1 和 2。顶点 1 和顶点 2 已被访问，遍历停止。
方法 1:包含使用邻接矩阵作为给定图中输入的 DFS 遍历的 C 程序
输入用某些数字定义，使用 for 循环，它将遍历邻接矩阵并返回 DFS 遍历。
算法
步骤 1:程序首先定义一个常量 `MAX` 来表示给定图中的最大节点数，并初始化一个名为 `visited` 的数组，以跟踪在遍历过程中是否访问过特定节点。
步骤 2:'dfs()' 函数采用参数为一个方形邻接矩阵作为"adjMatrix"，表示我们的图，顶点总数为"vCount"，起始顶点为"start"。此函数对给定的图执行递归深度优先搜索遍历。
步骤 3:在 'dfs()' 函数中，我们使用基于布尔值的 'visited[]' 数组中的索引将每个当前处理的顶点标记为"已访问"，并相应地打印其值。
步骤 4:'dfs()' 中的循环递归遍历当前节点的所有未访问邻居，直到没有可能获得与其连接的顶点。
步骤 5:在 main() 中，我们使用嵌套循环从用户那里读取输入，例如顶点数量为 'vCount' 及其相应的连接到邻接矩阵中。
步骤 6:然后，我们在初始化 'visited[]' 的每个元素之前提示用户输入他们想要的起始顶点数组为零(因为尚未访问任何节点)。
步骤 7:最后，程序使用适当的参数调用"dfs()"函数来启动深度优先搜索遍历，并打印出 DFS 遍历路径。
示例
//包含所需的头文件
#include<stdio.h>
#define MAX 100
int accessed[MAX];
//dfs 函数使用三个参数定义
void dfs(int adjMatrix[][MAX], int vCount, int start) {
visited[start] = 1;
printf("%d ", start);
for(int i=0; i<vCount; i++) {
if(adjMatrix[start][i] && !visited[i]) {
dfs(adjMatrix,vCount,i);
}
}
}
//main函数用于实现上述功能
int main() {
int adjMatrix[MAX][MAX];
int vCount;
// 为变量赋值为4
vCount = 4;
// 直接为邻接矩阵赋值，与上面的例子相同
adjMatrix[0][0] = 1;
adjMatrix[0][1] = 0;
adjMatrix[0][2] = 0;
adjMatrix[0][3] = 1;
adjMatrix[1][0] = 0;
adjMatrix[1][1] = 1;
adjMatrix[1][2] = 1;
adjMatrix[1][3] = 0;
adjMatrix[2][0] = 0;
adjMatrix[2][1] = 1;
adjMatrix[2][2] = 1;
adjMatrix[2][3] = 0;
adjMatrix[3][0] = 1;
adjMatrix[3][1] = 0;
adjMatrix[3][2] = 0;
adjMatrix[3][3] = 1;
//将起始变量声明为整数数据类型，稍后赋值为 2
int start;
// 直接赋值起始顶点
start = 2;
for(int i = 0; i < MAX; ++i) {
visited[i] = 0;
}
printf("\nDFS Traversal: ");
dfs(adjMatrix, vCount, start);
return 0;
}
输出
DFS Traversal: 2 1
结论
通过使用邻接矩阵作为图的表示，我们可以有效地对大型或复杂的数据集执行 DFS。在本文中，我们详细解释了这一点，并给出了一个使用基于邻接矩阵的表示实现深度优先搜索遍历的 C 程序。深度优先搜索是一种用于探索和分析图结构的强大算法。
