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

硅谷探秘者 797 0 0

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

猜你喜欢
数据结构与算法 833 上一篇:广bfs广java-用邻接矩阵表示图的定点之间的关系如下图则用邻接矩阵表示为: privatestaticintmap
数据结构与算法 8051 问题描述思路:典型的广,根字典序大小,可以确定遍历的循序,因为字典序DLRU,所以对于每一个节点往下走,然后向左走,然后向右走,然后向上走。则最后首到达出口的一条路径就是符合
数据结构与算法 8305 迷宫问题-寻找最短路径广:队列,链表代码:!DOCTYPEhtmlhtml head metacharset="UTF-8" title/title script
weblog 3037 a*动态演示分析请参考http://photo.jiajiajia.club/item/a-star.html什么是a*A*,俗称A星,作为启发式中的一种,这是一
数据结构与算法 495 prim(普里姆)求出。对于任何一个,理解只是一个方面,更重要的是要明白它的应用范围或应用场景,最小生成树的应用非常广泛,例如:假设要在n个城市之间建立通信联络网,则连接n个
weblog 3542 ://photo.jiajiajia.club/item/a-star.htmlDijkstra与最佳在了解a*之前相信您已经对这两个有所了解Dijkstra是典型最短路径,用于计一个节点到其他节点
数据结构与算法 496 原文链接:https://www.zhihu.com/question/23148377?sort=created基础 时间复杂 空间复杂基础 线性表 列表(必学) 链表(必学
数据结构与算法 467 思想把所有需要排序的分成两个集合,一个是待排序集合,一个是已排序的集合,每次从未排序集合顺序或随机拿取一个,把它加入到已排序集合使其有序,直到未排序集合中的被取走完,束案例
归档
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
目录