基于廣度優先遍歷算法的應用

思考題：

（思考題答案：

BFS(廣度優先遍歷)在一般的帶權圖中是不能解決最短路問題，了解BFS的都知道，BFS是根據節點到源節點之間的節點數遍歷的，也就是先訪問離源節點節點數最少的點。要使得BFS能計算最短路徑，需要圖結構滿足所有的權值相等。否則應該使用dijkstra算法去解決最短路。

權值相等的這種情況，在解決迷宮問題的時候有很好的表現能力。因為迷宮問題滿足下面幾個特點：

1.迷宮采用矩陣的方式去儲存的時候，矩陣中的每一個元素都是一個節點。

2.節點之間四近鄰可達，或者其他的可達條件描述了節點之間的連接信息，保證了節點之間的權值是相等的。

3.節點之間是否連接是不明顯的，除非你去將迷宮矩陣轉化成圖矩陣，在不明顯的情況下，dijkstra算法就不太好理解實現。

對于這種情況的求最短路徑我們一般采用BFS求最短路徑，可以達到很好的效果。）

結論：

https://blog.csdn.net/feliciafay/article/details/9624909