摘要：散列表上面的地圖向我們展示了如何用廣度優(yōu)先搜索的思想找到北京到廣州的最短路線。在廣度優(yōu)先搜索中，我們需要用到隊列的這種思想來實(shí)現(xiàn)查找。建立了下面這個模型武漢廣州西藏上海上海武漢廣州代碼完整實(shí)現(xiàn)，利用遞歸和廣度優(yōu)先搜索的思想實(shí)現(xiàn)。

如果只是是背概念，幼兒園的小朋友都能背下來念給你聽。

假設(shè)看這篇文章的都和我一樣是個前端工程師，我們要從廣度優(yōu)先搜索（BFS）中學(xué)到什么？如果你看完這篇文章能夠回答這個問題，那么你已經(jīng)看懂了。

廣度優(yōu)先搜索不是排序算法，它和快速排序、選擇排序、冒泡排序等不一樣，你聽過二分查找嗎？廣度優(yōu)先搜索是一種查找算法。

它可以用來解決2類問題：

1、節(jié)點(diǎn)A能不能到節(jié)點(diǎn)N？

2、如果能到，它的最短路徑是什么？

1、圖

2、散列表

3、隊列

4、算法實(shí)現(xiàn)

學(xué)過數(shù)據(jù)結(jié)構(gòu)的同學(xué)對圖比較了解了，沒學(xué)過的也沒關(guān)系，圖表示的關(guān)系網(wǎng)絡(luò)，你看過神經(jīng)網(wǎng)絡(luò)圖、人際關(guān)系圖、家族圖譜圖、以及最常見的地圖嗎？如果你都沒見過，還是別學(xué)了......

下面我將展示一個簡單的地圖。

思考一個問題，假設(shè)你現(xiàn)在在北京，現(xiàn)在想跳槽到廣州，行李以及收拾好了，跟老板辭職也通過了，現(xiàn)在你想將所有可以到達(dá)廣州的路線找出來（這里忽略你搭地鐵或者打的的時間，而且模擬北京不能直達(dá)廣州的情況），都有那幾條路線？

請思考1分鐘....

確保你真的思考的前提下，我來猜一下你是如何找到北京到廣州的所有路線的！

1、你眼睛先盯著北京，然后發(fā)現(xiàn)可以到達(dá)武漢，接著發(fā)現(xiàn)武漢可以到達(dá)廣州，ok，第一條路線完成。

北京 -> 武漢 -> 廣州

2、接著你又返回北京，你突然記得武漢可以到達(dá)上海，所以你又從北京到達(dá)了武漢，武漢去了上海，發(fā)現(xiàn)上海可以到達(dá)廣州。第二條路線完成。

北京 -> 武漢 -> 上海 -> 廣州

3、再次回到北京，你記得武漢還有一條去往西藏的路線，但是走了一遍發(fā)現(xiàn)西藏不能到達(dá)廣州。

4、回到北京，現(xiàn)在出發(fā)去上海，接著你發(fā)現(xiàn)上海直接到達(dá)了廣州，第三條路線完成。

北京 -> 上海 -> 廣州

5、回到北京，再次去上海，接著到武漢，哇塞，又能到廣州了。第四條路線完成。

北京 -> 上海 -> 武漢 -> 廣州

現(xiàn)在找完了所有路線，一共4條，但是，這不是廣度優(yōu)先搜索的思路。不過已經(jīng)很接近了，廣度優(yōu)先搜索沒有那么深奧，你完全可以用正常邏輯來理解。

還記得上面我們說到廣度優(yōu)先搜索解決的問題嗎？

1、節(jié)點(diǎn)A能不能到節(jié)點(diǎn)N？

2、如果能到，它的最短路徑是什么？

廣度優(yōu)先搜索判斷北京到廣州的路徑：

1、首先你在北京；

2、接著你問自己，北京能不能直接到達(dá)廣州？你將地圖搜索了一下，發(fā)現(xiàn)北京只能到達(dá)武漢和上海，這說明你完成了第一步搜索。上海和武漢屬于北京的“一度空間”，具有優(yōu)先搜索權(quán)；

3、西藏和廣州屬于北京的“二度空間”，當(dāng)你在一度空間搜索不到目標(biāo)時，就在二度空間搜索，如果還是搜索不到，就一直往N度空間搜索下去，直至搜索完整個地圖。用正常人的理解就是，第2步時你搜索了武漢和上海都沒有找到目標(biāo)，就分別搜索武漢和上海的臨近節(jié)點(diǎn)，發(fā)現(xiàn)武漢和上海都可以直接到達(dá)廣州；

4、你根據(jù)這種方法很快就回答了廣度優(yōu)先搜索提出的2個問題，找到了北京到廣州的路線，并且找到了2條可能是最短的路線：北京 -> 武漢 -> 廣州，北京 -> 上海 -> 廣州。實(shí)際問題中，我們需要計算的節(jié)點(diǎn)間的距離找到最短的路線，這里不做計算，只分析思路。

圖本身的概念挺多，包括節(jié)點(diǎn)、邊界、有向、無向，但不需要學(xué)習(xí)這些知識也能理解廣度優(yōu)先搜索的思想。

