广度优先搜索算法(BFS)
标签（空格分隔）： algorithm
1.广度优先搜索算法(Breadth First Search：BFS)
- 广度优先搜索顾名思义，就是要广阔 ，不断通过搜索自己旁边的节点，旁边的节点构成一个队列，只有把自己旁边的节点遍历完之后，才会遍历旁边旁边的节点
- 对于这种有先后顺序的特性的算法过程，会考虑使用队列这种FIFO的数据结构来实现算法
- 树的层次遍历，可以使用广度优先算法
- 画一个简单的图，带入一下下面的代码，就会很明白
- 伪代码
void BFS(){
1.初始化:遍历需要的队列Q、标志节点是否访问过的，hashmap
2.起始节点入队列:Q.push(startNode)
3.标志起始节点已经在队列当中了: hashmap[startNode] = true
while(队列非空:!Q.empty()){
需要遍历的节点出队列：node = Q.dequeue()
访问节点：visited(node)
获取node节点的旁边，邻接节点集合:adjlist = getadjList(node)
for adjNode : adjlist: 对每一个邻接点，执行
如果邻接点没有被访问：hashmap[adjNode] != true
把邻接点加入队列，等待访问 Q.add(adjlist)
标志邻接点已经在队列当中了：hashmap[adjlist] = true
}
}
- 从遍历的过程来看，只要节点在队列当中，那么肯定标志hashmap当中也一定有标记过
- 所以可以看出来，进队列的时候说明这个节点即将被访
- 出队列的时候，才是节点真正被访问的时候。
- 只要抓住上述两点的状态变化，就能够明白BFS的执行过程
- 有个问题时，如果一个图当中，有两个节点，是没有任何邻接节点的，那怎么遍历呢？
- 上述的问题很好，值得思考，哈哈:(:(,:):)
- 上述的BFS描述了，从某个节点出发去访问这个节点能够到达的所有节点，即访问从这个节点出发，到任何一个节点之间有路径的图
- 如果一个图有两个节点直接没有路径，那么从单次调用BFS是无法访问到所有的节点的，所以就需要多次调用BFS
- 需要注意的是，标志节点是否被访问过的hashmap需要变成对于整个图的
void GraphTraversal(){
一个图 Graph G
初始化标志是否访问过的hashmap
对每一个在图G中的节点调用BFS: for node in G:
如果节点没有被访问过则调用BFS：if hashmap[node] != true :
BFS(node,hashmap)
}
- 通过上述的伪代码能看出，一次调用BFS可能已经把很多节点都访问了，这个时候下次以这个节点来做循环的时候，就不需要在调用了，因为图的一个连通图的从任何一个节点开始都能够访问到所有的连通图中所有的节点
- 例如A---B相连，那么通过A开始访问，就可以把B也访问了。如果从B节点开始，那么这个时候也能访问到A，但是这重复访问，遍历只需要访问一次就可以。
public static void main(String[] args){
Graph G = new Graph();
DFS(G.get(0),G);// 表示从0 节点开始遍历
}
public static void BFS(Node S,Graph G) {
/* 初始化数据结构
* 队列Q
* 是否遍历的标志hashmap
*/
Queue<Node> Q = new LinkedList<Node>();
HashMap<Node,Boolean> visitedMap = new HashMap<Node,Boolean>();
/** 初始化标志
*/
Q.add(S);
visitedMap.put(S, true); // S 已经认为是在队列当中，说明已经要被访问了，所以这么标志
while( !Q.isEmpty()) { // (0).队列非空
Node q = Q.poll(); // (1).出队列
visited(q); // (2).这个就是遍历函数，或者要通过遍历来实现的目标的函数,,也可以是其他的过程处理，比如计数，求和等
/* (3).把它的相邻节点，有个求相邻节点的函数
* 且未遍历到的标志为待遍历并放入队列Q
*/
ArrayList<Node> adjNodeList = G.getAdjectList(q); // 获取相邻的节点
for(int i = 0; i < adjNodeList.size() ; ++i) {
/**没有被访问过，放到队列当中*/
if (visitedMap.containsKey(adjNodeList.get(i)) == false) { // 没有被访问过
Q.add(adjNodeList.get(i)); //加入到队列中
visitedMap.put(adjNodeList.get(i),true);// 表示即将被访问
}
}//end for
}// end while
}
public static void visited(Node s) {
System.out.println(s); // 这里只是简单的打印一下，可进行性统计、计数等操作
}
2 图联通量的遍历
2.1 问题描述
- 岛的个数
- 假设有一块地，地中有两种地方，一种是岛：人可以到达，另一种是有水的地方，人不可以到达。每个岛只能从上下左右到达。
- 抽象成数学问题就是，一个二维矩阵表示一块地，岛用'1'表示，水用'0' 表示，岛和岛之间如果在垂直或者水平方向相邻，则认为这两个岛是可以组成一个大岛，现在是要问，这块地上有多少个被水围起来的孤立大岛。
- 抽象数据结构问题：问这个图中有多少个连通分量，连通指的是，节点之间可达。
11110
11010
11000
00000
answer:1- 1 之间都是可达的连通的
11000
11000
00100
00011
answer:3 左上角的四个1是连通的，右下角的11是连通的，中间的1和自己是连通的
- 解答的思路是：通过BFS或者DFS遍历整个图，计算出需要调用BFS或者DFS多少次。
- 按照上面的BFS模板，容易写出代码，需要注意的是，这个题的重点是，调用多少次BFS，其实是标志哪些节点可以再一次BFS调用中被访问
- 调用一次BFS中被访问的节点，是连通的
/*** 一个图
* A----B D E
* | | | |
* F----G H I
* | |
* J K L M
* | |
* N O----P----Q
* x,y 坐标的相邻坐标
* (x-1,y-1)---(x-1,y)----(x,y-1)
* (x , y-1)---(x , y)----(x,y+1)
* (x+1,y-1)---(x+1,y)----(x+1,y+1)
*/
public int numIslands(char[][] grid) {
// 初始化访问标志
HashMap<String,Boolean> visitedMap = new HashMap<String,Boolean>();
int count = 0;
for(int x =0; x < grid.length; ++x) {
for(int y = 0; y < grid[0].length; ++y) {
if(grid[x][y] == '0') // 只从某个岛('1')开始遍历
continue;
String xykey = x + ":" + y;
if(visitedMap.containsKey(xykey) == false) {
// 把连通的岛遍历一下，并标志下
BFS(grid,visitedMap,x,y);
count ++;// 表示找到了一个连通分量
}
}
}
return count;
}
/**BFS的实现过程*/
public static void BFS(char[][] grid,HashMap<String,Boolean> visitedMap,int startx,int starty) {
/*初始化队列*/
Queue<NodeValue> Q = new LinkedList<NodeValue>();
NodeValue e = new NodeValue(startx, starty);
/**1.添加起始遍历节点到队列
2.标志这个节点即将被访问
3.这里使用 x +":" + y 的字符串形式作为这个节点是否被访问的表示
**/
Q.add(e);
visitedMap.put(startx + ":" + starty, true);
while(! Q.isEmpty()) {
NodeValue q = Q.poll();
//visited(q) 不需要任何访问
/**获取节点的邻接节点集合*/
ArrayList<NodeValue> adjlist = getAdjList(grid,q);
for(int i = 0 ;i < adjlist.size(); ++i) {
e = adjlist.get(i);
String ekey = e.x +":" + e.y;
if(visitedMap.containsKey(ekey) == false) { //如果没有被访问
Q.add(e);
visitedMap.put(ekey , true); // 标志即将被访问
}
}
}
}
/**获取某个节点的邻接节点集合*/
public static ArrayList<NodeValue> getAdjList(char[][] grid,NodeValue e) {
ArrayList<NodeValue> adjlist = new ArrayList<NodeValue>();
int xlen = grid.length;
int ylen = grid[0].length;
if(e.x - 1 >=0 ) { // 上面(x-1,y)
if (grid[e.x -1][e.y] == '1') {
adjlist.add(new NodeValue(e.x - 1,e.y));
}
}
if(e.y - 1 >=0 ) { //左面(x,y - 1)
if (grid[e.x][e.y - 1 ] == '1') {
adjlist.add(new NodeValue(e.x,e.y - 1 ));
}
}
if(e.x + 1 < xlen ) { // 下面(x+1,y)
if (grid[e.x + 1][e.y] == '1') {
adjlist.add(new NodeValue(e.x + 1,e.y));
}
}
if(e.y + 1 < ylen ) { // 右面(x,y+1)
if (grid[e.x ][e.y + 1] == '1') {
adjlist.add(new NodeValue(e.x,e.y + 1));
}
}
return adjlist;
}
/**存储下x,y的坐标*/
static class NodeValue{
public int x, y;
public NodeValue(int x,int y){
this.x = x;
this.y = y;
}
}
- 上述的Hashmap的使用其实很别扭，标志的hashmap其实，需要起到标记作用的数据结构都是可以的，所以可以对于二维表来表示某个坐标表示的岛是否被访问过，
- 使用数组标记的代码如下
public int numIslands(char[][] grid) {
if(grid.length == 0 ){
return 0;
}
/**标志数组*/
int [][] visitedMap= new int[grid.length][grid[0].length];
for(int i= 0 ;i< grid.length;++i){
for(int j= 0;j < grid[0].length;++j)
visitedMap[i][j] = 0;// 0:表示为访问，1:表示访问到了
}
int count = 0;
for(int x =0; x < grid.length; ++x) {
for(int y = 0; y < grid[0].length; ++y) {
if(grid[x][y] == '0')// 忽略是水的地方，因为岛只可能是'1'
continue;
if(visitedMap[x][y] == 0 ) {
BFS(grid,visitedMap,x,y);// 把连通的岛遍历一下，并标志下
count ++;// 表示找到了一个连通分量
}
}
}
return count;
}
public static void BFS(char[][] grid,int [][] visitedMap,int x,int y) {
Queue<NodeValue> Q = new LinkedList<NodeValue>();
NodeValue e = new NodeValue(x, y);
Q.add(e);
visitedMap[x][y] = 1;
while(! Q.isEmpty()) {
NodeValue q = Q.poll();
ArrayList<NodeValue> adjlist = getAdjList(grid,q);
for(int i = 0 ;i < adjlist.size(); ++i) {
e = adjlist.get(i);
if(visitedMap[e.x][e.y] == 0) {
Q.add(e);
visitedMap[e.x][e.y] = 1;
}
}
}
}
public static ArrayList<NodeValue> getAdjList(char[][] grid,NodeValue e) {
ArrayList<NodeValue> adjlist = new ArrayList<NodeValue>();
int xlen = grid.length;
int ylen = grid[0].length;
if(e.x - 1 >=0 ) { // 上面
if (grid[e.x -1][e.y] == '1') {
adjlist.add(new NodeValue(e.x - 1,e.y));
}
}
if(e.y - 1 >=0 ) { //左面
if (grid[e.x][e.y - 1 ] == '1') {
adjlist.add(new NodeValue(e.x,e.y - 1 ));
}
}
if(e.x + 1 < xlen ) { // 下面
if (grid[e.x + 1][e.y] == '1') {
adjlist.add(new NodeValue(e.x + 1,e.y));
}
}
if(e.y + 1 < ylen ) { // 右面
if (grid[e.x ][e.y + 1] == '1') {
adjlist.add(new NodeValue(e.x,e.y + 1));
}
}
return adjlist;
}
static class NodeValue{
public int x, y;
public NodeValue(int x,int y){
this.x = x;
this.y = y;
}
}
- 上述题目还有相关的变形，主要是visited函数的功能的实现
- 相关题目
3.参考内容：
- 1.算法导论第22章基本图算法-广度优先搜索
- 2.leetcode 200题目Number of Islands
