Graphs/Breadth First Traversal: Difference between revisions
From charlesreid1
No edit summary |
|||
| Line 9: | Line 9: | ||
The fact that the BFS tree yields shortest paths is a natural consequence of how the BFS process works. | The fact that the BFS tree yields shortest paths is a natural consequence of how the BFS process works. | ||
= | =Related= | ||
Graphs: | |||
* [[Graphs/Depth First Traversal]] | |||
* [[Graphs/Breadth First Traversal]] | |||
* [[Graphs/Euler Tour]] | |||
Traversals on trees: | |||
* [[Trees/Preorder]] | |||
* [[Trees/Postorder]] | |||
* [[Trees/Inorder]] | |||
[[:Category:Traversal]] | |||
=Flags= | |||
{{GraphsFlag}} | {{GraphsFlag}} | ||
[[Category:BFS]] | [[Category:BFS]] | ||
[[Category:Traversal]] | |||
Revision as of 13:58, 7 September 2017
Also see BFS
Notes
What BFS Gets Us
Breadth-first search is important because it gets us the shortest path (the path with the fewest number of edges) from a vertex u to a vertex v. To state this more rigorously, a path in a breadth-first search tree rooted at vertex u to any other vertex v is guaranteed to be the shortest path from u to v (where shortest path denotes number of edges).
The fact that the BFS tree yields shortest paths is a natural consequence of how the BFS process works.
Related
Graphs:
Traversals on trees:
Flags
