使用邻接矩阵在给定图中实现 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 已经被访问过，遍历停止。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

方法 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 遍历路径。

示例

Open Compiler
//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 程序，该程序使用基于邻接矩阵的表示法实现了深度优先搜索遍历。深度优先搜索是一种用于探索和分析图结构的强大算法。

更新于： 2023年8月9日

4K+ 次查看

开启您的 职业生涯

通过完成课程获得认证

立即开始
广告