简介
图论使我们能够研究和可视化对象或实体之间的关系。在当前的计算机科学技术中，图遍历在探索和分析不同类型的数据结构中起着至关重要的作用。在图上执行的关键操作之一是遍历 - 遵循特定路径访问所有顶点或节点。基于深度优先方法的 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，因此在遍历过程中不能再次访问它。顶点3在顶点2之后被访问，那么我们需要查看顶点3的邻接顶点1和2。顶点1和顶点2已经被访问过，遍历停止。
方法 1：C 程序，包括使用邻接矩阵作为给定图中的输入进行 DFS 遍历
输入是用某些数字定义的，并使用 for 循环它将迭代邻接矩阵并返回 DFS 遍历。
算法
第 1 步：程序首先定义一个常量“MAX”来表示给定图中的最大节点数，并初始化一个名为“visited”的数组来跟踪特定节点是否存在遍历期间已被访问过。
第 2 步：“dfs()”函数将一个方形邻接矩阵作为参数，“adjMatrix”代表我们的图，顶点总数为“vCount”，起始顶点为`开始`。该函数对给定图执行递归深度优先搜索遍历。
第 3 步：在“dfs()”函数中，我们使用基于布尔值的“visited[]”数组中的索引将每个当前处理的顶点标记为“已访问”，并相应地打印其值。
第 4 步：“dfs()”内部的循环递归地迭代当前节点的所有未访问的邻居，直到不可能获得与其连接的顶点。
第5步：在main()中，我们使用嵌套循环读取用户的输入，例如“vCount”的顶点数量及其相应的连接到邻接矩阵中。
第 6 步：然后，我们提示用户输入所需的起始顶点，然后将“visited[]”数组的每个元素初始化为零（因为尚未访问任何节点）。
第7步：最后，程序使用适当的参数调用“dfs()”函数来启动深度优先搜索遍历，并打印出DFS遍历路径。
示例
//Including the required header files
#include<stdio.h>
#define MAX 100
int visited[MAX];
//dfs function is defined with three arguments
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 function is used to implement the above functions
int main() {
int adjMatrix[MAX][MAX];
int vCount;
// Assigning the variable with value of 4
vCount = 4;
// Assigning the adjacency matrix directly same the example given above
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;
//Declaring the start variable as integer data type and later assigned with a value of 2
int start;
// Assigning the starting vertex directly
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 程序。深度优先搜索是一种用于探索和分析图结构的强大算法。
