Prims Algorithm: Difference between revisions

From Rice Wiki
No edit summary
No edit summary
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)}}<aside class="portable-infobox noexcerpt pi-background pi-theme-default pi-layout-stacked">
{{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)}}
== Prims Algorithm ==
</aside><span></span>


= Approach: Greedy =
= Approach: Greedy =

Revision as of 23:54, 12 March 2024

Approach: Greedy

See Minimum_Spanning_Tree

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.