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

如果只是是背概念，幼兒園的小朋友都能背下來(lái)念給你聽(tīng)。

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

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

它可以用來(lái)解決2類(lèi)問(wèn)題：

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

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

1、圖

2、散列表

3、隊(duì)列

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

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

下面我將展示一個(gè)簡(jiǎn)單的地圖。

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

請(qǐng)思考1分鐘....

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

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)先搜索的思路。不過(guò)已經(jīng)很接近了，廣度優(yōu)先搜索沒(méi)有那么深?yuàn)W，你完全可以用正常邏輯來(lái)理解。

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

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

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

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

1、首先你在北京；

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

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

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

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

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

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

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

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

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

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

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

你應(yīng)該有過(guò)在學(xué)校飯?zhí)门抨?duì)打飯的體驗(yàn)，在確保沒(méi)人插隊(duì)的前提下，排隊(duì)越前的就越先打到飯，然后離開(kāi)，新來(lái)的要打飯的人必須排隊(duì)到隊(duì)列的末尾。專(zhuān)業(yè)名詞叫做“先進(jìn)先出”。

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

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

想要回答這個(gè)問(wèn)題，我們結(jié)合前面講過(guò)的圖、散列表、隊(duì)列一起來(lái)解答。

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

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

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

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

思路：構(gòu)造二度空間散列表，我們只需要遍歷一度空間，然后用遞歸遍歷二度甚至N度空間即可，但是遞歸要注意內(nèi)存溢出的問(wèn)題，前端不宜做大量數(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é)會(huì)分析這種問(wèn)題，思維比算法的實(shí)現(xiàn)更重要，如果給你換一個(gè)圖，你就不會(huì)用JavaScript實(shí)現(xiàn)也沒(méi)有關(guān)系，能用文字表達(dá)出思路就夠了。

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

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