Breadth-first search(BFS) Intuition:find the neighbors of the neighbors Additional structure:a queue Q ·Pseudocode: o Initialize: ·dist[s】=O;dist[u=∞for all other vertices u o Q=[s] o While Q is not empty Dequeue the top element u of Q 。For all neighbors v of u,if dist[v]=∞， o Put v in Q o Set dist[v]=dist[u]+1 ● ●
Breadth-first search (BFS) • Intuition: find the neighbors of the neighbors • Additional structure: a queue Q • Pseudocode: o Initialize: • dist[s] = 0; dist[u] = ∞ for all other vertices u o Q = [s] o While Q is not empty • Dequeue the top element u of Q • For all neighbors v of u, if dist[v] = ∞, o Put v in Q o Set dist[v] = dist[u] + 1
Dry run 。1:Initialize u dist[u] 1 ∞ Source 2 ∞ 3 0 4 02 5 30 ok 6 o 7 c ●6 。1 ●
Dry run • 1: Initialize 1 2 3 4 5 6 7 u dist[u] 1 ∞ 2 ∞ 3 0 4 ∞ 5 ∞ 6 ∞ 7 ∞ Source s
Dry run 2:Q=[s] Q 3 u dist[u] 1 ∞ 2 3 0 4 0 5 e 6 c∞ 30 7 c∞ ●6 01 ●
Dry run • 2: Q = [ s ] 1 2 3 4 5 6 7 u dist[u] 1 ∞ 2 ∞ 3 0 4 ∞ 5 ∞ 6 ∞ 7 ∞ Q 3 1 4 5 7
Dry run ·3:Dequeue Q u dist[u] 1 ∞ u=3 2 ∞ 3 0 4 ∞ 03 5 Jo OA 6 G∞ 7 c∞ ●6 01 ●
Dry run • 3: Dequeue 1 2 3 4 5 6 7 u dist[u] 1 ∞ 2 ∞ 3 0 4 ∞ 5 ∞ 6 ∞ 7 ∞ Q 3 1 4 5 7 u = 3
Dry run 。4:Find neighbors Q u dist[u] 1 0∞ u=3 2 ∞ 3 0 4 P 02 5 e 6 ∞ Jo 7 C∞ ●6 。1 ●
Dry run • 4: Find neighbors 1 2 3 4 5 6 7 u dist[u] 1 ∞ 2 ∞ 3 0 4 ∞ 5 ∞ 6 ∞ 7 ∞ Q 3 1 4 5 7 u = 3