深度优先搜索(dfs、深搜)java实现-数据结构和算法

硅谷探秘者 1619 0 0

上一篇:广度优先搜索算法(bfs、广搜)java实现-数据结构和算法

用邻接矩阵表示图的定点之间的关系

如下图数据结构

则用邻接矩阵表示为:

	private static int map[][]={
	  {0  ,3  ,6  ,-1 ,-1 ,-1 ,-1 ,-1,-1,-1,-1},
	  {3  ,0  ,-1 ,4  ,1  ,-1 ,-1 ,-1,3 ,-1,-1},
	  {6  ,-1 ,0  ,-1 ,-1 ,-1 ,-1 ,3 ,-1,-1,-1},
	  {-1 ,4  ,-1 ,0  ,3  ,-1 ,-1 ,6 ,-1,-1,-1},
	  {-1 ,1  ,-1 ,3  ,0  ,5  ,-1 ,-1,-1,-1,-1},
	  {-1 ,-1 ,-1 ,-1 ,5  ,0  ,2  ,-1,-1, 3, 3},
	  {-1 ,-1 ,-1 ,-1 ,-1 ,2  ,0  ,1 ,-1,-1,-1},
	  {-1 ,-1 ,3  ,6  ,-1 ,-1 ,1  ,0 ,-1,-1,-1},
	  {-1 ,3  ,-1 ,-1 ,-1 ,-1 ,-1 ,-1,0 ,-1,-1},
	  {-1 ,-1 ,-1 ,-1 ,-1 ,3  ,-1 ,-1,-1,0 ,3 },
	  {-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1,-1,3 ,0 }
	};

横坐标和纵坐标代表第n个节点,值>0代表两个节点相连,并且值代表两个节点之间的权值(暂时没有用到),-1代表两个节点之间不相连。

