廣度優(yōu)先搜索算法（Breadth First Search，縮寫為BFS），又譯作寬度優(yōu)先搜索，或橫向優(yōu)先搜索，是一種圖形搜索算法。簡單的說，廣度優(yōu)先搜索算法是從根節(jié)點開始，沿著樹的寬度遍歷樹的節(jié)點。如果所有節(jié)點均被訪問，則算法中止。借助廣度優(yōu)先搜索算法，可以讓你找出兩樣東西之間的最短距離。

本文通過go語言實現(xiàn)廣度優(yōu)先搜索算法，使用該算法從朋友圈中找出關(guān)系最近的售貨員朋友。

下面介紹詳細的實現(xiàn)過程。首先，調(diào)用createFriendCircle函數(shù)創(chuàng)建一個模擬的朋友圈，朋友圈如下圖所示：

圖1 參考《算法圖解》

朋友圈通過字典實現(xiàn)，以“你”（you）作為根節(jié)點，字典的鍵是朋友圈屬主，值是朋友圈所有朋友名字，通過一個列表方式實現(xiàn)，名字按字母順序排序。

其次，傳遞創(chuàng)建的朋友圈給breadthFirstSearch函數(shù)，該函數(shù)是廣度優(yōu)先搜索算法的具體實現(xiàn)，在函數(shù)內(nèi)部，首先取出you的所有朋友，如果朋友數(shù)為0，查找失敗，返回false。如果朋友數(shù)不為0，則從you的所有朋友中取出一個朋友，并將朋友從待查找的朋友列表中刪除，然后創(chuàng)建一個字典記錄被查找過的朋友，避免再次查找。如果該朋友沒有被檢查過，則檢查該朋友是否是售貨員（名字以字母y結(jié)尾）。如果是售貨員，查找成功，返回true。如果該朋友不是售貨員，將該朋友的所有朋友又添加到待查找朋友列表中，繼續(xù)查找，直到結(jié)束，實現(xiàn)一種類似Z字形的搜索路徑。

由示例中可以看到，查找到的售貨員是peggy，而不是jonny。因為這里的朋友名字是按字母順序排序，所以優(yōu)先查找了bob的朋友，而不是claire的朋友，即peggy是朋友圈中距離you最近的售貨員朋友。

示例代碼如下：

package main

import "fmt"

func main() {
    friendCircle := createFriendCircle()
    breadthFirstSearch(friendCircle)
}

func personIsSeller(name string) bool {
    return name[len(name)-1] == 'y'
}

func createFriendCircle() map[string][]string {
    fc := make(map[string][]string)
    fc["you"] = []string{"alice", "bob", "claire"}
    fc["bob"] = []string{"anuj", "peggy"}
    fc["alice"] = []string{"peggy"}
    fc["claire"] = []string{"thom", "jonny"}
    fc["anuj"] = []string{}
    fc["peggy"] = []string{}
    fc["thom"] = []string{}
    fc["jonny"] = []string{}
    return fc
}

func breadthFirstSearch(friendCircle map[string][]string) bool {
    searchList := friendCircle["you"]
    if len(searchList) == 0 {
        return false
    }

    searched := make(map[string]bool)
    for {
        person := searchList[0]
        searchList = searchList[1:]
        _, found := searched[person]
        if !found {
            if personIsSeller(person) {
                fmt.Println(person + " is a seller!")
                return true
            } else {
                searchList = append(searchList, friendCircle[person]...)
                searched[person] = true
            }
        }

        if len(searchList) == 0 {
            break
        }
    }

    return false
}

/*
peggy is a seller!
*/

參考：

• 《算法圖解》
• wiki：廣度優(yōu)先搜索