Prims Algorithm: Difference between revisions
Line 1: | Line 1: | ||
{{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)}} | {{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 == | == 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> | 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). | ||
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. | 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. |
Revision as of 17:47, 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
Priority queue is slower than array when the graph is dense, so sometimes it's better to use Dijsktra's algorithm.
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.