深度优先搜索（dfs、深搜）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