#11: 親等大計算：BFS 最短路徑
nevikw39
($\mathscr{nevikw}\pmb{39}\in\m...)
學校
:
一中
編號 : 4
來源 : [140.114.207.96]
最後登入時間 ：
2023-02-14 20:37:38
c009. Ⅸ. 親等大計算
| From: [162.158.243.150] |
發表日期
:
2020-06-15 22:24
本題求的是樹上的最短路徑，所以可以利用 Breadth-First Search, BFS 透過佇列在 $O(V)$ 下輕鬆地求解。
首先自起點出發，逐一把與其相連的節點放入佇列中，同時並記錄是否造訪過與距起點的最短路徑，直到達到終點，即為所求。
謝謝大家 o'_'o
ZeroJudge Forum