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

2019 精帖
0 183

上一篇:广度优先搜索算法(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	

 

留言(0)
加载更多
猜你喜欢
  • blog --完全二叉树的权值

    试题描述:思路: 用组表示完全二叉树,用序遍历的方式遍历每一层的节点,用一个组储存每一层的,因为规模小于100000所以用一个容量为17的组即可。计完每一层的,再比较层最小之最大的那一层。代码:packa
  • file 判断单链表是否有环以及求环的入口环长2种方案分析-附java代码

    <pre class="language-java"><code class="line-numbers data-output match-braces rainbow-braces">/**
  • blog 冒泡排序 -

    思想: 每次从没有排序的集合a中拿取一个最大或最小的元素,放入有序的集合b中,直到a集合中的元素被取完 描述: 用变量i遍历整个组,用变量j遍历i后面的组,每次交换i比j大的元素,使得i遍历过的组元素有序,直至整个组被
  • blog 希尔排序 -

    思想: 希尔排序是插入排序的增强版,其主要的思想还是插入排序的思想。 描述: 在插入排序的基础上,对待排序组进行间隔为inc的分组,然后对每个分组进行直接插入排序,一次排序完成后,减小inc间隔,然后再进行分组,对每个分
  • blog 插入排序 -

    思想: 把所有需要排序的分成两个集合,一个是待排序集合,一个是已排序的集合,每次从未排序集合顺序或随机拿取一个,把它加入到已排序集合使其有序,直到未排序集合中的被取走完,束 public class Test
  • blog 归并排序(递归)-

    思想 该使用递归,思路为:每次递归将待排序组在中间位置分成左右两组,分别对左右两个组进行归并排序,递归的条件是组长必须大于等于3,所以当组中只有两个的时候可以直接进行比较排序,若组只有一个元素则无需操作。每次
  • blog 快速排序 -

    思想 将待排序集合以该集合中随机的一个为分界点分成左右两个集合,一次排序使其右边的集合的全部大于左边的集合,然后再分别递归式的对左右两个集合执行上述排序操作,直到递归集合没有,递归束完成排序。 描述 有待排序
  • ofc 再探a*(启发式函的影响)

    再探a*(启发式函的影响)
  • blog 最小生成树Kruskal-

    最小生成树其应用         什么是最小生成树:一个有 n 个点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个点,并且有保持图连通的最少的边。最小生成树可以用krus
  • blog 选择排序 -

    思想: 对冒泡排序的一种改进,每次从没有排序的集合a中拿取一个最大或最小的元素,放入有序的集合b中,直到a集合中的元素被取完 描述: 用变量i遍历整个组,用变量j遍历i后面的组,每次遍历i初始k=i,每次发a[k]比a[