首页　>　文章列表　>　给定一个图，使用邻接矩阵实现深度优先搜索（DFS）遍历的C程序

给定一个图，使用邻接矩阵实现深度优先搜索（DFS）遍历的C程序

图邻接矩阵深度优先搜索(DFS)
399 2023-08-28

简介

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

使用邻接矩阵进行DFS遍历

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

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

示例

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

设图的起始顶点为 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;
}