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 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

[vijos]lxhgww的奇思妙想(长链剖分)

首先我们维护出每一个重链头向上$len[i]$个节点是什么,沿着重链走向下$len[i]$个节点是什么

795
来自专栏高爽的专栏

HashMap深度解析(二)

上一篇比较深入的分析了HashMap在put元素时的整体过程,Java Collections Framework中实际操作的都是数组或者链表,而我们通常...

2100
来自专栏工科狗和生物喵

【编程能力不行?那就写啊!】二叉索引树

本文直接借鉴下面的博客进行补充: 区间信息的维护与查询(一)——二叉索引树(Fenwick树、树状数组)

1066
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java提高十八】Map接口集合详解

四、Map接口 Map与List、Set接口不同,它是由一系列键值对组成的集合,提供了key到Value的映射。同时它也没有继承Collecti...

3516
来自专栏老九学堂

【干货】小白如何熟练掌握C语言随机数!

随机数的使用,是不少小伙伴在学C语言过程中都会遇到的一个坎,今天老九为大家讲解如何在C语言中使用随机数。 通常情况下,使用最多的方法的就是使用rand函数随机生...

3997
来自专栏Java技术分享

泛形

一. 泛型概念的提出(为什么需要泛型)? 首先,我们看下下面这段简短的代码:

17810
来自专栏数据结构与算法

洛谷P1501 [国家集训队]Tree II(LCT)

1530
来自专栏desperate633

一篇文章搞懂红黑树的原理及实现2-3-4 Tree(2-3-4树)红黑树左倾红黑树的删除操作删除红黑树最小节点删除任意节点总结

二叉查找树(Binary Search Tree,简称BST)是一棵二叉树,它的左子节点的值比父节点的值要小,右节点的值要比父节点的值大。它的高度决定了它的查找...

2952
来自专栏数据结构与算法

P3386 【模板】二分图匹配

题目背景 二分图 题目描述 给定一个二分图,结点个数分别为n,m,边数为e,求二分图最大匹配数 输入输出格式 输入格式: 第一行,n,m,e 第二至e+1行,每...

3277
来自专栏数据结构与算法

P3379 【模板】最近公共祖先(LCA)

题目描述 如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。 输入输出格式 输入格式: 第一行包含三个正整数N、M、S,分别表示树的结点个数...

3726

扫码关注云+社区