Breadth-first search: Difference between revisions
No edit summary |
No edit summary |
||
Line 19: | Line 19: | ||
'''Auxiliary data:''' | '''Auxiliary data:''' | ||
A queue <math>Q</math> whose elements are nodes in <math>V</math>. | A FIFO queue <math>Q</math> whose elements are nodes in <math>V</math>. | ||
'''Invariant:''' | '''Invariant:''' | ||
Line 38: | Line 38: | ||
'''Proof:''' Obvious. | '''Proof:''' Obvious. | ||
== Induction step == | == Induction step == | ||
Line 47: | Line 48: | ||
## Label <math>w</math> as seen. | ## Label <math>w</math> as seen. | ||
## Append <math>w</math> to <math>Q</math>. | ## Append <math>w</math> to <math>Q</math>. | ||
## Add <math> | ## Add <math>w</math> to <math>Q</math>. | ||
Line 55: | Line 56: | ||
The loop variant is obviously fulfilled. | The loop variant is obviously fulfilled. | ||
== Correctness == | == Correctness == | ||
It is easy to see that each operation of the algorithm is well defined. Due to the variant, the loop terminates after a finite number of steps | It is easy to see that each operation of the algorithm is well defined. Due to the variant, the loop terminates after a finite number of steps. | ||
== Complexity == | == Complexity == | ||
Line 71: | Line 68: | ||
'''Statement:''' The asymptotic complexity is in <math>\Theta(|V|+|A|)</math> in the best and worst case. | '''Statement:''' The asymptotic complexity is in <math>\Theta(|V|+|A|)</math> in the best and worst case. | ||
'''Proof:''' | '''Proof:''' | ||
Revision as of 18:37, 8 October 2014
General information
Algorithmic problem: Graph traversal
Type of algorithm: loop
Abstract view
Definition:‘‘‘ On this page, the distance of a node [math]\displaystyle{ v\in V }[/math] is the minimal number of arcs on a path from the start node [math]\displaystyle{ s }[/math] to [math]\displaystyle{ v }[/math].
Specific characteristic: The nodes are finished in the order of increasing distance.
Auxiliary data: A FIFO queue [math]\displaystyle{ Q }[/math] whose elements are nodes in [math]\displaystyle{ V }[/math].
Invariant: Before and after each iteration:
- There is a current distance [math]\displaystyle{ k\in\mathbb{N} }[/math].
- Let [math]\displaystyle{ n }[/math] denote the current size of [math]\displaystyle{ Q }[/math]. There is [math]\displaystyle{ \ell\in\{1,\ldots,n\} }[/math] such that the first [math]\displaystyle{ \ell }[/math] elements of [math]\displaystyle{ Q }[/math] have distance [math]\displaystyle{ k }[/math] and the last [math]\displaystyle{ n-\ell }[/math] elements have distance [math]\displaystyle{ k+1 }[/math].
Variant: One node is removed from [math]\displaystyle{ Q }[/math].
Break condition: [math]\displaystyle{ Q=\emptyset }[/math].
Induction basis
Abstract view: The start node is seen, no other node is seen. The start node is the only element of [math]\displaystyle{ Q }[/math]. The arborescence [math]\displaystyle{ T }[/math] is initialized so as to contain all nodes and no arcs.
Implementation: Obvious.
Proof: Obvious.
Induction step
Abstract view:
- Let [math]\displaystyle{ v }[/math] be the first element of [math]\displaystyle{ Q }[/math].
- Extract [math]\displaystyle{ v }[/math] from [math]\displaystyle{ Q }[/math].
- For all outgoing arcs [math]\displaystyle{ (v,w) }[/math] of [math]\displaystyle{ v }[/math], if [math]\displaystyle{ w }[/math] is not yet seen:
- Label [math]\displaystyle{ w }[/math] as seen.
- Append [math]\displaystyle{ w }[/math] to [math]\displaystyle{ Q }[/math].
- Add [math]\displaystyle{ w }[/math] to [math]\displaystyle{ Q }[/math].
Implementation: Obvious.
Proof: The loop variant is obviously fulfilled.
Correctness
It is easy to see that each operation of the algorithm is well defined. Due to the variant, the loop terminates after a finite number of steps.
Complexity
Statement: The asymptotic complexity is in [math]\displaystyle{ \Theta(|V|+|A|) }[/math] in the best and worst case.
Proof:
Pseudocode
BFS(G,s)
1 for each vertex u ∈ G.V - {s}
2 u.color = WHITE
3 u.d = ∞
4 u.π = NIL
5 s.color = GRAY
6 s.d = 0
7 s.π = NIL
8 Q = Ø
9 ENQUE(Q, s)
10 while Q ≠ Ø
11 u = DEQUEUE(Q)
12 for each v ∈ G.Adj[u]
13 if v.color == WHITE
14 v.color = GRAY
15 v.d = u.d + 1
16 v.π = u
17 ENQUEUE(Q, v)
18 u.color = BLACK