【数据结构】3个例题带你理解图的遍历:深度优先搜索

简介: 【数据结构】3个例题带你理解图的遍历:深度优先搜索

1、定义


连通图的深度优先搜索遍历


从图中某个顶点v0出发,访问此顶点,然后依次从v0的各个未被访问的邻接点出发深度优先搜索遍历图,直到图中所有和v0有路径想通的顶点都被访问到。


非连通图处理方法:


访问完一个连通分量后,再在图中选一个未曾被访问的顶点作为始点继续进行深度优先搜索遍历。


练习1:已知一个图,若从顶点v1出发,写出它的按深度优先搜索进行遍历的遍历序列。

5adff998737c40c787fcfc4e1db5340e.png


优先深度搜索过程:


2dc2bdfd26404a35bb49247980791403.png


练习2:已知一个图,从顶点v0开始遍历,写出它的按深度优先搜索进行遍历的遍历序列。


69cb6e480f134ccd93d7767113b70204.png


 优先深度搜索过程:


注:深度搜索到末端,进行退回,去另一个分支进行深度搜索


bb77e0c647044195a014acb5ecf768e1.png


练习3:已知一个图的邻接表存储结构,如下图,若从顶点v1出发,分别写出有向图按深度优先搜索法进行遍历进行遍历得到的顶点序列。


8e72b0887fbb4bb0b0d0a0e664e4d8da.png


4ff65896f6744758bfbcb2c072e3ffc0.png


2、性能分析


深度优先搜索遍历图的时间复杂度和广度优先遍历相同,不同之处仅在于对顶点的访问顺序不同。


图的存储结构采用邻接矩阵时,时间复杂度为O(n2)。


图的存储结构采用邻接表时,时间复杂度为O(e)。


3)算法实现


算法核心:递归

public class DTraverser {
  private static boolean[] visited;// 访问标志数组
  // 对图G做深度优先遍历
  public static void DFSTraverse(IGraph G) throws Exception {
    visited = new boolean[G.getVexNum()];
    for (int v = 0; v < G.getVexNum(); v++)
      // 访问标志数组初始化
      visited[v] = false;
    for (int v = 0; v < G.getVexNum(); v++)
      if (!visited[v])// 对尚未访问的顶点调用DFS
        DFS(G, v);
  }
  // 从第v个顶点出发递归地深度优先遍历图G
  public static void DFS(IGraph G, int v) throws Exception {
    visited[v] = true;
    System.out.print(G.getVex(v).toString() + " ");// 访问第v个顶点
        //对顶点v的每一个未被访问的邻接点进行DFS操作
    for (int w = G.firstAdjVex(v); w >= 0; w = G.nextAdjVex(v, w))
      if (!visited[w])// 对v的尚未访问的邻接顶点w递归调用DFS
        DFS(G, w);
  }
  public static void main(String[] args) throws Exception {
    ALGraph G = GenerateGraph.generateALGraph();
    DTraverser.DFSTraverse(G);
  }
}



相关文章
|
2月前
|
算法 测试技术 定位技术
数据结构与算法——DFS(深度优先搜索)
数据结构与算法——DFS(深度优先搜索)
|
6月前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
|
2月前
|
存储 编译器 C++
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
|
2月前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
29 0
|
3月前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手,详细介绍了先序、中序和后序遍历方法,并探讨了如何构建二叉树及线索二叉树的概念。接着,文章讲解了树和森林的存储结构,特别是如何将树与森林转换为二叉树形式,以便利用二叉树的遍历方法。最后,讨论了树和森林的遍历算法,包括先根、后根和层次遍历。通过这些内容,读者可以全面了解二叉树及其相关概念。
|
4月前
【数据结构】遍历二叉树(递归思想)-->赋源码
【数据结构】遍历二叉树(递归思想)-->赋源码
54 4
|
5月前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
46 1
|
6月前
|
算法 C语言
【数据结构与算法 经典例题】使用队列实现栈(图文详解)
【数据结构与算法 经典例题】使用队列实现栈(图文详解)
|
6月前
|
算法 C语言 计算机视觉
【数据结构与算法 经典例题】括号匹配问题
【数据结构与算法 经典例题】括号匹配问题
|
6月前
|
算法
【数据结构与算法 经典例题】随机链表的复制(图文详解)
【数据结构与算法 经典例题】随机链表的复制(图文详解)