C++ 使用邻接矩阵在给定图中实现深度优先搜索遍历

介绍

图论使我们能够研究和可视化对象或实体之间的关系。在当前计算机科学技术中，图遍历在探索和分析不同类型的数据结构中起着至关重要的作用。图的关键操作之一是遍历 – 访问所有顶点或节点，根据特定路径进行遍历。基于深度优先的DFS遍历允许我们在回溯和探索其他分支之前探索图的深度。在本文中，我们将介绍如何使用邻接矩阵表示在C语言中实现DFS遍历。

使用邻接矩阵的DFS遍历

图由两个主要组成部分组成，即代表实体或元素的顶点或节点，以及连接这些顶点的边，表示它们之间的关系。

表示加权或非加权图中顶点之间关系的唯一方法是使用邻接矩阵。它通常采用方阵的形式，其中行表示源顶点，列表示目标顶点，每个单元格包含有关相应对之间的边的存在或权重的信息。

示例

输入是使用图的四个顶点给出的一组特定元素。输入为：

并让图的起始顶点为2。图将从顶点“2”开始遍历。顶点“2”的相邻顶点显然是1和3。由于起始顶点是2，在遍历过程中不能再次访问它。在顶点2之后访问了顶点3，然后我们需要查看顶点3的相邻顶点，它们是1和2。顶点1和顶点2已经被访问过，遍历停止。

方法1：使用邻接矩阵作为输入的C程序，包含DFS遍历给定图

输入是用一些数字定义的，并使用for循环遍历邻接矩阵，并返回DFS遍历结果。

步骤

步骤1 ：程序通过定义一个常量MAX来表示给定图中的最大节点数，并初始化一个名为visited的数组来跟踪特定节点在遍历过程中是否已被访问。

步骤2 ：’dfs()’函数以一个表示图的方形邻接矩阵adjMatrix、顶点总数为’vCount’和一个起始顶点start作为参数。此函数在给定的图上执行递归深度优先搜索遍历。

步骤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;
}