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

硅谷探秘者 740 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	

 

猜你喜欢
数据结构与算法 678 广dfsjava-用邻接矩阵表示图的定点之间的关系如下图的:则用邻接矩阵表示为: privatestaticintmap[][]={ {0,3,6
数据结构与算法 8002 问题描述思路:典型的广,根字典序大小,可以确定遍历的循序,因为字典序DLRU,所以对于每一个节点往下走,然后向左走,然后向右走,然后向上走。则最后首到达出口的一条路径就是符合
weblog 2903 a*动态演示分析请参考http://photo.jiajiajia.club/item/a-star.html什么是a*A*,俗称A星,作为启发式中的一种,这是一
数据结构与算法 8272 迷宫问题-寻找最短路径:广:队列,链表代码:!DOCTYPEhtmlhtml head metacharset="UTF-8" title/title script
weblog 3408 ://photo.jiajiajia.club/item/a-star.htmlDijkstra与最佳在了解a*之前相信您已经对这两个有所了解Dijkstra是典型最短路径,用于计一个节点到其他节点
数据结构与算法 447 原文链接:https://www.zhihu.com/question/23148377?sort=created基础 时间复杂 空间复杂基础 线性表 列表(必学) 链表(必学
数据结构与算法 2561 ,largestout)的行为特征。通常采用堆级队列是不同于出队列的另一种队列。每次从队列中取出的是具有最高权的元素。操作:1.往队列中添加2.从队列中获取级队列通
weblog 2846 什么是二叉树的前驱节点后继节点?某节点的前驱节点的val值小于该节点的val值并且值是最大的那个节点。某节点的后继节点的val值大于该节点的val值并且值是最小的那个节点。下面给出一个二叉树节点类
归档
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
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo
目录