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 AlGraph3 { List<Node> vertexes = new ArrayList<Node>(); void addVertex(Node vertex) { vertexes.add(vertex); } void addArc(Node head, Node tail) { head.addArc(tail); } public void DFSTraverse() { InitVisited(); DFS(vertexes.get(0)); } private void DFS(Node node) { node.isVisited = true; System.out.print(node.name); System.out.print(" -> "); for(Node tmp : node.adjs) { if(tmp.isVisited != true) DFS(tmp); } } private void InitVisited() { for(Node node : vertexes) { node.isVisited = false; } } static AlGraph3 createAlGraph() { AlGraph3 alGraph = new AlGraph3(); Node V1 = new Node("V1"); Node V2 = new Node("V2"); Node V3 = new Node("V3"); Node V4 = new Node("V4"); Node V5 = new Node("V5"); Node V6 = new Node("V6"); Node V7 = new Node("V7"); Node V8 = new Node("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(Node head : vertexes) { System.out.print(head.name); for(Node arc : head.adjs) { System.out.print(" -> "); System.out.print(arc.name); } System.out.println(); } } public static void main(String[] args) { AlGraph3.createAlGraph().print(); System.out.println("\nAlGraph DFSTraverse !!"); AlGraph3.createAlGraph().DFSTraverse(); } } class Node { String name; boolean isVisited; List<Node> adjs = new ArrayList<Node>(); Node(String name) { this.name = name; } void addArc(Node node) { adjs.add(node); } }
输出结果 写道
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 ->
相关推荐
在这个程序设计任务中,我们需要实现的是连通无向图的深度优先遍历(DFS)和广度优先遍历(BFS),这两种遍历方法是图算法的基础。无向图指的是图中的边没有方向,即任意两个节点之间可以双向连接。 1. **邻接表和...
"建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历" 本文档主要介绍了图的存储方式,包括邻接矩阵和邻接表两种存储方法,并在此基础上实现了图的深度优先遍历和广度优先遍历。 一、图...
以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 [实现提示] 设图的结点不超过30个,每个结点用一个编号表示(如果...
**深度优先遍历**是一种从某个顶点出发,尽可能深入地搜索图中的路径直到无法前进为止,然后回溯的遍历方式。 给定的代码实现了一个DFS算法: 1. 初始化一个布尔数组`visited`记录每个顶点是否被访问过。 2. 对于图...
### 图的深度优先遍历与广度优先遍历 #### 一、引言 图是一种非线性数据结构,由顶点集和边集组成。其中顶点表示实体,而边则表示实体之间的关系。图的遍历是图的重要操作之一,它用于系统地访问图中的所有顶点。图...
实现图的深度和广度优先搜索 .../* 从初始点v出发深度优先遍历邻接表GL表示的图 */ void DfsAdjlist(AdjList GL,int v) /*从初始点v出发广度优先遍历邻接表GL表示的图*/ void BfsAdjlist(AdjList GL,int v)
以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 注: 1.代码共182行。 2.代码经过多次编译运行,无错误。
图的遍历是图论中的基础操作,主要包含深度优先搜索(DFS, Depth First Search)和广度优先搜索(BFS, Breadth First Search)两种方法。这两种遍历方式在计算机科学中有着广泛的应用,例如在搜索算法、路径查找、网络...
根据给定文件的信息,我们可以总结出以下关于图的邻接表存储及遍历操作的关键知识点: ### 一、邻接表的基本概念 邻接表是一种用于表示图的存储结构,适用于稀疏图(即边的数量远小于顶点数量的平方)。它通过一...
### 图的存储结构:邻接表 ...通过邻接表,不仅可以方便地实现图的创建,还可以有效地支持深度优先遍历和广度优先遍历等图算法的应用。理解并掌握这些基础知识对于深入学习计算机科学中的图论及其应用具有重要意义。
### C语言实现无向图的深度优先遍历 #### 一、无向图与深度优先遍历概述 在计算机科学中,无向图是一种数据结构,由一系列节点(顶点)以及连接这些节点的边组成。如果边没有方向性,则称这样的图为无向图。在图论...
以邻接表为存储结构,实现创建图、销毁图、查找顶点、获取顶点值、顶点赋值、获得第一邻接点、获得下一邻接点、插入顶点、删除顶点、插入弧、删除弧、深度优先搜索遍历、广深度优先搜索遍历等操作 注: 1.系统设计 2...
并输出之(2)建立如图所示的有向图G的邻接表,并输出之(3)输出如图所示的有向图G从顶点0开始的深度优先遍历序列(4)输出如图所示的有向图G从顶点0开始的广度优先遍历序列(5)销毁图G的邻接表
邻接表是一种链式的存储结构,在邻接表中,对图中每个顶点建立一个单链表,第 i 个单链表中的结点表示依附于顶点 Vi 的边(对有向图是以顶点 Vi 为尾的弧)。 图的深度遍历可以递归定义,首先访问出发点 v,并将其...
编写在邻接矩阵或邻接表存储结构下,带权有向图基本操作的实现函数(如初始化图、在图中插入一个结点、在图中插入一条边、在图中寻找序号为v的结点的第一个邻接结点、在图中寻找序号为v1结点的邻接结点v2的下一个...
邻接表表示的图的深度优先搜索和广度优先搜索程序 这篇文章介绍了使用邻接表表示的图的深度优先搜索和广度优先搜索程序,旨在帮助读者理解图的深度优先搜索和广度优先搜索算法的实现。 首先,文章定义了图的邻接表...
深度优先搜索(DFS,Depth-First Search)是一种用于遍历或搜索树或图的算法,尤其在图的遍历中有着广泛的应用。图的遍历是解决图的连通性问题、拓扑排序和求关键路径等算法的基础。深度优先搜索类似于树的先序遍历...
通过以上分析可以看出,这段代码不仅实现了图的基本存储结构——邻接表,还提供了两种重要的图遍历算法:深度优先搜索和广度优先搜索,以及一个队列辅助结构。这些基础知识对于理解和实现图的相关算法非常有帮助。
邻接表是通过链式结构来存储图的边或弧的一种方法,对于一个包含n个顶点的图,邻接表由一组链表组成,其中每个链表对应于一个顶点,链表中的结点保存该顶点的所有邻接顶点的信息。具体来说: - **顶点表**:每个...
编写在邻接矩阵或邻接表存储结构下,带权有向图基本操作的实现函数(如初始化图、在图中插入一个结点、在图中插入一条边、在图中寻找序号为v的结点的第一个邻接结点、在图中寻找序号为v1结点的邻接结点v2的下一个...