Prims Algorithm: Difference between revisions

From Rice Wiki
(:q)
No edit summary
Line 24: Line 24:


= Proof: Greedy =
= Proof: Greedy =
'''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>.
'''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>.


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

Revision as of 01:34, 8 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 .