日撸Java三百行(day34:图的深度优先遍历)

2024-08-26 09:12

本文主要是介绍日撸Java三百行(day34:图的深度优先遍历),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

一、深度优先搜索

二、图的深度优先遍历

三、代码实现

总结


一、深度优先搜索

深度优先搜索(Depth First Search:DFS)是一种用于遍历树或图的算法,具体来说就是从起始节点开始,沿某一分支路径不断深入,直到无法再深入时回溯并探索其他分支。

补充:

回溯法,又称试探法,是一种选优搜索法,它的基本思想是根据选优条件向前搜索,以达到目标。当探索到某一步发现原选择并不优或达不到目标时,就回退到上一步重新选择,这种走不通就退回重走的方法即为回溯法,而满足回溯条件的点(即可以退回重新进行选择的点)就称为回溯点。

需要注意,回溯操作往往发生在某一路径不能再继续深入时,且回溯并不是回到起始位置,而是回退到上一步。

二、图的深度优先遍历

所谓图的深度优先遍历就是按照深度优先搜索的方式对图进行遍历,且每个节点(顶点)只能访问一次,为了更直观地理解深度优先遍历的整个过程,我们以下图为例进行说明。

我们将节点a作为起始节点,然后从a开始深度优先遍历,具体如下:

第一步,从节点a出发,选择一条分支路径不断深入,这里我们选择的是b-c-d分支,如下图1。

此时得到访问顺序为a-b-c-d,如下图2。

第二步,到达节点d后发现无法再继续深入,于是开始回溯,回溯到节点c后重新选择节点c的另一条分支路径e开始深入,如下图3。

此时得到访问顺序为a-b-c-d-e,如下图4。

第三步,访问节点e之后,发现节点e的唯一分支b节点已经被访问,于是回溯到节点c;回溯到节点c之后,发现节点c的两个分支均已经被访问,于是继续回溯到节点b;回溯到节点b之后,发现节点b的唯一分支节点c也已经被访问过了,于是再次回溯;回溯到节点a之后,重新选择节点a的另一分支f开始深入,如下图5。

此时得到访问顺序为a-b-c-d-e-f-g,如下图6。

第四步,访问节点g之后,发现节点g的唯一分支节点e已经被访问,于是回溯到节点f;回溯到节点f之后,发现节点f的唯一分支节点g也已经被访问,于是继续回溯到节点a;回溯到节点a之后,发现节点a的两个分支均已经被访问,于是再次回溯;发现已经没有节点可以回溯了,遍历结束。

因此,最终的遍历顺序就是a-b-c-d-e-f-g。 

根据以上分析,我们可以把DFS的过程总结为三大步:

  • 第一步,访问当前节点。
  • 第二步,如果当前节点存在未被访问的邻接节点,就进入该邻接节点(即把该邻接节点作为新的当前节点),并返回第一步。
  • 第三步,如果当前节点不存在未被访问的邻接节点,就回溯到上一个节点(即把上一个节点作为新的当前节点),并返回第二步。

此外,在上述遍历的过程中可以发现,有时候会到达已经被访问过的节点,因此为了避免重复访问,我们可以使用一个访问数组来标记节点是否被访问。

在深度优先遍历的过程中,我们需要进行回溯,即需要暂存节点信息以便后续操作使用,因此很容易想到利用栈来实现,之前入栈的元素进行出栈即可达到回溯的目的。下面我们就用栈来模拟一下上述例子的深度优先遍历,具体如下:

  • 访问节点a;a存在未被访问的邻接节点,于是将a入栈。
  • 寻找节点a的未被访问的邻接节点,找到了节点b。
  • 访问节点b;b存在未被访问的邻接节点c,于是将b入栈。
  • 寻找节点b的未被访问的邻接节点,找到了节点c。
  • 访问节点c;c存在未被访问的邻接节点d,于是将c入栈。
  • 寻找节点c的未被访问的邻接节点,找到了节点d。
  • 访问节点d;d不存在未被访问的邻接节点,所以d不入栈,将当前栈顶元素c出栈。
  • 寻找当前出栈元素c的未被访问的邻接节点,找到了节点e。
  • 访问节点e;e不存在未被访问的邻接节点,所以e不入栈,将当前栈顶元素b出栈。
  • 寻找当前出栈元素b的未被访问的邻接节点,没有找到,继续将当前栈顶元素a出栈。
  • 寻找当前出栈元素a的未被访问的邻接节点,找到了节点f。
  • 访问节点f;f存在未被访问的邻接节点,于是将f入栈。
  • 寻找节点f的未被访问的邻接节点,找到了节点g。
  • 访问节点g;g不存在未被访问的邻接节点,所以g不入栈,将当前栈顶元素出栈。
  • 但由于此时栈已空,于是遍历结束。

