dfs

一、DFS定义 

  深度优先搜索算法(Depth-First-Search,简称DFS)是一种常用于遍历或搜索树或图的算法。从初始访问结点出发,初始访问结点可能有多个邻接结点,深度优先遍历的策略就是首先访问第一个邻接结点,然后再以这个被访问的邻接结点作为初始结点,访问它的第一个邻接结点,尽可能深的搜索树的分支。当节点所在边都己被探寻过,搜索将回溯到发现节点的那条边的起始节点。重复这一过程一直进行到已发现从源节点可达的所有节点为止。

二、DFS过程

  深度优先搜索是一个递归的过程。算法的具体实现过程就可以表述如下:

  1.访问初始节点v,并标记节点v为已访问;

  2.查找节点v的第一个邻接节点w;

  3.若w存在,则继续执行4步骤,否则结束算法;

  4.若w未被访问,对w进行深度优先搜索递归(将w看做新的初始节点,重复1,2,3);

  5.查找节点v的w邻接节点的下一个邻接节点,转到步骤3。

图1 深度优先搜索示意图

  如图1所示,节点1作为初始节点,从该节点开始,并将其标记为已访问,查找节点1的第一个邻节点,为节点2,节点2未被访问过,然后将2看做初始节点,查找节点2的第一个邻接节点,为节点4,节点4未被访问过,将节点4看做初始节点,查找节点4的第一个临接节点,为节点8,节点8未被访问过,将节点8看做初始节点,查找节点8的第一个邻接节点,不存在,所以回溯到节点4,节点4除了节点8之外没有其他临接节点,回溯到节点2,节点2除了节点4这个邻接节点之外,还有一个邻接节点5,节点5未被访问过,将节点5看做初始节点,节点5的临接节点不存在,回溯到2,节点2没有其他临接节点,回溯到节点1,以此继续进行下去,直到遍历完全部的节点。

所以,深度优先遍历顺序为:1->2->4->8->5->3->6->7

三、DFS算法实现 

  在解决深度优先搜索的问题上,常用递归法和栈这两种方法来实现。

  方法一:递归法

/**
 * 深度优先搜索(递归法)
 * 
 * */
public class DFSTest {

	//存储节点信息
	private char[] nodes;
	
	//存储边信息(如果节点连接,为1,否则为0)
	private int[][] edges;
	
	//节点个数
	private int nodesNum;
	
	//边是否被遍历过
	private boolean[] visited;
	
	/**
	 * 初始化
	 * 1. 节点个数
	 * 2. 节点连接信息
	 * 3. 节点是否被遍历过
	 * 
	 * */
	public DFSTest(int num) {
		
		nodesNum = num;
		nodes = new char[num];
		edges = new int[num][num];
		visited = new boolean[num];
		
		for (int i = 0; i < nodesNum; i++) {
			for (int j = 0; j < nodesNum; j++) {
				
				edges[i][j] = 0;
			}
		}
	}
	
	/**
	 * 添加边信息(节点连接则设置为1,否则为0)
	 * 
	 * @param num1 通过边连接的节点1
	 * @param num2 通过边连接的节点2
	 * 
	 * */
	public void addEdge(int num1, int num2) {
		
		if (num1 == num2) {
			
			return;
		} else {
			
			edges[num1][num2] = 1;
			edges[num2][num1] = 1;
		}
	}
	
	/**
	 * 设置节点集
	 * @param nodes 节点
	 * 
	 * */
	public void setNodes(char[] nodes) {
		
		this.nodes = nodes;
	}
	
	/**
	 * 设置节点访问标记
	 * @param visited 访问标记
	 * 
	 * */
	public void setVisited(boolean[] visited) {
		
		this.visited = visited;
	}
	
	/**
	 * 打印遍历节点
	 * @param num 节点
	 * 
	 * */
	public void visit(int i) {
		
		System.out.print(nodes[i] + " ");
	}
	
