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

硅谷探秘者 1496 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实现-数据结构和算法

猜你喜欢
数据结构与算法 1490 上一篇:广bfs广java-用邻接矩阵表示图的定点之间的关系如下图则用邻接矩阵表示为: privatestaticintmap
数据结构与算法 8439 问题描述思路:典型的广,根字典序大小,可以确定遍历的循序,因为字典序DLRU,所以对于每一个节点往下走,然后向左走,然后向右走,然后向上走。则最后首到达出口的一条路径就是符合
weblog 3965 a*动态演示分析请参考http://photo.jiajiajia.club/item/a-star.html什么是a*A*,俗称A星,作为启发式中的一种,这是一
数据结构与算法 8602 迷宫问题-寻找最短路径广:队列,链表代码:!DOCTYPEhtmlhtml head metacharset="UTF-8" title/title script
weblog 4334 ://photo.jiajiajia.club/item/a-star.htmlDijkstra与最佳在了解a*之前相信您已经对这两个有所了解Dijkstra是典型最短路径,用于计一个节点到其他节点
数据结构与算法 870 prim(普里姆)求出。对于任何一个,理解只是一个方面,更重要的是要明白它的应用范围或应用场景,最小生成树的应用非常广泛,例如:假设要在n个城市之间建立通信联络网,则连接n个
数据结构与算法 1022 原文链接:https://www.zhihu.com/question/23148377?sort=created基础 时间复杂 空间复杂基础 线性表 列表(必学) 链表(必学
数据结构与算法 4195 堆排序(英语:Heapsort)是指利用堆这种所设计的一种排序。堆是一个近似完全二叉树的,并同时满足堆积的性质:即子点的键值或引总是小于(或者大于)它的父节点。以最小堆为例下沉操
归档
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 2021年04月  4 2021年05月  4 2021年06月  1 2021年07月  7 2021年08月  2 2021年09月  8 2021年10月  9 2021年11月  16 2021年12月  14 2022年01月  7 2022年05月  1 2022年08月  3 2022年09月  2
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础
目录
余生别太较劲,放过自己 才会幸福。