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

2019
0 53

广度优先搜索算法(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
java代码实现:
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实现-数据结构和算法

留言(0)
加载更多
猜你喜欢