上面的地圖向我們展示了如何用廣度優(yōu)先搜索的思想找到北京到廣州的最短路線。那么散列表是什么？它在廣度優(yōu)先搜索中的作用是什么？

為了回答這2個問題，我想請你回憶一下JavaScript中的Map，如果不了解Map，也沒關(guān)系，回憶Object也行。Object近似的可以看成是散列表的數(shù)據(jù)結(jié)構(gòu)。

散列表也叫做哈希表，它的平均時間復(fù)雜度是O(1)，它長的也不奇怪，就是key，value結(jié)構(gòu)。

我們可以用簡單的Object結(jié)構(gòu)來表示節(jié)點(diǎn)之間的關(guān)系：

const map = {
  "武漢": {
    "廣州": {},
    "西藏": {},
    "上海": {}
  },
  "上海": {
    "武漢": {},
    "廣州": {}
  }
}

散列表的內(nèi)部實(shí)現(xiàn)是一種鏈組結(jié)構(gòu)，也就是鏈表和數(shù)組的復(fù)合體。使用散列表的時候，要注意，key盡量不要重復(fù)，要分散，如果有重復(fù)，就會造成沖突，導(dǎo)致時間復(fù)雜度不是O(1)了。

有了圖的存儲結(jié)構(gòu)，就能用代碼來實(shí)現(xiàn)查找操作，但是在這之前，我們還要了解隊列的思想。

你應(yīng)該有過在學(xué)校飯?zhí)门抨牬蝻埖捏w驗，在確保沒人插隊的前提下，排隊越前的就越先打到飯，然后離開，新來的要打飯的人必須排隊到隊列的末尾。專業(yè)名詞叫做“先進(jìn)先出”。

在廣度優(yōu)先搜索中，我們需要用到隊列的這種思想來實(shí)現(xiàn)查找。JavaScript可以用數(shù)組模擬隊列，你不需要多帶帶構(gòu)建一個隊列的數(shù)據(jù)結(jié)構(gòu)。

那么，廣度優(yōu)先搜索是如何用隊列實(shí)現(xiàn)的呢？

想要回答這個問題，我們結(jié)合前面講過的圖、散列表、隊列一起來解答。

先要明白一點(diǎn)，廣度優(yōu)先搜索沒有唯一的算法，不同的圖實(shí)現(xiàn)的方法不一樣，但是思想是一致的，主要跟你的圖對應(yīng)的存儲結(jié)構(gòu)有關(guān)。復(fù)雜的圖可能使用多張表來存儲數(shù)據(jù)。

這里我采用的方法是根據(jù)維度空間來建立數(shù)據(jù)模型。首先找到一維空間的路線，北京 -> 武漢，北京 -> 上海。然后是二維空間的路線。建立了下面這個模型：

const map = {
  "武漢": {
    "廣州": {},
    "西藏": {},
    "上海": {}
  },
  "上海": {
    "武漢": {},
    "廣州": {}
  }
}

JavaScript代碼完整實(shí)現(xiàn)，利用遞歸和廣度優(yōu)先搜索的思想實(shí)現(xiàn)。

思路：構(gòu)造二度空間散列表，我們只需要遍歷一度空間，然后用遞歸遍歷二度甚至N度空間即可，但是遞歸要注意內(nèi)存溢出的問題，前端不宜做大量數(shù)據(jù)的算法操作。

const map = {
  "武漢": {
    "廣州": {},
    "西藏": {},
    "上海": {}
  },
  "上海": {
    "武漢": {},
    "廣州": {}
  }
}
function breadthSearch(obj, goal, arr = ["北京"]) {
  for(let key in obj) {
    //遍歷一度空間
    if (arr.indexOf(key) < 0) {
      //如果數(shù)組中不存在當(dāng)前的key，就push
      arr.push(key)
      if (key === goal) {
        //如果key是要查找的目標(biāo)節(jié)點(diǎn)，直接返回
        return arr
      } else {
        //如果key不是要查找的目標(biāo)節(jié)點(diǎn)，繼續(xù)遞歸
        return breadthSearch(obj[key], goal, arr)
      }
    }
  }
}

const s = breadthSearch(map, "廣州")

console.log(s) //["北京", "武漢", "廣州"]

看到這里，廣度優(yōu)先搜索的思想以及JavaScript模擬實(shí)現(xiàn)到這里就結(jié)束了，前端工程師不需要完全掌握它，而是學(xué)會分析這種問題，思維比算法的實(shí)現(xiàn)更重要，如果給你換一個圖，你就不會用JavaScript實(shí)現(xiàn)也沒有關(guān)系，能用文字表達(dá)出思路就夠了。

廣度優(yōu)先針對的是無權(quán)圖的搜索，如果給節(jié)點(diǎn)之間的邊加上權(quán)重距離，就要用到其他算法了，后面我會講到狄克斯特拉算法和貪婪算法等思想的實(shí)現(xiàn)。

與廣度優(yōu)先搜索相對的，就是深度優(yōu)先搜索，我不打算在這一章講，回到文章一開始的問題，你從廣度優(yōu)先搜索（BFS）中學(xué)到了什么？現(xiàn)在能回答了嗎？