Graphs/Breadth First Traversal: Difference between revisions
From charlesreid1
(Created page with "Also see BFS =Notes= =Resources= ==Flags== {{GraphsFlag}} Category:BFS") |
No edit summary |
||
| Line 3: | Line 3: | ||
=Notes= | =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. | |||
=Resources= | =Resources= | ||
Revision as of 13:40, 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.
Resources
Flags
