▴

न्यूनतम विस्तारित वृक्ष कैलकुलेटर

Kruskal's Algorithm · Prim's Algorithm · Graph Visualization

एक भारित undirected graph को edge list के रूप में दर्ज करें और Kruskal's और Prim's दोनों एल्गोरिदम का उपयोग करके MST की गणना करें। चरण-दर-चरण तालिका और canvas विज़ुअलाइज़ेशन देखें।

त्वरित उदाहरण (Quick Examples)

Spanning Tree क्या है?

एक connected undirected graph G = (V, E) का spanning tree एक subgraph है जिसमें सभी vertices V और edges का एक उपसमुच्चय शामिल है जो एक tree बनाता है — एक connected, acyclic graph। n vertices वाले graph के लिए, प्रत्येक spanning tree में ठीक n−1 edges होते हैं।

न्यूनतम विस्तारित वृक्ष (MST) क्या है?

एक न्यूनतम विस्तारित वृक्ष (MST) एक spanning tree है जिसका कुल edge भार graph के सभी spanning trees में न्यूनतम है। MST इस प्रश्न का उत्तर देता है: "सभी vertices को जोड़ने का सबसे सस्ता तरीका क्या है?" n vertices और m edges वाले graph के लिए, MST में ठीक n−1 edges हैं।

दो classical greedy algorithms इस समस्या को efficiently हल करते हैं: Kruskal का एल्गोरिदम और Prim का एल्गोरिदम। दोनों एक MST खोजने की गारंटी देते हैं।

Kruskal का एल्गोरिदम

Kruskal का एल्गोरिदम edges को globally process करता है, भार के अनुसार sort करके। यह प्रत्येक vertex को अपने component में रखकर प्रारंभ करता है और greedily सबसे सस्ती edge जोड़कर components को merge करता है।

चरण

  1. सभी edges को आरोही भार क्रम में sort करें।
  2. प्रत्येक vertex को अपने set के रूप में Union-Find (disjoint set) structure initialize करें।
  3. Sorted order में प्रत्येक edge (u, v, w) के लिए: यदि u और v अलग-अलग components में हैं, तो edge को MST में जोड़ें और दोनों components को union करें।
  4. जब n−1 edges जोड़ दिए जाएं तो रुकें।

Union-Find data structure के साथ path compression और union by rank cycle detection को लगभग O(1) प्रति edge बनाता है, Kruskal के एल्गोरिदम को O(E log E) समय complexity देता है।

Prim का एल्गोरिदम

Prim का एल्गोरिदम एक starting vertex से MST को बढ़ाता है, हमेशा वह सबसे सस्ती edge चुनता है जो current MST को एक ऐसे vertex से जोड़ती है जो अभी तक tree में नहीं है।

चरण

  1. किसी भी vertex से प्रारंभ करें; उसे visited mark करें।
  2. Current MST के सभी edges को min-priority queue में जोड़ें।
  3. Minimum-weight edge (u, v) निकालें जहाँ v unvisited है; उसे MST में जोड़ें।
  4. v को visited mark करें और उसकी edges enqueue करें। n−1 edges जुड़ने तक दोहराएं।

Binary heap के साथ Prim's O(E log V) में चलता है।

Kruskal's vs Prim's — तुलना

गुणKruskal'sPrim's
दृष्टिकोणGlobal edge sortVertex-by-vertex विस्तार
Data StructureUnion-FindMin-Heap / Priority Queue
Time ComplexityO(E log E)O(E log V)
सर्वश्रेष्ठSparse graphsDense graphs
प्रारंभ बिंदुकोई नहीं (सभी edges)चुना हुआ start vertex

MST की uniqueness

MST unique है यदि सभी edge weights distinct हैं। जब edges का एक समान भार होता है, तो एक समान कुल भार वाले कई MSTs मौजूद हो सकते हैं। हालांकि, कुल MST भार हमेशा unique रूप से निर्धारित होता है।

Disconnected Graphs — Spanning Forests

