Graphs/Breadth First Traversal: Difference between revisions
From charlesreid1
| Line 13: | Line 13: | ||
<pre> | <pre> | ||
def bfs(g, s, discovered): | def bfs(g, s, discovered): | ||
discovered = empty map | |||
create new queue | |||
queue.add(s) | |||
while queue is not empty: | |||
u = queue.pop() | |||
for e in incident_edges(u): | |||
v = opposite_edge(u, e) | |||
if v not in discovered: | |||
// add (v,e) to discovered | |||
discovered[v] = e | |||
queue.add(v) | |||
</pre> | </pre> | ||
Revision as of 11:25, 9 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.
Pseudocode
def bfs(g, s, discovered):
discovered = empty map
create new queue
queue.add(s)
while queue is not empty:
u = queue.pop()
for e in incident_edges(u):
v = opposite_edge(u, e)
if v not in discovered:
// add (v,e) to discovered
discovered[v] = e
queue.add(v)
Related
Graphs:
- Graphs#Graph Traversals
- Graphs/Depth First Traversal
- Graphs/Breadth First Traversal
- Graphs/Euler Tour
- Graphs/Euler Circuit
Traversals on trees:
Breadth-first search and traversal on trees:
Depth-first search and traversal on trees:
OOP design patterns:
Flags
