广度优先搜索算法（dfs、深搜）java实现-数据结构和算法

如下图的数据结构：

则用邻接矩阵表示为：

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

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

• 1.先将第一个开始遍历的节点放入队列，并且标记该元素已放入队列
• 2.如果队列中有数据，则从队列中取出一个数据，否则结束遍历
• 3.访问该数据
• 4.将该数据所有相邻的并且还没有被标记的元素放入队列，执行过程2

import java.util.LinkedList;
/**
 * @author Jiajiajia
 */
public class Test {
	
	/**
	 * 	邻接矩阵表示的图 的二维数组
	 * 	横坐标和纵坐标代表第n个节点,值>0代表两个节点相连，并且值代表两个节点之间的权值（暂时没有用到），
	 * 	-1代表两个节点之间不相连
	 */
	private static int map[][]={
	  {0  ,3  ,6  ,-1 ,-1 ,-1 ,-1 ,-1},
	  {3  ,0  ,-1 ,4  ,1  ,-1 ,-1 ,-1},
	  {6  ,-1 ,0  ,-1 ,-1 ,-1 ,-1 ,3 },
	  {-1 ,4  ,-1 ,0  ,3  ,-1 ,-1 ,6 },
	  {-1 ,1  ,-1 ,3  ,0  ,5  ,-1 ,-1},
	  {-1 ,-1 ,-1 ,-1 ,5  ,0  ,2  ,-1},
	  {-1 ,-1 ,-1 ,-1 ,-1 ,2  ,0  ,1 },
	  {-1 ,-1 ,3  ,6  ,-1 ,-1 ,1  ,0 }
	};
	
	public static void main(String[] args) {
		bfs();
	}
	
	/**
	 * 	bfs（广度优先搜索）
	 * 	思路：
	 * 	1.先将第一个开始遍历的节点放入队列，并且标记该元素已放入队列
	 * 	2.如果队列中有数据，则从队列中取出一个数据，否则结束遍历
	 * 	3.访问该数据
	 * 	4.将该数据所有相邻的并且还没有被标记的元素放入队列，执行过程2
	 */
	public static void bfs() {
		/**
		 * 	储存待遍历节点的队列
		 */
		LinkedList<Integer> queue=new LinkedList<Integer>();
		/**
		 * 	将第一个需要遍历的节点放入队列
		 */
		queue.offer(0);
		map[0][0]=-1;
		while(queue.size()>0) {
			/**
			 * 	如果队列中有数据，那就取出数据并访问
			 */
			Integer i=queue.pop();//取出数据（头部）
			System.out.println("访问："+i);//访问数据
			for(int p=0;p<map.length;p++) {
				/**
				 * 遍历当前节点所有没有遍历过的子节点，并将其加入队列
				 */
				if(map[i][p]>0&&map[p][p]==0) {
					/**
					 * 	map[i][p]>0代表i节点和p节点连接，map[p][p]==0代表该节点还未被访问过
					 */
					map[p][p]=-1;//标记该节点已被访问
					queue.offer(p);//将该节点加入队列(尾部插入)
				}
			}
		}
	}
}

输出：

0	1	2	3	4	7	5	6

下一篇： 深度优先搜索（dfs、深搜）java实现-数据结构和算法