简介
图论使我们能够研究和可视化对象或实体之间的关系。在当前的计算机科学技术中，图遍历在探索和分析不同类型的数据结构中起着至关重要的作用。在图上执行的关键操作之一是遍历 – 遵循特定路径访问所有顶点或节点。基于深度优先方法的 DFS 遍历允许我们在回溯和探索其他分支之前探索图的深度。在本文中，我们将使用 C 语言的邻接矩阵表示来实现 DFS 遍历。
使用邻接矩阵进行DFS遍历
图由两个主要组件组成，即表示实体或元素的顶点或节点，以及连接这些顶点的边，描述它们之间的关系。
表示加权或未加权图中顶点之间关系的唯一方法是通过邻接矩阵。它通常采用方阵的形式，其中行表示源顶点，列表示目标顶点，每个单元包含有关对应对之间的边存在或权重的信息。
示例
输入是使用图形的四个顶点通过一组特定元素给出的。输入是：
1 0 0 10 1 1 00 1 1 01 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#define MAX 100int visited[MAX];//dfs function is defined with three argumentsvoid 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 functionsint 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 程序。深度优先搜索是一种用于探索和分析图结构的强大算法。
以上就是给定一个图，使用邻接矩阵实现深度优先搜索（DFS）遍历的C程序的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1443941.html
微信扫一扫 
支付宝扫一扫 
