Breadth-first search: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 58: Line 58:
The variant is obviously fulfilled. Clearly, the first point of the invariant is only a notation, so nothing is to show.
The variant is obviously fulfilled. Clearly, the first point of the invariant is only a notation, so nothing is to show.


First consider the fourth point of the invariant: Let <math>p</math> be a path from <math>s</math> to some node that is not yet seen immerdiately after the current iteration. If <math>p</math> does not contain <math>v</math>, nothing is to show. So assume <math>p</math> contains <math>v</math>. Let <math>x</math> be the last node on <math>p</math> that is already seen immediately after the current iteration. If <math>x=v</math>, the claim follows from the fact that all unseen nodes <math>w\in V</math> with <math>(v,w)\in A</math> were put in <math>Q</math>. Otherwise, the claim follows from the induction hypothesis.
First consider the fourth point of the invariant: Let <math>p</math> be a path from some seen node outside <math>Q</math> to some node that is not yet seen immediately after the current iteration. If <math>p</math> does not contain <math>v</math>, nothing is to show. So assume <math>p</math> contains <math>v</math>. Let <math>x</math> be the last node on <math>p</math> that is already seen immediately after the current iteration. If <math>x=v</math>, the claim follows from the fact that all unseen nodes <math>w\in V</math> with <math>(v,w)\in A</math> were put in <math>Q</math>, so the immediate successor of <math>v</math> on <math>p</math> is in <math>Q</math> now. Otherwise, the claim follows from the induction hypothesis.


For the second point of the invariant, we have to show that the distance of <math>(v,w)</math>
For the second point of the invariant, we have to show that the distance of <math>(v,w)</math>

Revision as of 11:22, 10 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 (which is not unique, in general).

Auxiliary data: A FIFO queue [math]\displaystyle{ Q }[/math] whose elements are nodes in [math]\displaystyle{ V }[/math].

Invariant: Before and after each iteration:

  1. There is a current distance [math]\displaystyle{ k\in\mathbb{N} }[/math].
  2. All nodes with distance less than [math]\displaystyle{ k }[/math] are already seen.
  3. 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:
    1. 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].
    2. If [math]\displaystyle{ \ell\lt n }[/math] (that is, if there are nodes with distance [math]\displaystyle{ k+1 }[/math] in [math]\displaystyle{ Q }[/math]), all nodes with distance [math]\displaystyle{ k }[/math] are already seen.
  4. Each path from some seen node to some unseen node contains at least one node that is currently stored in [math]\displaystyle{ Q }[/math].

Basically, the fourth point means that the content of the queue is kind of a frontier line between the nodes that already left [math]\displaystyle{ Q }[/math] and the nodes that have not entered [math]\displaystyle{ Q }[/math] so far.

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 output sequence is empty.

Implementation: Obvious.

Proof: Obvious.

Induction step

Abstract view:

  1. Extract the first element [math]\displaystyle{ v }[/math] from [math]\displaystyle{ Q }[/math].
  2. For each outgoing arc [math]\displaystyle{ (v,w) }[/math] of [math]\displaystyle{ v }[/math] such that [math]\displaystyle{ w }[/math] is not yet seen:
    1. Label [math]\displaystyle{ w }[/math] as seen.
    2. Append [math]\displaystyle{ w }[/math] to [math]\displaystyle{ Q }[/math].
    3. Add [math]\displaystyle{ w }[/math] to [math]\displaystyle{ Q }[/math].

Implementation: Obvious.

Proof: The variant is obviously fulfilled. Clearly, the first point of the invariant is only a notation, so nothing is to show.

First consider the fourth point of the invariant: Let [math]\displaystyle{ p }[/math] be a path from some seen node outside [math]\displaystyle{ Q }[/math] to some node that is not yet seen immediately after the current iteration. If [math]\displaystyle{ p }[/math] does not contain [math]\displaystyle{ v }[/math], nothing is to show. So assume [math]\displaystyle{ p }[/math] contains [math]\displaystyle{ v }[/math]. Let [math]\displaystyle{ x }[/math] be the last node on [math]\displaystyle{ p }[/math] that is already seen immediately after the current iteration. If [math]\displaystyle{ x=v }[/math], the claim follows from the fact that all unseen nodes [math]\displaystyle{ w\in V }[/math] with [math]\displaystyle{ (v,w)\in A }[/math] were put in [math]\displaystyle{ Q }[/math], so the immediate successor of [math]\displaystyle{ v }[/math] on [math]\displaystyle{ p }[/math] is in [math]\displaystyle{ Q }[/math] now. Otherwise, the claim follows from the induction hypothesis.

For the second point of the invariant, we have to show that the distance of [math]\displaystyle{ (v,w) }[/math]


To see the invariant, first note that [math]\displaystyle{ v }[/math] has distance [math]\displaystyle{ k }[/math]. So, for every node [math]\displaystyle{ w }[/math] such that [math]\displaystyle{ (v,w)\in A }[/math], the distance of [math]\displaystyle{ w }[/math] is at most [math]\displaystyle{ k+1 }[/math]. By induction hypothesis (point 2 of the invariant), the distance of [math]\displaystyle{ w }[/math] is not less than [math]\displaystyle{ k }[/math]. This proves the second


We have to show: The distance of [math]\displaystyle{ w }[/math] is at least [math]\displaystyle{ k }[/math], and if there are nodes with distance [math]\displaystyle{ k+1 }[/math] in [math]\displaystyle{ Q }[/math], the distance of [math]\displaystyle{ w }[/math] is [math]\displaystyle{ k+1 }[/math].

First suppose for a contradiction that the distance of [math]\displaystyle{ w }[/math] is less than [math]\displaystyle{ k }[/math].

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 uG.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 vG.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