Prims Algorithm: Difference between revisions

From Rice Wiki
No edit summary
 
(11 intermediate revisions by the same user not shown)
Line 1: Line 1:
{{Infobox Algorithm|class=[[Minimum_Spanning_Tree]] <br> [[Graph Algorithm]] <br> [[Greedy Algorithm]]|runtime=Heap: O(E log V) <br> Array: O(V^2)}}
{{Infobox Algorithm|class=[[Minimum_Spanning_Tree]] <br> [[Graph Algorithm]] <br> [[Greedy Algorithm]]| runtime=V*Extract_min + V + E + E update <br> Heap: O(E log V) <br> Array: O(V^2)}}
== Approach: Greedy ==
The approach is to try to add the smallest edges as long as they do not create a cycle; add an edge to the tree that is minimum across the cut of <math>T</math> vs. <math>V - T</math>. Unlike [[Dijkstra's Algorithm|Dijkstra's algorithm]], the weight of the crossing edge is directly considered (as opposed to the distance from the source node).


= Approach: Greedy =
Given the MST of <math>V_{n - m} = v_1, v_2, \ldots, v_{ n - m} </math>, the MST of <math>V</math> should be that of <math>V_{n-1}</math> plus the edge that connects to <math>v_n</math> that is the shortest.
See [[Minimum_Spanning_Tree]]
 
<math>
OPT(n) = OPT(n-1) + min( (v_i, v_n) \in E )
</math>


= Implementation =
= Implementation =
Line 21: Line 26:


= Analysis =
= Analysis =
Priority queue is slower than array when the graph is dense, so sometimes it's better to use Dijsktra's algorithm.
Initialization takes O(V). Walk through is O(V + E).
 
During the walk through, the minimum edge is extracted V times, and the edge priority queue is updated E times. Depending on the data structure used, the runtime is different.
 
* For an ''array'', the extraction takes O(V) and the update takes O(1). The overall runtime is O(V^2)
* For a ''heap'', the extraction takes O(logV) and the update takes O(logV). The overall runtime is O(E logV).
 
As such, priority queue is slower than array when the graph is dense (where E approaches V^2).


= Proof: Greedy =
= Proof: Greedy =


== Suboptimality ==
'''Greeedy strategy:''' Let the greedy choice be the edge that is
smallest that crosses the cut between <math>A</math> and <math>V -
A</math>.


Given MST tree for the graph G
'''Name greedy choice:''' let <math>r \rightarrow x</math> be the
smallest edge that crosses the cut from <math>A = r</math> and <math>V -
r</math>.


<math>
Given an optimal solution with (r,y), prove that <math>A = OPT - (r,y) +
OPT = \text{set of edges}
(r, x)</math> is still optimal.
</math>


where the number of edges is <math>n - 1</math>, the weight of edges is
<math>A</math> is still a tree since there is no cycles created.
minimum, and the tree is spanning.


Let <math>(x,y)</math> be a leaf edge in the tree.
<math>w(r,y) \geq w(r,x)</math> due to its properties as the greedy
choice.


Therefore, <math>A</math> must be optimal.


[[Category:Algorithms]]
[[Category:Algorithms]]

Latest revision as of 17:56, 20 March 2024

Approach: Greedy

The approach is to try to add the smallest edges as long as they do not create a cycle; add an edge to the tree that is minimum across the cut of vs. . Unlike Dijkstra's algorithm, the weight of the crossing edge is directly considered (as opposed to the distance from the source node).

Given the MST of , the MST of should be that of plus the edge that connects to that is the shortest.

Implementation

for each u in V:
    key[u] = infinity   // cost array
    pi[u] = infinity    // from array
Q = new PriorityQueue(V)
key[root] = 0
while Q is not empty:
    u = extractMin(Q)
    # Reduce nodes
    for v in adj[u]:
        if v in Q and w[u,v] < key[v]:
            key[v] = w[u,v]

Analysis

Initialization takes O(V). Walk through is O(V + E).

During the walk through, the minimum edge is extracted V times, and the edge priority queue is updated E times. Depending on the data structure used, the runtime is different.

  • For an array, the extraction takes O(V) and the update takes O(1). The overall runtime is O(V^2)
  • For a heap, the extraction takes O(logV) and the update takes O(logV). The overall runtime is O(E logV).

As such, priority queue is slower than array when the graph is dense (where E approaches V^2).

Proof: Greedy

Greeedy strategy: Let the greedy choice be the edge that is smallest that crosses the cut between and .

Name greedy choice: let be the smallest edge that crosses the cut from and .

Given an optimal solution with (r,y), prove that is still optimal.

is still a tree since there is no cycles created.

due to its properties as the greedy choice.

Therefore, must be optimal.