蓝桥杯 BFS 广度优先搜索

问题描述

要求：用广度搜索遍历下图，再使用顺序存储结构表示

0 0 1 1 0 1 0

0 0 1 0 0 0 0

1 1 0 1 0 0 0

1 0 1 0 0 0 0

0 0 0 0 0 0 1

1 0 0 0 0 0 1

0 0 0 0 1 1 0

广搜：A-C-D-F-B-G-E

解题思路

BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。

参考代码

import java.util.LinkedList;
import java.util.Queue;

public class Main {

	static String []nodes = { "A", "B", "C", "D", "E","F","G" };
	static int length = nodes.length;
	static boolean check[] = new boolean[length];
	static Queue<Integer> queue = new LinkedList<Integer>();
	static int[][] map ={
		{0 ,0 ,1 ,1 ,0 ,1 ,0},
		{0 ,0 ,1 ,0 ,0 ,0 ,0},
		{1 ,1 ,0 ,1 ,0 ,0 ,0},
		{1 ,0 ,1 ,0 ,0 ,0 ,0},
		{0 ,0 ,0 ,0 ,0 ,0 ,1},
		{1 ,0 ,0 ,0 ,0 ,0 ,1},
		{0 ,0 ,0 ,0 ,1 ,1 ,0}
		}; 
	public static void main(String[] args) {
		//从A节点开始
		queue.add(0);
		check[0] = true;
		
		//遍历节点的条件：队列不为空
		while (!queue.isEmpty()) {
			//队列弹出节点
			int index = queue.poll();
			System.out.print(nodes[index]+"-");//输出访问
			
			//遍历此节点与其他节点是否联通
			for (int i = 0; i < length; i++) {
				//判定条件：要访问的节点未被访问过 && 要访问的节点与此节点联通
				if (!check[i] && map[index][i] == 1){
					//找到联通节点继续加入队列，并标记为访问
					check[i] = true;
					queue.add(i);
				}
			}
		}
	}
}