Prim: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 1: Line 1:
'''Algorithmic problem:''' Minimum spanning tree
'''Algorithmic problem:''' [[Minimum spanning tree]]


'''Prerequisites:'''
'''Prerequisites:'''
Line 6: Line 6:


'''Auxiliary data:'''
'''Auxiliary data:'''
#A key for each node .
#A key <math>k_v \in \mathbb{R}</math> for each node <math>v \in V</math>.
#A priority queue of nodes. The key of a node for is , the information is one of the edges of that is incident to .
#A priority queue <math>Q</math> of nodes. The key of a node <math>v</math> for <math>Q</math> is <math>k_v</math>, the information is one of the edges of <math>G</math> that is [[incident]] to <math>v</math>.


==Abstract view==
==Abstract view==


'''Invariant:''' After iterations:
'''Invariant:''' After <math>i \geq 0</math> iterations:
#There is a node set of size and an edge set such that solely connects nodes in , and is a tree.
#There is a node set <math>V_i</math> of size <math>\vert V_i \vert = i+1</math> and an edge set <math>E_i \subseteq E</math> such that <math>E_i</math> solely connects nodes in <math>V_i</math>, and <math>V(V_i,E_i)</math> is a tree.
#There is a minimum spanning tree of such that .
#There is a minimum spanning tree <math>(V,E'_i)</math> of <math>G</math> such that <math>E_i \subseteq E'_i</math>.
#The key of is the minimal length of an edge that connects with some node in (or , if there is no such edge). If and , this edge is the information associated with in .
#The key <math>k_v</math> of <math>v \in V \setminus V_i</math> is the minimal length of an edge that connects <math>v</math> with some node in <math>V_i</math> (or <math>K_v = +\infty</math>, if there is no such edge). If <math>v \in Q</math> and <math>K_v < +\infty</math>, this edge is the information associated with <math>v</math> in <math>Q</math>.
Note that, once a node joins , its key will be irrelevant for the rest of the algorithm.
Note that, once a node joins <math>V_i</math>, its key will be irrelevant for the rest of the algorithm.
'''Variant:'''   increases by .
 
'''Break condition:'''  ; then return .
'''Variant:''' <math>i</math> increases by <math>1</math>.
 
'''Break condition:'''  <math>i = n - 1</math>; then return <math>E_{n-1}</math>.


==Induction basis==
==Induction basis==


'''Abstract view:'''
'''Abstract view:'''
#Choose an arbitrary node and set .
#Choose an arbitrary node <math>s \in V</math> and set <math>V_0 := \{s\}</math>.
#For each node :
#For each node <math>v \in V \setminus \{s\}</math>:
##If , set , otherwise set .
##If <math>\{s,v\} \in E</math>, set <math>k_v := \ell(\{s,v\})</math>, otherwise set <math>k_v := + \infty</math>.
##Insert with key in .
##Insert <math>v</math> with key <math>k_v</math> in <math>Q</math>.
'''Implementation:''' Obvious.
'''Implementation:''' Obvious.
'''Proof:''' Obvious.
'''Proof:''' Obvious.


Line 32: Line 35:


'''Abstract view:'''
'''Abstract view:'''
#Extract the first node from .
#Extract the first node <math>v</math> from <math>Q</math>.
#Let denote the edge stored as information for in .
#Let <math>e</math> denote the edge stored as information for <math>v</math> in <math>Q</math>.
#For each such that and :
#For each <math>w \in V \setminus <math>Insert formula here</math>V_{i-1}</math> such that <math>\{v,w\} \in E</math> and <math>\ell(\{v,w\}) < k_w</math>:
##Set as the new information for in .
##Set <math>\{v,w\}</math> as the new information for <math>w</math> in <math>Q</math>.
##Set .
##Set <math>k_w := \ell(\{v,w\})</math>.
##Rearrange according to the decreased key .
##Rearrange <math>Q</math> according to the decreased key <math>k_w</math>.
#.
#<math>E_i := E_{i-1} \cup \{e\}</math>.
#.
#<math>V_i := V_{i-1} \cup \{v\}</math>.
'''Implementation:''' Obvious.
'''Implementation:''' Obvious.
'''Correctness:''' The first and third invariants are obviously maintained, so we will focus on the second invariant. Let denote the other endnode of , so it is .  
 
Since is a spanning tree of , there is exactly one path in connecting and . As is cycle-free and contains the tree , contains exactly one edge such that and . If (and thus ), the invariant is maintained by . So consider the case that .  
'''Correctness:''' The first and third invariants are obviously maintained, so we will focus on the second invariant. Let <math>u \in V_{i-1}</math> denote the other endnode of <math>e</math>, so it is <math>e = \{u,v\}</math>.  
Note that immediately before the -th iteration. Therefore, the specific choice of  implies . So, with we obtain a spanning tree of whose weight is not larger than that of , which is minimum by definition.
 
