廣度優(yōu)先搜索算法(BFS)
標(biāo)簽（空格分隔）： algorithm
1.廣度優(yōu)先搜索算法(Breadth First Search：BFS)
- 廣度優(yōu)先搜索顧名思義，就是要廣闊 ，不斷通過搜索自己旁邊的節(jié)點(diǎn)，旁邊的節(jié)點(diǎn)構(gòu)成一個(gè)隊(duì)列，只有把自己旁邊的節(jié)點(diǎn)遍歷完之后铛只，才會(huì)遍歷旁邊旁邊的節(jié)點(diǎn)
- 對(duì)于這種有先后順序的特性的算法過程，會(huì)考慮使用隊(duì)列這種FIFO的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)算法
- 樹的層次遍歷摩泪，可以使用廣度優(yōu)先算法
- 畫一個(gè)簡單的圖捷绑，帶入一下下面的代碼韩脑，就會(huì)很明白
- 偽代碼
void BFS(){
1.初始化:遍歷需要的隊(duì)列Q、標(biāo)志節(jié)點(diǎn)是否訪問過的粹污，hashmap
2.起始節(jié)點(diǎn)入隊(duì)列:Q.push(startNode)
3.標(biāo)志起始節(jié)點(diǎn)已經(jīng)在隊(duì)列當(dāng)中了: hashmap[startNode] = true
while(隊(duì)列非空:!Q.empty()){
需要遍歷的節(jié)點(diǎn)出隊(duì)列：node = Q.dequeue()
訪問節(jié)點(diǎn)：visited(node)
獲取node節(jié)點(diǎn)的旁邊段多，鄰接節(jié)點(diǎn)集合:adjlist = getadjList(node)
for adjNode : adjlist: 對(duì)每一個(gè)鄰接點(diǎn)，執(zhí)行
如果鄰接點(diǎn)沒有被訪問：hashmap[adjNode] != true
把鄰接點(diǎn)加入隊(duì)列壮吩，等待訪問 Q.add(adjlist)
標(biāo)志鄰接點(diǎn)已經(jīng)在隊(duì)列當(dāng)中了：hashmap[adjlist] = true
}
}
- 從遍歷的過程來看进苍，只要節(jié)點(diǎn)在隊(duì)列當(dāng)中，那么肯定標(biāo)志hashmap當(dāng)中也一定有標(biāo)記過
- 所以可以看出來鸭叙，進(jìn)隊(duì)列的時(shí)候說明這個(gè)節(jié)點(diǎn)即將被訪
- 出隊(duì)列的時(shí)候觉啊，才是節(jié)點(diǎn)真正被訪問的時(shí)候。
- 只要抓住上述兩點(diǎn)的狀態(tài)變化沈贝，就能夠明白BFS的執(zhí)行過程
- 有個(gè)問題時(shí)杠人，如果一個(gè)圖當(dāng)中，有兩個(gè)節(jié)點(diǎn)宋下，是沒有任何鄰接節(jié)點(diǎn)的嗡善，那怎么遍歷呢？
- 上述的問題很好学歧，值得思考罩引，哈哈:(:(,:):)
- 上述的BFS描述了，從某個(gè)節(jié)點(diǎn)出發(fā)去訪問這個(gè)節(jié)點(diǎn)能夠到達(dá)的所有節(jié)點(diǎn)枝笨，即訪問從這個(gè)節(jié)點(diǎn)出發(fā)蜒程，到任何一個(gè)節(jié)點(diǎn)之間有路徑的圖
- 如果一個(gè)圖有兩個(gè)節(jié)點(diǎn)直接沒有路徑，那么從單次調(diào)用BFS是無法訪問到所有的節(jié)點(diǎn)的伺帘，所以就需要多次調(diào)用BFS
- 需要注意的是昭躺，標(biāo)志節(jié)點(diǎn)是否被訪問過的hashmap需要變成對(duì)于整個(gè)圖的
void GraphTraversal(){
一個(gè)圖 Graph G
初始化標(biāo)志是否訪問過的hashmap
對(duì)每一個(gè)在圖G中的節(jié)點(diǎn)調(diào)用BFS: for node in G:
如果節(jié)點(diǎn)沒有被訪問過則調(diào)用BFS：if hashmap[node] != true :
BFS(node,hashmap)
}
- 通過上述的偽代碼能看出，一次調(diào)用BFS可能已經(jīng)把很多節(jié)點(diǎn)都訪問了伪嫁，這個(gè)時(shí)候下次以這個(gè)節(jié)點(diǎn)來做循環(huán)的時(shí)候领炫，就不需要在調(diào)用了，因?yàn)閳D的一個(gè)連通圖的從任何一個(gè)節(jié)點(diǎn)開始都能夠訪問到所有的連通圖中所有的節(jié)點(diǎn)
- 例如A---B相連张咳，那么通過A開始訪問帝洪，就可以把B也訪問了。如果從B節(jié)點(diǎn)開始脚猾，那么這個(gè)時(shí)候也能訪問到A葱峡，但是這重復(fù)訪問，遍歷只需要訪問一次就可以龙助。
public static void main(String[] args){
Graph G = new Graph();
DFS(G.get(0),G);// 表示從0 節(jié)點(diǎn)開始遍歷
}
public static void BFS(Node S,Graph G) {
/* 初始化數(shù)據(jù)結(jié)構(gòu)
* 隊(duì)列Q
* 是否遍歷的標(biāo)志hashmap
*/
Queue<Node> Q = new LinkedList<Node>();
HashMap<Node,Boolean> visitedMap = new HashMap<Node,Boolean>();
/** 初始化標(biāo)志
*/
Q.add(S);
visitedMap.put(S, true); // S 已經(jīng)認(rèn)為是在隊(duì)列當(dāng)中砰奕，說明已經(jīng)要被訪問了，所以這么標(biāo)志
while( !Q.isEmpty()) { // (0).隊(duì)列非空
Node q = Q.poll(); // (1).出隊(duì)列
visited(q); // (2).這個(gè)就是遍歷函數(shù)，或者要通過遍歷來實(shí)現(xiàn)的目標(biāo)的函數(shù),,也可以是其他的過程處理军援，比如計(jì)數(shù)仅淑，求和等
/* (3).把它的相鄰節(jié)點(diǎn)，有個(gè)求相鄰節(jié)點(diǎn)的函數(shù)
* 且未遍歷到的標(biāo)志為待遍歷并放入隊(duì)列Q
*/
ArrayList<Node> adjNodeList = G.getAdjectList(q); // 獲取相鄰的節(jié)點(diǎn)
for(int i = 0; i < adjNodeList.size() ; ++i) {
/**沒有被訪問過胸哥，放到隊(duì)列當(dāng)中*/
if (visitedMap.containsKey(adjNodeList.get(i)) == false) { // 沒有被訪問過
Q.add(adjNodeList.get(i)); //加入到隊(duì)列中
visitedMap.put(adjNodeList.get(i),true);// 表示即將被訪問
}
}//end for
}// end while
}
public static void visited(Node s) {
System.out.println(s); // 這里只是簡單的打印一下涯竟，可進(jìn)行性統(tǒng)計(jì)、計(jì)數(shù)等操作
}
2 圖聯(lián)通量的遍歷
2.1 問題描述
- 島的個(gè)數(shù)
- 假設(shè)有一塊地空厌，地中有兩種地方庐船，一種是島：人可以到達(dá)，另一種是有水的地方嘲更，人不可以到達(dá)筐钟。每個(gè)島只能從上下左右到達(dá)。
- 抽象成數(shù)學(xué)問題就是哮内，一個(gè)二維矩陣表示一塊地盗棵，島用'1'表示壮韭，水用'0' 表示北发，島和島之間如果在垂直或者水平方向相鄰，則認(rèn)為這兩個(gè)島是可以組成一個(gè)大島喷屋，現(xiàn)在是要問琳拨，這塊地上有多少個(gè)被水圍起來的孤立大島。
- 抽象數(shù)據(jù)結(jié)構(gòu)問題：問這個(gè)圖中有多少個(gè)連通分量屯曹，連通指的是狱庇，節(jié)點(diǎn)之間可達(dá)。
11110
11010
11000
00000
answer:1- 1 之間都是可達(dá)的連通的
11000
11000
00100
00011
answer:3 左上角的四個(gè)1是連通的恶耽，右下角的11是連通的密任，中間的1和自己是連通的
- 解答的思路是：通過BFS或者DFS遍歷整個(gè)圖，計(jì)算出需要調(diào)用BFS或者DFS多少次偷俭。
- 按照上面的BFS模板浪讳，容易寫出代碼，需要注意的是涌萤，這個(gè)題的重點(diǎn)是淹遵，調(diào)用多少次BFS，其實(shí)是標(biāo)志哪些節(jié)點(diǎn)可以再一次BFS調(diào)用中被訪問
- 調(diào)用一次BFS中被訪問的節(jié)點(diǎn)负溪，是連通的
/*** 一個(gè)圖
* A----B D E
* | | | |
* F----G H I
* | |
* J K L M
* | |
* N O----P----Q
* x,y 坐標(biāo)的相鄰坐標(biāo)
* (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) {
// 初始化訪問標(biāo)志
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') // 只從某個(gè)島('1')開始遍歷
continue;
String xykey = x + ":" + y;
if(visitedMap.containsKey(xykey) == false) {
// 把連通的島遍歷一下透揣，并標(biāo)志下
BFS(grid,visitedMap,x,y);
count ++;// 表示找到了一個(gè)連通分量
}
}
}
return count;
}
/**BFS的實(shí)現(xiàn)過程*/
public static void BFS(char[][] grid,HashMap<String,Boolean> visitedMap,int startx,int starty) {
/*初始化隊(duì)列*/
Queue<NodeValue> Q = new LinkedList<NodeValue>();
NodeValue e = new NodeValue(startx, starty);
/**1.添加起始遍歷節(jié)點(diǎn)到隊(duì)列
2.標(biāo)志這個(gè)節(jié)點(diǎn)即將被訪問
3.這里使用 x +":" + y 的字符串形式作為這個(gè)節(jié)點(diǎn)是否被訪問的表示
**/
Q.add(e);
visitedMap.put(startx + ":" + starty, true);
while(! Q.isEmpty()) {
NodeValue q = Q.poll();
//visited(q) 不需要任何訪問
/**獲取節(jié)點(diǎn)的鄰接節(jié)點(diǎn)集合*/
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); // 標(biāo)志即將被訪問
}
}
}
}
/**獲取某個(gè)節(jié)點(diǎn)的鄰接節(jié)點(diǎn)集合*/
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;
}
/**存儲(chǔ)下x,y的坐標(biāo)*/
static class NodeValue{
public int x, y;
public NodeValue(int x,int y){
this.x = x;
this.y = y;
}
}
- 上述的Hashmap的使用其實(shí)很別扭，標(biāo)志的hashmap其實(shí)川抡，需要起到標(biāo)記作用的數(shù)據(jù)結(jié)構(gòu)都是可以的辐真，所以可以對(duì)于二維表來表示某個(gè)坐標(biāo)表示的島是否被訪問過，
- 使用數(shù)組標(biāo)記的代碼如下
public int numIslands(char[][] grid) {
if(grid.length == 0 ){
return 0;
}
/**標(biāo)志數(shù)組*/
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')// 忽略是水的地方拆祈，因?yàn)閸u只可能是'1'
continue;
if(visitedMap[x][y] == 0 ) {
BFS(grid,visitedMap,x,y);// 把連通的島遍歷一下恨闪，并標(biāo)志下
count ++;// 表示找到了一個(gè)連通分量
}
}
}
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;
}
}
- 上述題目還有相關(guān)的變形，主要是visited函數(shù)的功能的實(shí)現(xiàn)
- 相關(guān)題目
3.參考內(nèi)容：
- 1.算法導(dǎo)論第22章基本圖算法-廣度優(yōu)先搜索
- 2.leetcode 200題目Number of Islands