	/**
	 * 从第i个节点开始深度优先遍历
	 * 
	 * @param i 第i个节点
	 * 
	 * */
	private void travel(int i) {
		
		visited[i] = true;
		
		visit(i);
		
		for (int j = 0; j < nodesNum; j++) {
			
			if (1 == edges[i][j] && false == visited[j]) {
				
				travel(j);
			}
		}
	}
	
	//图的深度优先遍历(递归法)
	public void DFSTravel() {
		
		//初始化节点遍历标记
		for (int i = 0;  i < nodesNum; i++) {
			
			visited[i] = false;
		}
		
		//从没有遍历过的节点开始遍历
		for (int i = 0; i < nodesNum; i++) {
			
			if (visited[i] == false) {
				
				travel(i);
			}
		}
	}
	
	public static void main(String[] args) {
		
		DFSTest dfsTest = new DFSTest(8);
		
		char[] nodes = {'1', '2', '3', '4', '5', '6', '7', '8'};
		dfsTest.setNodes(nodes);
		
		dfsTest.addEdge(0, 1);
		dfsTest.addEdge(0, 2);
		dfsTest.addEdge(1, 0);
		dfsTest.addEdge(1, 3);
		dfsTest.addEdge(1, 4);
		dfsTest.addEdge(2, 0);
		dfsTest.addEdge(2, 5);
		dfsTest.addEdge(2, 6);
		dfsTest.addEdge(3, 1);
		dfsTest.addEdge(3, 7);
		dfsTest.addEdge(4, 1);
		dfsTest.addEdge(4, 7);
		dfsTest.addEdge(5, 2);
		dfsTest.addEdge(5, 6);
		dfsTest.addEdge(6, 2);
		dfsTest.addEdge(6, 5);
		dfsTest.addEdge(7, 3);
		dfsTest.addEdge(7, 4);
		
		dfsTest.DFSTravel();
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之用两个栈实现队列(九度OJ1512)

题目描述: 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 输入: 每个输入文件包含一个测试样例。 对于每个测试样例,第一...

1845
来自专栏python读书笔记

《python算法教程》Day4 - 拓扑排序(基于有向无环图)拓扑排序简介代码实例

这是《python算法教程》的第4篇读书笔记。这篇笔记的主要内容为拓扑排序。 拓扑排序简介 在将一件事情分解为若干个小事情时,会发现小事情之间有完成的先后次序之...

34211
来自专栏一英里广度一英寸深度的学习

Leetcode 第一题 《两数之和》

681
来自专栏文武兼修ing——机器学习与IC设计

调度队列的优先堆实现应用场景模拟应用分析代码实现

应用场景模拟 考虑优先堆的一种应用场景——按优先级的任务调度队列:每个任务有一个优先级和唯一标号,该调度队列需要具有以下功能: 添加任务:将任务添加进调度队列并...

32510
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之用两个栈实现队列(九度OJ1512)

题目描述: 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 输入: 每个输入文件包含一个测试样例。 对于每个测试样例,第一...

1766
来自专栏小白客

每天学习一点儿算法--递归

递归是很多算法都使用的一种编程方法。听说递归是一种十分优雅的问题解决办法,可是对于初涉递归的我,还没有形成这种独特的体会。 学习使用递归的关键在于:如何将问题分...

2958
来自专栏用户2442861的专栏

strcpy函数的实现

http://blog.csdn.net/gpengtao/article/details/7464061

512
来自专栏python读书笔记

《算法图解》NOTE 3 递归1.定义2递归结构2.适用场合3.应用案例

1444
来自专栏深度学习之tensorflow实战篇

稀疏矩阵压缩sparse.csr_matrix函数与sparse.csc_matric详解

概述 在用python进行科学运算时,常常需要把一个稀疏的np.array压缩,这时候就用到scipy库中的sparse.csr_matrix(csr:Comp...

3195
来自专栏闪电gogogo的专栏

【数据结构(C语言版)系列四】 串

串(或字符串)是由零个或多个字符组成的有限序列,一般记为 s = 'a1a2...an',s为串名。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。

311

扫码关注云+社区