Since <math>(V,E'_{i-1})</math> is a spanning tree of <math>G</math>, there is exactly one [[path]] <math>p</math> in <math>(V,E'_{i-1}</math> connecting <math>u</math> and <math>v</math>. As <math>(V,E'_{i-1})</math> is cycle-free and contains the tree <math>(V_{i-1},E_{i-1})</math>, <math>p</math> contains exactly one edge <math>e' = \{v',w'\} \in E'_{i-1}</math> such that <math>v' \in V_{i-1}</math> and <math>w' \notin V_{i-1}</math>. If <math>e' = e</math> (and thus <math>p = (e)</math>), the invariant is maintained by <math>E'_i := E'_{i-1}</math>. So consider the case that <math>e' \neq e</math>.  
 
Note that <math>e' \in Q</math> immediately before the <math>i</math>-th iteration. Therefore, the specific choice of  implies <math>\ell(e') \geq \ell(e)</math>. So, with <math>E'_i := E'_{i-1} \setminus \{e'\} \cup \{e\}</math> we obtain a spanning tree of <math>G</math> whose weight is not larger than that of <math>(V,E'_{i-1})</math>, which is minimum by definition.


==Complexity==
==Complexity==


'''Statement:'''   in the worst case, where and and is the asymptotic complexity of the methods of .
'''Statement:''' <math>\mathcal{O}((n+m) \cdot T(n))</math> in the worst case, where <math>n = \vert V \vert</math> and <math>m = \vert A \vert</math> and <math>T(n)</math> is the asymptotic complexity of the methods of <math>Q</math> .


'''Proof:''' In the preprocessing, nodes are to be inserted in , which takes time. Since each node is inserted at most once, all extraction operations take time, too. For each edge, has to be rearranged at most once, which results in time. Clearly, all other operations of the preprocessing and the main loop are dominated by these bounds as well.
'''Proof:''' In the preprocessing, <math>n - 1</math> nodes are to be inserted in <math>Q</math>, which takes <math>\mathcal{O}(n \cdot T(n))</math> time. Since each node is inserted at most once, all extraction operations take <math>\mathcal{O}(n \cdot T(n))</math> time, too. For each edge, <math>Q</math> has to be rearranged at most once, which results in <math>\mathcal{O}(m \cdot T(n))</math> time. Clearly, all other operations of the preprocessing and the main loop are dominated by these bounds as well.

Revision as of 00:25, 17 June 2015

Algorithmic problem: Minimum spanning tree

Prerequisites:

Type of algorithm: loop

Auxiliary data:

  1. A key [math]\displaystyle{ k_v \in \mathbb{R} }[/math] for each node [math]\displaystyle{ v \in V }[/math].
  2. A priority queue [math]\displaystyle{ Q }[/math] of nodes. The key of a node [math]\displaystyle{ v }[/math] for [math]\displaystyle{ Q }[/math] is [math]\displaystyle{ k_v }[/math], the information is one of the edges of [math]\displaystyle{ G }[/math] that is incident to [math]\displaystyle{ v }[/math].

Abstract view

Invariant: After [math]\displaystyle{ i \geq 0 }[/math] iterations:

  1. There is a node set [math]\displaystyle{ V_i }[/math] of size [math]\displaystyle{ \vert V_i \vert = i+1 }[/math] and an edge set [math]\displaystyle{ E_i \subseteq E }[/math] such that [math]\displaystyle{ E_i }[/math] solely connects nodes in [math]\displaystyle{ V_i }[/math], and [math]\displaystyle{ V(V_i,E_i) }[/math] is a tree.
  2. There is a minimum spanning tree [math]\displaystyle{ (V,E'_i) }[/math] of [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ E_i \subseteq E'_i }[/math].
  3. The key [math]\displaystyle{ k_v }[/math] of [math]\displaystyle{ v \in V \setminus V_i }[/math] is the minimal length of an edge that connects [math]\displaystyle{ v }[/math] with some node in [math]\displaystyle{ V_i }[/math] (or [math]\displaystyle{ K_v = +\infty }[/math], if there is no such edge). If [math]\displaystyle{ v \in Q }[/math] and [math]\displaystyle{ K_v \lt +\infty }[/math], this edge is the information associated with [math]\displaystyle{ v }[/math] in [math]\displaystyle{ Q }[/math].

Note that, once a node joins [math]\displaystyle{ V_i }[/math], its key will be irrelevant for the rest of the algorithm.

Variant: [math]\displaystyle{ i }[/math] increases by [math]\displaystyle{ 1 }[/math].

Break condition: [math]\displaystyle{ i = n - 1 }[/math]; then return [math]\displaystyle{ E_{n-1} }[/math].

Induction basis

Abstract view:

  1. Choose an arbitrary node [math]\displaystyle{ s \in V }[/math] and set [math]\displaystyle{ V_0 := \{s\} }[/math].
  2. For each node [math]\displaystyle{ v \in V \setminus \{s\} }[/math]:
    1. If [math]\displaystyle{ \{s,v\} \in E }[/math], set [math]\displaystyle{ k_v := \ell(\{s,v\}) }[/math], otherwise set [math]\displaystyle{ k_v := + \infty }[/math].
    2. Insert [math]\displaystyle{ v }[/math] with key [math]\displaystyle{ k_v }[/math] in [math]\displaystyle{ Q }[/math].

Implementation: Obvious.

Proof: Obvious.

Induction step

Abstract view:

  1. Extract the first node [math]\displaystyle{ v }[/math] from [math]\displaystyle{ Q }[/math].
  2. Let [math]\displaystyle{ e }[/math] denote the edge stored as information for [math]\displaystyle{ v }[/math] in [math]\displaystyle{ Q }[/math].
  3. For each [math]\displaystyle{ w \in V \setminus \lt math\gt Insert formula here }[/math]V_{i-1}</math> such that [math]\displaystyle{ \{v,w\} \in E }[/math] and [math]\displaystyle{ \ell(\{v,w\}) \lt k_w }[/math]:
    1. Set [math]\displaystyle{ \{v,w\} }[/math] as the new information for [math]\displaystyle{ w }[/math] in [math]\displaystyle{ Q }[/math].
    2. Set [math]\displaystyle{ k_w := \ell(\{v,w\}) }[/math].
    3. Rearrange [math]\displaystyle{ Q }[/math] according to the decreased key [math]\displaystyle{ k_w }[/math].
  4. [math]\displaystyle{ E_i := E_{i-1} \cup \{e\} }[/math].
  5. [math]\displaystyle{ V_i := V_{i-1} \cup \{v\} }[/math].

Implementation: Obvious.

Correctness: The first and third invariants are obviously maintained, so we will focus on the second invariant. Let [math]\displaystyle{ u \in V_{i-1} }[/math] denote the other endnode of [math]\displaystyle{ e }[/math], so it is [math]\displaystyle{ e = \{u,v\} }[/math].

Since [math]\displaystyle{ (V,E'_{i-1}) }[/math] is a spanning tree of [math]\displaystyle{ G }[/math], there is exactly one path [math]\displaystyle{ p }[/math] in [math]\displaystyle{ (V,E'_{i-1} }[/math] connecting [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math]. As [math]\displaystyle{ (V,E'_{i-1}) }[/math] is cycle-free and contains the tree [math]\displaystyle{ (V_{i-1},E_{i-1}) }[/math], [math]\displaystyle{ p }[/math] contains exactly one edge [math]\displaystyle{ e' = \{v',w'\} \in E'_{i-1} }[/math] such that [math]\displaystyle{ v' \in V_{i-1} }[/math] and [math]\displaystyle{ w' \notin V_{i-1} }[/math]. If [math]\displaystyle{ e' = e }[/math] (and thus [math]\displaystyle{ p = (e) }[/math]), the invariant is maintained by [math]\displaystyle{ E'_i := E'_{i-1} }[/math]. So consider the case that [math]\displaystyle{ e' \neq e }[/math].

Note that [math]\displaystyle{ e' \in Q }[/math] immediately before the [math]\displaystyle{ i }[/math]-th iteration. Therefore, the specific choice of implies [math]\displaystyle{ \ell(e') \geq \ell(e) }[/math]. So, with [math]\displaystyle{ E'_i := E'_{i-1} \setminus \{e'\} \cup \{e\} }[/math] we obtain a spanning tree of [math]\displaystyle{ G }[/math] whose weight is not larger than that of [math]\displaystyle{ (V,E'_{i-1}) }[/math], which is minimum by definition.

Complexity

Statement: [math]\displaystyle{ \mathcal{O}((n+m) \cdot T(n)) }[/math] in the worst case, where [math]\displaystyle{ n = \vert V \vert }[/math] and [math]\displaystyle{ m = \vert A \vert }[/math] and [math]\displaystyle{ T(n) }[/math] is the asymptotic complexity of the methods of [math]\displaystyle{ Q }[/math] .

Proof: In the preprocessing, [math]\displaystyle{ n - 1 }[/math] nodes are to be inserted in [math]\displaystyle{ Q }[/math], which takes [math]\displaystyle{ \mathcal{O}(n \cdot T(n)) }[/math] time. Since each node is inserted at most once, all extraction operations take [math]\displaystyle{ \mathcal{O}(n \cdot T(n)) }[/math] time, too. For each edge, [math]\displaystyle{ Q }[/math] has to be rearranged at most once, which results in [math]\displaystyle{ \mathcal{O}(m \cdot T(n)) }[/math] time. Clearly, all other operations of the preprocessing and the main loop are dominated by these bounds as well.