最后得到遍历顺序为a-b-c-d-e-f-g,与之前保持一致。因此,如果用栈来实现,那么我们之前总结的三大步就可以修改为:

  • 第一步,访问当前节点。
  • 第二步,如果该当前节点存在未被访问的邻接节点,则将该当前节点入栈,并把它的未被访问的邻接节点作为新的当前节点,返回第一步。
  • 第三步,如果该当前节点不存在未被访问的邻接节点,则将当前栈顶元素出栈,并寻找该出栈元素的未被访问的邻接节点。如果找到了,则将找到的这个节点作为新的当前节点,返回第一步;如果没有找到,就再次将当前栈顶元素出栈,重新执行第三步。

三、代码实现

大致理清楚图的深度优先遍历后,我们开始代码实现。

首先是一些基本准备工作,包括创建一个通用性栈,用于暂存节点以及创建一个布尔类型的访问数组,用于记录节点是否被访问,如下:

ObjectStack tempStack = new ObjectStack();
String resultString = "";int tempNumNodes = connectivityMatrix.getRows();
boolean[] tempVisitedArray = new boolean[tempNumNodes];

然后,访问起始节点,将访问数组中起始节点对应的元素赋值为true,并将起始节点入栈,如下:

// Initialize the stack.
// Visit before push.
tempVisitedArray[paraStartIndex] = true;
resultString += paraStartIndex;
tempStack.push(new Integer(paraStartIndex));
System.out.println("Push " + paraStartIndex);
System.out.println("Visited " + resultString);

接着,开始遍历剩余节点, 具体如下:

        // Now visit the rest of the graph.int tempIndex = paraStartIndex;int tempNext;Integer tempInteger;while (true){// Find an unvisited neighbor.tempNext = -1;for (int i = 0; i < tempNumNodes; i++) {if (tempVisitedArray[i]) {continue; // Already visited.} // Of ifif (connectivityMatrix.getData()[tempIndex][i] == 0) {continue; // Not directly connected.} // Of if// Visit this one.tempVisitedArray[i] = true;resultString += i;tempStack.push(new Integer(i));System.out.println("Push " + i);tempNext = i;// One is enough.break;} // Of for iif (tempNext == -1) {tempInteger = (Integer) tempStack.pop();System.out.println("Pop " + tempInteger);if (tempStack.isEmpty()) {// No unvisited neighbor. Backtracking to the last one// stored in the stack.// Attention: This is the terminate condition!break;} else {// Back to the previous node, however do not remove it.tempInteger = (Integer) tempStack.pop();tempIndex = tempInteger.intValue();tempStack.push(tempInteger);} // Of if} else {tempIndex = tempNext;} // Of if} // Of whilereturn resultString;

tempIndex代表当前栈顶元素,由于我们之前仅将起始节点入栈,所以此时的栈顶元素即为起始节点;然后我们进入for循环,去寻找当前节点的未被访问的邻接(直接相连)节点,在该for循环中第一个if语句用于排除已经被访问的节点,第二个if语句用于排除非邻接(直接相连)的节点,一旦找到后立马访问该节点,将访问数组中该节点对应的元素赋值为true,并将该节点入栈;tempNext代表当前未被访问的邻接节点,tempNext=-1时表示此时不存在未被访问的邻接节点,于是将当前的栈顶元素出栈。

