對比Tree Traversal的level order traversal，Graph Traversal的level order traversal稱為Breadth First Search，以寬度為優先遍歷的概念。

我們一樣用上一章節的graph來舉例，如果我們想要找出從s點到任意節點的最短距離，就可以使用Breadth First Search。

我們會需要一個queue來存放預計要做bfs的節點，而bfs時會找出neighbor，mark這些neighbor並紀錄edgeTo和distTo來紀錄路徑的走向跟距離。後續的節點在判斷neighbor時要判斷有沒有被mark過，避免把做過bfs的節點也丟到queue中：

比較一下各種traversal的遍歷順序：

BFS：012453687

DFS preorder：012543678

DFS postorder：347685210

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License