यदि graph disconnected है, तो कोई spanning tree अस्तित्व में नहीं है। इसके बजाय, प्रत्येक connected component का अपना MST होता है, और मिलकर वे एक न्यूनतम spanning forest बनाते हैं।

वास्तविक अनुप्रयोग

  • Network Design: न्यूनतम कुल cable लंबाई के साथ telephone, power, या internet network डिज़ाइन करना।
  • Cable/Pipeline बिछाना: शहरों को physical links से जोड़ने का सबसे सस्ता तरीका।
  • Cluster Analysis: Machine learning में single-linkage hierarchical clustering।
  • TSP Approximation: MST, metric Travelling Salesman Problem के लिए 2-approximation देता है।
  • Image Segmentation: Computer vision में pixel similarity graphs पर MST-based segmentation।
  • VLSI Circuit Design: Chip पर circuit components को जोड़ने वाले wire की लंबाई minimize करना।

अक्सर पूछे जाने वाले प्रश्न

न्यूनतम विस्तारित वृक्ष (MST) क्या है?
न्यूनतम विस्तारित वृक्ष एक connected weighted undirected graph का spanning tree है जिसमें सबसे छोटा संभव कुल edge भार है। इसमें graph के सभी n vertices n−1 edges से जुड़े हैं बिना किसी cycle के, और कोई अन्य spanning tree का edge weights का योग कम नहीं होता।
Kruskal और Prim एल्गोरिदम में क्या अंतर है?
Kruskal's globally काम करता है — सभी edges sort करता है और cycle न बनाने वाली edge greedily जोड़ता है। Sparse graphs के लिए O(E log E) समय efficient है। Prim's locally काम करता है — एक vertex से शुरू होकर, हमेशा unvisited node तक सबसे सस्ती edge चुनता है। Binary heap के साथ O(E log V) में चलता है, dense graphs के लिए उपयुक्त।
क्या प्रत्येक connected graph में MST होता है?
हाँ। प्रत्येक finite connected weighted undirected graph में कम से कम एक MST होता है। Disconnected graphs के लिए, प्रत्येक connected component अलग से एक MST रखता है, जो मिलकर एक minimum spanning forest बनाते हैं।
क्या MST हमेशा unique होता है?
MST unique है तब और केवल तब जब सभी edge weights distinct हों। Distinct weights होने पर Kruskal's और Prim's दोनों हमेशा एक ही edges चुनते हैं। जब कुछ edges का एक समान भार हो, तो एक ही कुल भार वाले कई MSTs हो सकते हैं।
Kruskal के एल्गोरिदम की time complexity क्या है?
Kruskal का एल्गोरिदम O(E log E) समय में चलता है, जहाँ E edges की संख्या है। Edges को sort करना dominant cost है। Union-Find operations, path compression और union by rank के साथ, O(E α(V)) में चलते हैं जहाँ α inverse Ackermann function है — effectively कोई भी practical input size के लिए 5 से कम constant है।
न्यूनतम विस्तारित वृक्ष के वास्तविक अनुप्रयोग क्या हैं?
MSTs engineering और computer science में हर जगह दिखते हैं: minimum-cost दूरसंचार और electrical grid layouts; शहरों के बीच cables, water pipes, या roads; machine learning में single-linkage hierarchical clustering; Travelling Salesman Problem के लिए 2-approximation solutions; computer vision में image segmentation; VLSI circuit layout में wire length minimize करना।
Spanning Forest क्या है?
Spanning forest, disconnected graphs के लिए spanning tree का सामान्यीकरण है। यह spanning trees का एक समुच्चय है, प्रत्येक connected component के लिए एक। यदि graph में n vertices और k connected components हैं, तो उसके minimum spanning forest में ठीक n−k edges हैं और सभी components में कुल भार minimize होता है।

संबंधित कैलकुलेटर

Dijkstra की सबसे छोटी पथ कैलकुलेटर
Adjacency Matrix कैलकुलेटर
Graph Coloring कैलकुलेटर
Hamiltonian Path Checker
रैखिक प्रोग्रामिंग सॉल्वर