8.3.1深度优先搜索遍历
图的深度优先搜索遍历类似于二叉树的深度优先搜索遍历。其基本思想如下:假定以图中某个顶点Vi为出发点,首先访问出发点,然后选择一个Vi的未访问过的邻接点Vj,以Vj为新的出发点继续进行深度优先搜索,直至图中所有顶点都被访问过。显然,这是一个递归的搜索过程。
现以图8.15为例说明深度优先搜索过程。假定V1是出发点,首先访问V1。因V1有两个邻接点V2、V3均末被访问过,可以选择V2作为新的出发点,访问V2之后,再找V2的末访问过的邻接点。同V2邻接的有V1、V4和V5,其中V1已被访问过,而V4、V5尚未被访问过,可以选择V4作为新的出发点。重复上述搜索过程,继续依次访问V8、V5 。访问V5之后,由于与V5相邻的顶点均已被访问过,搜索退回到V8,访问V8的另一个邻接点V6。接下来依次访问V3和V7,最后得到的的顶点的访问序列为:V1 → V2 → V4 → V8 → V5 → V6 → V3 → V7。
package abc.graph; import java.util.ArrayList; import java.util.List; public class AlGraph { List<HeadNode> headNodes = new ArrayList<HeadNode>(); void addVertex(HeadNode node) { headNodes.add(node); } void addArc(HeadNode head, HeadNode tail) { if(head.firstArcNode == null) head.firstArcNode = new ArcNode(tail); else { ArcNode arcNode = head.firstArcNode; while (arcNode.nextArcNode != null) { arcNode = arcNode.nextArcNode; } arcNode.nextArcNode = new ArcNode(tail); } } public void DFSTraverse() { InitVisited(); DFS(headNodes.get(0)); } private void DFS(HeadNode node) { node.isVisited = true; System.out.print(node.name); System.out.print(" -> "); ArcNode arcNode = node.firstArcNode; while(arcNode != null) { if(arcNode.headNode.isVisited != true) DFS(arcNode.headNode); arcNode = arcNode.nextArcNode; } } private void InitVisited() { for(HeadNode node : headNodes) { node.isVisited = false; } } static AlGraph createAlGraph() { AlGraph alGraph = new AlGraph(); HeadNode V1 = new HeadNode("V1"); HeadNode V2 = new HeadNode("V2"); HeadNode V3 = new HeadNode("V3"); HeadNode V4 = new HeadNode("V4"); HeadNode V5 = new HeadNode("V5"); HeadNode V6 = new HeadNode("V6"); HeadNode V7 = new HeadNode("V7"); HeadNode V8 = new HeadNode("V8"); alGraph.addVertex(V1); alGraph.addVertex(V2); alGraph.addVertex(V3); alGraph.addVertex(V4); alGraph.addVertex(V5); alGraph.addVertex(V6); alGraph.addVertex(V7); alGraph.addVertex(V8); alGraph.addArc(V1, V2); alGraph.addArc(V1, V3); alGraph.addArc(V2, V1); alGraph.addArc(V2, V4); alGraph.addArc(V2, V5); alGraph.addArc(V3, V1); alGraph.addArc(V3, V6); alGraph.addArc(V3, V7); alGraph.addArc(V4, V2); alGraph.addArc(V4, V8); alGraph.addArc(V5, V2); alGraph.addArc(V5, V8); alGraph.addArc(V6, V3); alGraph.addArc(V6, V8); alGraph.addArc(V7, V3); alGraph.addArc(V7, V8); alGraph.addArc(V8, V4); alGraph.addArc(V8, V5); alGraph.addArc(V8, V6); alGraph.addArc(V8, V7); return alGraph; } void print() { for(HeadNode head : headNodes) { System.out.print(head.name); if(head.firstArcNode != null) { ArcNode arcNode = head.firstArcNode; System.out.print(" -> "); System.out.print(arcNode.headNode.name); while (arcNode.nextArcNode != null) { arcNode = arcNode.nextArcNode; System.out.print(" -> "); System.out.print(arcNode.headNode.name); } } System.out.println(); } } public static void main(String[] args) { AlGraph.createAlGraph().print(); System.out.println("\nAlGraph DFSTraverse !!"); AlGraph.createAlGraph().DFSTraverse(); } } class ArcNode { HeadNode headNode; ArcNode nextArcNode; public ArcNode(HeadNode tail) { this.headNode = tail; } } class HeadNode { String name; ArcNode firstArcNode; boolean isVisited; HeadNode(String name) { this.name = name; } }
输出 写道
V1 -> V2 -> V3
V2 -> V1 -> V4 -> V5
V3 -> V1 -> V6 -> V7
V4 -> V2 -> V8
V5 -> V2 -> V8
V6 -> V3 -> V8
V7 -> V3 -> V8
V8 -> V4 -> V5 -> V6 -> V7
AlGraph DFSTraverse !!
V1 -> V2 -> V4 -> V8 -> V5 -> V6 -> V3 -> V7 ->
V2 -> V1 -> V4 -> V5
V3 -> V1 -> V6 -> V7
V4 -> V2 -> V8
V5 -> V2 -> V8
V6 -> V3 -> V8
V7 -> V3 -> V8
V8 -> V4 -> V5 -> V6 -> V7
AlGraph DFSTraverse !!
V1 -> V2 -> V4 -> V8 -> V5 -> V6 -> V3 -> V7 ->
相关推荐
- **邻接表**:适用于稀疏图,即边的数量远小于顶点数量的平方。给定代码采用了邻接表的方式表示图。 ### 2. 邻接表表示法 邻接表是一种使用链表来表示图中各顶点的邻接关系的方法。每个顶点都由一个链表头结点...
根据给定文件的信息,我们可以总结出以下关于图的邻接表存储及遍历操作的关键知识点: ### 一、邻接表的基本概念 邻接表是一种用于表示图的存储结构,适用于稀疏图(即边的数量远小于顶点数量的平方)。它通过一...
### 图的存储结构:邻接表 ...通过邻接表,不仅可以方便地实现图的创建,还可以有效地支持深度优先遍历和广度优先遍历等图算法的应用。理解并掌握这些基础知识对于深入学习计算机科学中的图论及其应用具有重要意义。
1. 初始化图的邻接表,包括定义邻接表的边结点类型以及邻接表类型,并对邻接表进行初始化。 2. 根据所输入的相关信息,包括图的顶点数、边数、是否为有向,以及各条边的起点与终点序号,建立图的邻接表。 3. 分两种...
深度优先搜索(DFS,Depth-First Search)是一种用于遍历或搜索树或图的算法,尤其在图的遍历中有着广泛的应用。图的遍历是解决图的连通性问题、拓扑排序和求关键路径等算法的基础。深度优先搜索类似于树的先序遍历...
通过以上分析可以看出,这段代码不仅实现了图的基本存储结构——邻接表,还提供了两种重要的图遍历算法:深度优先搜索和广度优先搜索,以及一个队列辅助结构。这些基础知识对于理解和实现图的相关算法非常有帮助。
图的存储可以使用邻接矩阵表示法和邻接表表示法来实现,而图的遍历可以使用深度优先遍历和广度优先遍历来实现。通过对图的存储和遍历的研究,可以更好地理解和应用图结构。 此外,在图结构中,还有一些其他重要的...
根据给定文件的信息,我们可以提炼出以下关于使用邻接多重表实现图遍历的相关知识点: ### 一、邻接多重表的基本概念 邻接多重表是一种用于存储无向图的数据结构,它通过在每个顶点处维护一个指向与之相连的所有边...
邻接表和逆邻接表在图的遍历、搜索算法(如深度优先搜索DFS和广度优先搜索BFS)以及最短路径计算(如Dijkstra算法)等方面具有显著优势,因为它们避免了不必要的空间浪费,并且可以快速定位到相关的边。在实际应用中...
数据结构和算法Flash动画演示 顺序查找 顺序栈(4个存储空间) 顺序栈(8个存储空间) ...邻接表表示的图的深度优先遍历 拓扑排序 最短路径 克鲁斯卡尔算法构造最小生成树 B树的删除 B树的生长过程
根据图遍历顶点的顺序,可以绘制多重邻接表的示意图。 2. **有环判断**: 深度优先搜索(DFS)可以用来检测图中是否存在环。如果在遍历过程中发现某个节点的邻接节点已被访问且不是其父节点,那么存在回边,即存在...
本课程设计旨在让学生掌握《数据结构》课程中的相关知识,包括图的存储结构、队列的基本运算实现、邻接表的算法实现、图的广度优先搜索周游算法实现、图的深度优先搜索周游算法实现等。通过本次课程设计,学生将能够...
"判断任意两个顶点间是否存在路径" 本资源主要介绍了采用邻接表存储有...该函数通过遍历邻接表,检查了两点间是否存在路径,并将结果存储在 flag 变量中。如果 flag 变量为 1,则表示两点间存在路径,否则不存在路径。
本篇将详细探讨图的邻接矩阵和邻接表的建立,以及图的深度遍历方法。 首先,我们来了解什么是图。图是由顶点(或节点)和边组成的非线性数据结构。边表示顶点之间的关系,可以是有向的(箭头方向指示信息流向)或...
邻接表是图的一种高效存储方式,尤其适合稀疏图(边的数量远小于顶点数量的平方)。邻接表由两部分组成:顶点(Vnode 结构体)和边(ArcNode 结构体)。每个Vnode包含一个顶点的数据和指向其相邻顶点的链表...
2. **邻接表**:适用于稀疏图(即边的数量远小于顶点数量的平方)。邻接表使用一个数组加上链表的方式表示图。数组的每个元素是一个链表头结点,该链表包含所有与该顶点相邻的顶点。 #### 图的遍历算法 遍历图是指...
这两个函数用于遍历图的邻接表,找到指定顶点的相邻顶点。 在VC++环境中,通过上机调试线性表来实现这些功能,可以更好地理解和掌握图的动态构建过程。通过实际操作,学生能够深入理解图的存储结构、基本操作及其在...
//存放头结点的顺序表 int n,e; //图的顶点数和边数 } linkmap; int v[100]={0}; //深度优先遍历中标记已访问的信息 int dv[100]={0}; //广度优先遍历中标记已访问的信息 /*----------------定义建立图-----------...
本文详细介绍了如何使用C++实现图的邻接矩阵和邻接表表示,并展示了如何基于这两种表示实现图的各种基本操作,包括建立邻接表、非递归深度优先遍历、拓扑排序以及最短路径计算。通过对这些核心功能的理解和掌握,...
邻接表是一种高效的空间效率存储无向图和有向图的方法,尤其适合处理稀疏图(边的数量远小于顶点数量的平方)。 邻接表由两部分组成:vexlist(顶点列表)和adjlist(边的邻接节点列表)。在C语言中,可以定义如下...