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

2019 精帖
0 94

广度优先搜索算法(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)
加载更多
猜你喜欢
  • blog 使用双向循环链表解决 约瑟夫环问题-

    约瑟夫环问题描述         有m个人,围成一个环,编号为 1、2、3、、、m,从第一个人开始循环报(从1开始),假设到n的那个人出局,然后从下一个人继续(从1开始),到n出列,以
  • ofc -二叉树的前驱后继节点

    -二叉树的前驱后继节点
  • blog -反转链表-递归

    反转链表 有一个单向链表t如下: t = 1->2->3->4->5->6->7->8->9 写一个方反转链表t如下: 1<-2<-3<-4<-5<
  • blog --完全二叉树的权值

    试题描述:思路: 用组表示完全二叉树,用序遍历的方式遍历每一层的节点,用一个组储存每一层的,因为规模小于100000所以用一个容量为17的组即可。计完每一层的,再比较层最小之最大的那一层。代码:packa
  • blog java级队列(小顶堆)

    级队列 普通的队列是一种出的,元素在队列尾追加,而从队列头删除。在队列中,元素被赋予级。当访问元素时,具有最高级的元素最删除。队列具有最高级出 (first in, largest out
  • ofc 再探a*(启发式函的影响)

    再探a*(启发式函的影响)
  • blog 冒泡排序 -

    思想: 每次从没有排序的集合a中拿取一个最大或最小的元素,放入有序的集合b中,直到a集合中的元素被取完 描述: 用变量i遍历整个组,用变量j遍历i后面的组,每次交换i比j大的元素,使得i遍历过的组元素有序,直至整个组被
  • blog 希尔排序 -

    思想: 希尔排序是插入排序的增强版,其主要的思想还是插入排序的思想。 描述: 在插入排序的基础上,对待排序组进行间隔为inc的分组,然后对每个分组进行直接插入排序,一次排序完成后,减小inc间隔,然后再进行分组,对每个分
  • blog 插入排序 -

    思想: 把所有需要排序的分成两个集合,一个是待排序集合,一个是已排序的集合,每次从未排序集合顺序或随机拿取一个,把它加入到已排序集合使其有序,直到未排序集合中的被取走完,束 public class Test
  • blog 快速排序 -

    思想 将待排序集合以该集合中随机的一个为分界点分成左右两个集合,一次排序使其右边的集合的全部大于左边的集合,然后再分别递归式的对左右两个集合执行上述排序操作,直到递归集合没有,递归束完成排序。 描述 有待排序