然后,照例为该方法写一个单元测试,如下:

    /************************ Unit test for depthFirstTraversal.**********************/public static void depthFirstTraversalTest() {// Test an undirected graph.int[][] tempMatrix = { { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 0}, { 0, 1, 0, 0} };Graph tempGraph = new Graph(tempMatrix);System.out.println(tempGraph);String tempSequence = "";try {tempSequence = tempGraph.depthFirstTraversal(0);} catch (Exception ee) {System.out.println(ee);} // Of try.System.out.println("The depth first order of visit: " + tempSequence);} // Of depthFirstTraversalTest

完整的程序代码:

    /************************ Depth first traversal.* * @param paraStartIndex The start index.* @return The sequence of the visit.**********************/public String depthFirstTraversal(int paraStartIndex) {ObjectStack tempStack = new ObjectStack();String resultString = "";int tempNumNodes = connectivityMatrix.getRows();boolean[] tempVisitedArray = new boolean[tempNumNodes];// Initialize the stack.// Visit before push.tempVisitedArray[paraStartIndex] = true;resultString += paraStartIndex;tempStack.push(new Integer(paraStartIndex));System.out.println("Push " + paraStartIndex);System.out.println("Visited " + resultString);// Now visit the rest of the graph.int tempIndex = paraStartIndex;int tempNext;Integer tempInteger;while (true){// Find an unvisited neighbor.tempNext = -1;for (int i = 0; i < tempNumNodes; i ++) {if (tempVisitedArray[i]) {continue; // Already visited.} // Of ifif (connectivityMatrix.getData()[tempIndex][i] == 0) {continue; // Not directly connected.} // Of if// Visit this one.tempVisitedArray[i] = true;resultString += i;tempStack.push(new Integer(i));System.out.println("Push " + i);tempNext = i;// One is enough.break;} // Of for iif (tempNext == -1) {tempInteger = (Integer) tempStack.pop();System.out.println("Pop " + tempInteger);if (tempStack.isEmpty()) {// No unvisited neighbor. Backtracking to the last one// stored in the stack.// Attention: This is the terminate condition!break;} else {// Back to the previous node, however do not remove it.tempInteger = (Integer) tempStack.pop();tempIndex = tempInteger.intValue();tempStack.push(tempInteger);} // Of if} else {tempIndex = tempNext;} // Of if} // Of whilereturn resultString;} // Of depthFirstTraversal/************************ Unit test for depthFirstTraversal.**********************/public static void depthFirstTraversalTest() {// Test an undirected graph.int[][] tempMatrix = { { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 0}, { 0, 1, 0, 0} };Graph tempGraph = new Graph(tempMatrix);System.out.println(tempGraph);String tempSequence = "";try {tempSequence = tempGraph.depthFirstTraversal(0);} catch (Exception ee) {System.out.println(ee);} // Of try.System.out.println("The depth first order of visit: " + tempSequence);} // Of depthFirstTraversalTest/************************ The entrance of the program.* * @param args Not used now.**********************/public static void main(String args[]) {System.out.println("Hello!");Graph tempGraph = new Graph(3);System.out.println(tempGraph);// Unit test.getConnectivityTest();breadthFirstTraversalTest();depthFirstTraversalTest();} // Of main

运行结果:

总结

深度优先搜索DFS,简称深搜,是一种非常常见的算法,与广度优先搜索并称两大优先搜索算法,它具有广泛的实用性,不仅可以用来遍历树或图,还可以查找连通分量、实现拓扑排序、解决迷宫问题,并且在人工智能领域常和剪枝策略结合使用以提高在状态空间中搜索解决方案的效率。

图的深度优先遍历简言之就是先访问当前节点,然后不断搜索当前节点的未被访问的邻接节点,直到无法搜索到时开始回溯,显然这种模式下后访问的节点,它的邻接节点会先被访问,因此我们可以借助栈“后进先出”的特性来完成,当然也可以使用递归来实现。其实,如果仔细思考就会发现,图的深度优先遍历思想就是树的前序遍历思想。

这篇关于日撸Java三百行(day34:图的深度优先遍历)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1108145

相关文章

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类,它们之间的依赖,构建起了整个框架。想要理解整个架构,最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文(security context)的信息。当前操作的用户是谁,该用户是否已经被认证,他拥有哪些角色权限…这些都被保

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听