算法和思路:
  • 1.从第一个节点开始当作当前节点
  • 2.遍历当前节的所有没有被标记的子节点
  • 3.如果有[没有被标记的子节点,则把当前节点入栈,把子节点赋值给当前节点,继续过程2。否则,判断栈中是否含有元素,如果含有,则取出一个元素继续过程2,否则结束遍历 
java代码实现: 
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

public class Test {
	/**
	 * 	邻接矩阵表示的图 的二维数组
	 * 	横坐标和纵坐标代表第n个节点,值>0代表两个节点相连,并且值代表两个节点之间的权值(暂时没有用到),
	 * 	-1代表两个节点之间不相连
	 */
	private static int map[][]={
	  {0  ,3  ,6  ,-1 ,-1 ,-1 ,-1 ,-1,-1,-1,-1},
	  {3  ,0  ,-1 ,4  ,1  ,-1 ,-1 ,-1,3 ,-1,-1},
	  {6  ,-1 ,0  ,-1 ,-1 ,-1 ,-1 ,3 ,-1,-1,-1},
	  {-1 ,4  ,-1 ,0  ,3  ,-1 ,-1 ,6 ,-1,-1,-1},
	  {-1 ,1  ,-1 ,3  ,0  ,5  ,-1 ,-1,-1,-1,-1},
	  {-1 ,-1 ,-1 ,-1 ,5  ,0  ,2  ,-1,-1, 3, 3},
	  {-1 ,-1 ,-1 ,-1 ,-1 ,2  ,0  ,1 ,-1,-1,-1},
	  {-1 ,-1 ,3  ,6  ,-1 ,-1 ,1  ,0 ,-1,-1,-1},
	  {-1 ,3  ,-1 ,-1 ,-1 ,-1 ,-1 ,-1,0 ,-1,-1},
	  {-1 ,-1 ,-1 ,-1 ,-1 ,3  ,-1 ,-1,-1,0 ,3 },
	  {-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1,-1,3 ,0 }
	};
	
	public static void main(String[] args) {
		dfs();
	}
	/**
	 * 	深度优先搜索
	 * 	思路:
	 * 	1.从第一个节点开始当作当前节点
	 * 	2.遍历当前节的所有没有被标记的子节点
	 * 	3.如果有[没有被标记的子节点,则把当前节点入栈,把子节点赋值给当前节点,继续过程2。
	 * 		否则,判断栈中是否含有元素,如果含有,则取出一个元素继续过程2,否则结束遍历
	 */
	public static void dfs() {
		Set<Integer> set=new HashSet<Integer>();
		/**
		 * 存储经过的节点路径
		 */
		LinkedList<Integer> path=new LinkedList<Integer>();
		/**
		 * 	储存待遍历节点的栈
		 */
		LinkedList<Node> stack=new LinkedList<Node>();
		Node th=new Node(0, 0);//当前需要遍历的节点
		map[th.i][th.p]=-1;
		while(true) {
			int p;
			for(p=th.p;p<map.length;p++) {
				/**
				 * 	遍历当前节点的所有没有遍历过的子节点
				 */
				if(map[th.i][p]>0&&map[p][p]==0) {
					th.p=p+1;
					stack.addFirst(th);//当前节点入栈
					if(!set.contains(th.i)) {
						set.add(th.i);
						path.addFirst(th.i);
					}
					th=new Node(p,0);
					map[p][p]=-1;
					p=0;
				}
			}
			if(!set.contains(th.i)) {
				set.add(th.i);
				path.addFirst(th.i);
			}
			if(stack.size()>0) {
				th=stack.removeFirst();
			}else {
				break;
			}
		}
		while(path.size()>0){
			System.out.print(path.removeLast()+"\t");
		}
	}
	public static class Node{
		public Integer i;//当前元素i
		public Integer p;//当前遍历第p个元素
		public Node(int i,int p) {
			this.i=i;
			this.p=p;
		}
	}
}

 输出:

0	1	3	4	5	6	7	2	9	10	8	

 

猜你喜欢
数据结构与算法 1608 广dfsjava-用邻接矩阵表示图的定点之间的关系如下图的:则用邻接矩阵表示为: privatestaticintmap[][]={ {0,3,6
数据结构与算法 8526 问题描述思路:典型的广,根字典序大小,可以确定遍历的循序,因为字典序DLRU,所以对于每一个节点往下走,然后向左走,然后向右走,然后向上走。则最后首到达出口的一条路径就是符合
weblog 4130 a*动态演示分析请参考http://photo.jiajiajia.club/item/a-star.html什么是a*A*,俗称A星,作为启发式中的一种,这是一
数据结构与算法 8675 迷宫问题-寻找最短路径:广:队列,链表代码:!DOCTYPEhtmlhtml head metacharset="UTF-8" title/title script
weblog 4474 ://photo.jiajiajia.club/item/a-star.htmlDijkstra与最佳在了解a*之前相信您已经对这两个有所了解Dijkstra是典型最短路径,用于计一个节点到其他节点
数据结构与算法 1124 原文链接:https://www.zhihu.com/question/23148377?sort=created基础 时间复杂 空间复杂基础 线性表 列表(必学) 链表(必学
weblog 3740 什么是二叉树的前驱节点后继节点?某节点的前驱节点的val值小于该节点的val值并且值是最大的那个节点。某节点的后继节点的val值大于该节点的val值并且值是最小的那个节点。下面给出一个二叉树节点类
数据结构与算法 3552 ,largestout)的行为特征。通常采用堆级队列是不同于出队列的另一种队列。每次从队列中取出的是具有最高权的元素。操作:1.往队列中添加2.从队列中获取级队列通
归档
2018年11月  12 2018年12月  33 2019年01月  28 2019年02月  28 2019年03月  32 2019年04月  27 2019年05月  33 2019年06月  6 2019年07月  12 2019年08月  12 2019年09月  21 2019年10月  8 2019年11月  15 2019年12月  25 2020年01月  9 2020年02月  5 2020年03月  16 2020年04月  4 2020年06月  1 2020年07月  7 2020年08月  13 2020年09月  9 2020年10月  5 2020年12月  3 2021年01月  1 2021年02月  5 2021年03月  7 2021年04月  4 2021年05月  4 2021年06月  1 2021年07月  7 2021年08月  2 2021年09月  8 2021年10月  9 2021年11月  16 2021年12月  14 2022年01月  7 2022年05月  1 2022年08月  3 2022年09月  2 2022年10月  2
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础 xxl-job
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。