Prims Algorithm: Difference between revisions

From Rice Wiki
No edit summary
Line 22: Line 22:
= Analysis =
= Analysis =
Priority queue is slower than array when the graph is dense, so sometimes it's better to use Dijsktra's algorithm.
Priority queue is slower than array when the graph is dense, so sometimes it's better to use Dijsktra's algorithm.
= Proof: Greedy =
== Suboptimality ==
Given MST tree for the graph G
<math>
OPT = set of edges
</math>
where the number of edges is <math>n - 1</math>, the weight of edges is
minimum, and the tree is spanning.
Let <math>(x,y)</math> be a leaf edge in the tree.
[[Category:Algorithms]]
[[Category:Algorithms]]

Revision as of 01:16, 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

Suboptimality

Given MST tree for the graph G

where the number of edges is , the weight of edges is minimum, and the tree is spanning.

Let be a leaf edge in the tree.