Breadth First Search
Notes
- Note this algorithm is from CLRS and probably has more information that you are used to.
- π is the parent of a vertex
-
coloris the status of a vertex - d is the depth of a vertex in the bfs-tree
- We will use this information in future algorithms.
-
BFS(G,s) Input: a graph G = (V,E) s ∈ V, a starting point Output: a search tree all "reachable" vertexes labeled/identified information about the bfs-tree- for each vertex u ∈ G.V - {s}
- u.color = WHITE
- u.d = ∞
- u.π = NIL
- s.color = GRAY
- s.d = 0
- s.π = NIL
- Make an empty queue Q
- Q.enqueue(s)
- While not Q.isEmpty
- u = Q.Dequeue
- for each v ∈ G.Adj(u)
- if v.color == WHITE
- v.color = GRAY
- v.d = u.d + 1
- v.π = u
- Q.Enqueue(v)
- u.color = BLACK
- Trace with
- What does this do?
- Is it correct?
- What is the performance?