↑: [[幅優先探索.md|1/2]]
次のようなグラフで0から5に最小で移動したい場合
```
0-1-2
| | |
3-4-5
```
![[BFSで最短経路を求める例-20250817-191112.excalidraw.svg]]
%%[[BFSで最短経路を求める例-20250817-191112.excalidraw.md|🖋 Edit in Excalidraw]]%%
- 上の図のような探索の結果、0から5に移動したい場合は
最短3回で移動できることがわかる。
擬似コード
```python
graph = {
0: (1,3),
1: (0,4,2),
2: (1,5),
3: (0,4),
4: (1,3,5),
5: (2,4),
}
dist = [-1] * 6
Q = new queue()
dist[0] = 0 # スタート地点の距離は0
Q.add(0)
while (Q.front()):
q = Q.pop()
for next in graph(q):
if dist[next] == -1: # 未訪問なら
dist[next] = dist[q] + 1 # 「今のノードの距離+1」
Q.add(next)
```
%% DATAVIEW_PUBLISHER: start
```dataview
TABLE WITHOUT ID
file.link as child,
id
from "zk/core"
where meta(parent_id).display = this.id
SORT id ASC
```
%%
| child | id |
| ----- | -- |
%% DATAVIEW_PUBLISHER: end %%