Minimum Spanning Tree यानि Prim Algorithm

Prim का algorithm एक house से एक network बढ़ाने जैसा है, हमेशा सबसे सस्ती pipe जोड़ते हुए जो एक नए house तक पहुंचे।

In this page:

What is Prim
Key Values
Visited Set
Example
Complexity

Syntax

markup

import heapq
visited = set()
heap = [(0, start)]
while heap:
    w, u = heapq.heappop(heap)
    if u in visited:
        continue
    visited.add(u)
    total += w
    for v, weight in graph[u]:
        if v not in visited:
            heapq.heappush(heap, (weight, v))

What is Prim

Prim का algorithm भी एक minimum spanning tree बनाता है, लेकिन Kruskal की तरह globally सभी edges consider करने के बजाय, यह एक single starting vertex से बाहर की ओर एक connected tree बढ़ाता है, हमेशा सबसे सस्ती available edge के साथ extend करते हुए।

उदाहरण: What is Prim

#include <iostream>
using namespace std;
int main() {
	cout << "Prim: grow one tree outward from a start vertex, always extending along the cheapest edge out";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Prim: grow one tree outward from a start vertex, always extending along the cheapest edge out");
	}
}

print("Prim: grow one tree outward from a start vertex, always extending along the cheapest edge out")

#include <stdio.h>
int main() {
	printf("Prim: grow one tree outward from a start vertex, always extending along the cheapest edge out");
	return 0;
}

Key Values

Tree के बाहर हर vertex एक key value रखता है — अब तक tree से इसे connect करने वाली सबसे सस्ती edge की weight — जो जब भी एक नया-जोड़ा गया tree vertex इसे एक सस्ता connection offer करे update होती है।

उदाहरण: Key Values

#include <iostream>
using namespace std;
int main() {
	int key[4] = {0, 1000000, 1000000, 1000000};
	int newEdgeWeight = 6, v = 2;
	if (newEdgeWeight < key[v]) { key[v] = newEdgeWeight; cout << "key[" << v << "] updated to " << key[v]; }
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] key = {0, 1000000, 1000000, 1000000};
		int newEdgeWeight = 6, v = 2;
		if (newEdgeWeight < key[v]) { key[v] = newEdgeWeight; System.out.println("key[" + v + "] updated to " + key[v]); }
	}
}

key = [0, 1000000, 1000000, 1000000]
new_edge_weight, v = 6, 2
if new_edge_weight < key[v]:
    key[v] = new_edge_weight
    print(f"key[{v}] updated to {key[v]}")

#include <stdio.h>
int main() {
	int key[4] = {0, 1000000, 1000000, 1000000};
	int newEdgeWeight = 6, v = 2;
	if (newEdgeWeight < key[v]) { key[v] = newEdgeWeight; printf("key[%d] updated to %d", v, key[v]); }
	return 0;
}

Visited Set

एक vertex बढ़ते tree में जोड़े जाते ही visited set में move हो जाता है, और उसके बाद सिर्फ उस set के बाहर की vertices अगली सबसे सस्ती edge के लिए candidates हैं, construction से tree को cycle-free रखते हुए।

उदाहरण: Visited Set

#include <iostream>
using namespace std;
int main() {
	bool inTree[4] = {true, false, false, false};
	inTree[1] = true;
	cout << "Vertex 1 moved into tree; only vertices outside {0,1} are now candidates";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		boolean[] inTree = {true, false, false, false};
		inTree[1] = true;
		System.out.println("Vertex 1 moved into tree; only vertices outside {0,1} are now candidates");
	}
}

in_tree = [True, False, False, False]
in_tree[1] = True
print("Vertex 1 moved into tree; only vertices outside {0,1} are now candidates")

#include <stdio.h>
int main() {
	int inTree[4] = {1, 0, 0, 0};
	inTree[1] = 1;
	printf("Vertex 1 moved into tree; only vertices outside {0,1} are now candidates");
	return 0;
}

Example

Tree को एक single city से शुरू होने की कल्पना करें, फिर बार-बार जिस भी neighboring city का tree में पहले से मौजूद किसी भी city तक सबसे सस्ता road हो उसे annex करते हुए, जब तक हर city न जुड़ जाए।

उदाहरण: Example

#include <iostream>
using namespace std;
int main() {
	cout << "Tree starts as one city, repeatedly annexes the cheapest-connected neighboring city";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Tree starts as one city, repeatedly annexes the cheapest-connected neighboring city");
	}
}

print("Tree starts as one city, repeatedly annexes the cheapest-connected neighboring city")

#include <stdio.h>
int main() {
	printf("Tree starts as one city, repeatedly annexes the cheapest-connected neighboring city");
	return 0;
}

Complexity

एक straightforward implementation जो हर round minimum ढूंढने के लिए सभी key values scan करता है O(V²) लेता है, dense graphs के लिए well-suited; candidate edges track करने के लिए इसके बजाय एक min-heap उपयोग करना sparse graphs को O(E log V) तक लाता है।

उदाहरण: Complexity

#include <iostream>
using namespace std;
int main() {
	cout << "Prim: O(V^2) naive scan for dense graphs; O(E log V) with a min-heap for sparse graphs";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Prim: O(V^2) naive scan for dense graphs; O(E log V) with a min-heap for sparse graphs");
	}
}

print("Prim: O(V^2) naive scan for dense graphs; O(E log V) with a min-heap for sparse graphs")

#include <stdio.h>
int main() {
	printf("Prim: O(V^2) naive scan for dense graphs; O(E log V) with a min-heap for sparse graphs");
	return 0;
}

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson Minimum Spanning Tree Kruskal Next Lesson → DP Introduction and Memoization