• Home
  • /
  • Blog
  • /
  • मिनिमम स्पॅनिंग ट्रीज़ के लिए 2 बुनियादी एल्गोरिदम

मिनिमम स्पॅनिंग ट्रीज़ के लिए 2 बुनियादी एल्गोरिदम

Minimum Spanning Trees

This post is also available in: English (English) العربية (Arabic)

एक नए इलाके में केबल बिछाने वाली केबल टीवी कंपनी के परिदृश्य पर विचार करें। इसके साथ बाधा यह है कि यह केवल कुछ रास्तों के साथ केबल को दफन कर सकता है, फिर एक ग्राफ होगा जो उन रास्तों से जुड़ा होता है।

इनमें से कुछ रास्ते अधिक महंगे हो सकते हैं, क्योंकि वे लंबे होते हैं, या केबल को गहराई से दफन करने की आवश्यकता होती है; इन रास्तों को बड़े वज़न वाले किनारों द्वारा दर्शाया जाएगा।

उस ग्राफ़ के लिए एक स्पॅनिंग ट्री उन पथों का एक सबसेट है जिसमें कोई चक्र नहीं है लेकिन फिर भी हर घर से जुड़ता है। कई स्पॅनिंग ट्रीज़ हो सकते हैं। कम से कम कुल लागत वाला मिनिमम स्पॅनिंग ट्री होगा।

मिनिमम स्पॅनिंग ट्री क्या है?

मिनिमम स्पॅनिंग ट्री मूल रूप से एक ट्री होता है। यह अन्य ट्री से अलग होता है, क्योंकि यह किनारों से जुड़े भार को कम करता है। ग्राफ कैसा दिखता है इसके आधार पर, एक से अधिक मिनिमम स्पॅनिंग ट्री हो सकते हैं।

एक ग्राफ में जहां सभी किनारों का वजन समान होता है, प्रत्येक ट्री मिनिमम स्पॅनिंग ट्री होते हैं। यदि सभी किनारों में अलग-अलग वजन है (यानी, एक ही वजन के साथ दो किनारे नहीं हैं), तो वह सही मायने में एक मिनिमम स्पॅनिंग ट्री है। दूसरी ओर, यदि सभी किनारों में अलग-अलग वज़न नहीं है (कुछ किनारों पर अलग-अलग वज़न और कुछ समान वज़न के साथ), तो एक से अधिक मिनिमम स्पॅनिंग ट्री होंगे।

मिनिमम स्पॅनिंग ट्रीज़
मिनिमम स्पॅनिंग ट्री

मिनिमम स्पॅनिंग ट्री खोजने की क्या आवश्यकता है?

ग्राफ सिद्धांत से कई समस्याओं को मिनिमम स्पॅनिंग ट्री प्रोब्लेम्स कहा जाता है। ग्राफ सिद्धांत में, एक ट्री सभी कोने को एक साथ जोड़ने का एक तरीका है, ताकि किसी भी शीर्ष पर, ट्री के किसी भी अन्य शीर्ष से एक ही रास्ता हो।

यदि ग्राफ़ सड़कों से जुड़े कई शहरों का प्रतिनिधित्व करता है, तो कोई भी कई सड़कों का चयन कर सकता है, ताकि प्रत्येक शहर को एक दूसरे से पहुंचा जा सके, लेकिन एक शहर से दूसरे शहर में जाने के लिए एक से अधिक मार्ग नहीं है।

एक ग्राफ में एक से अधिक स्पॅनिंग ट्री हो सकते हैं, जैसे शहरों के बीच सड़कों का चयन करने के लिए एक से अधिक तरीके हो सकते हैं।

अधिकांश समय, ग्राफ़ भारित होते हैं; दो शहरों के बीच प्रत्येक कनेक्शन का भार होता है। यह दूरी, परिवहन की लागत या यात्रा करने का समय हो सकता है।

मिनिमम स्पॅनिंग ट्री खोजने के लिए एल्गोरिदम

न्यूनतम स्पैनिंग ट्री खोजने के लिए दो प्रसिद्ध एल्गोरिदम हैं।

क्रुक्साल एल्गोरिथम

यह पेड़ को किनारों पर एक-एक करके बढ़ते हुए स्पॅनिंग ट्री बनाता है। Kruksal’s algorithm follows a greedy approach as in each iteration it finds an edge that has the least weight and adds it to the growing spanning tree.

Steps in Kruksal’s algorithm

  • Sort the graph edges with respect to their weights.
  • Start adding edges to the Minimum Spanning Tree from the edge with the smallest weight until the edge of the largest weight.
  • Only add edges that don’t form a cycle, edges that connect only disconnected components.

In Kruskal’s algorithm, at each iteration, we will select the edge with the lowest weight. So, we will start with the lowest weighted edge first i.e., the edges with weight 1.

After that, we will select the second-lowest weighted edge i.e., edge with weight 2. Notice these two edges are totally disjoint.

Now, the next edge will be the third-lowest weighted edge i.e., edge with weight 3, which connects the two disjoint pieces of the graph.

Now, we are not allowed to pick the edge with weight 4, which will create a cycle and we can’t have any cycles. So we will select the fifth-lowest weighted edge i.e., edge with weight 5. Now the other two edges will create cycles so we will ignore them. In the end, we end up with a minimum spanning tree with total cost 11 ( = 1 + 2 + 3 + 5).

मिनिमम स्पॅनिंग ट्रीज़
Kruksal’s algorithm

C++ Program to Implement Kruksal’s Algorithm

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;
const int MAX = 1e4 + 5;
int id[MAX], nodes, edges;
pair <long long, pair<int, int> > p[MAX];

void initialize()
{
    for(int i = 0;i < MAX;++i)
        id[i] = i;
}

int root(int x)
{
    while(id[x] != x)
    {
        id[x] = id[id[x]];
        x = id[x];
    }
    return x;
}

void union1(int x, int y)
{
    int p = root(x);
    int q = root(y);
    id[p] = id[q];
}

long long kruskal(pair<long long, pair<int, int> > p[])
{
    int x, y;
    long long cost, minimumCost = 0;
    for(int i = 0;i < edges;++i)
    {
        // Selecting edges one by one in increasing order from the beginning
        x = p[i].second.first;
        y = p[i].second.second;
        cost = p[i].first;
        // Check if the selected edge is creating a cycle or not
        if(root(x) != root(y))
        {
            minimumCost += cost;
            union1(x, y);
        }    
    }
    return minimumCost;
}

int main()
{
    int x, y;
    long long weight, cost, minimumCost;
    initialize();
    cin >> nodes >> edges;
    for(int i = 0;i < edges;++i)
    {
        cin >> x >> y >> weight;
        p[i] = make_pair(weight, make_pair(x, y));
    }
    // Sort the edges in the ascending order
    sort(p, p + edges);
    minimumCost = kruskal(p);
    cout << minimumCost << endl;
    return 0;
}

Prim’s Algorithm

Prim’s Algorithm also use Greedy approach to find the minimum spanning tree. In Prim’s Algorithm we grow the spanning tree from a starting position. Unlike an edge in Kruskal’s, we add vertex to the growing spanning tree in Prim’s.

Steps in Prim’s algorithm

  • Maintain two disjoint sets of vertices. One containing vertices that are in the growing spanning tree and other that are not in the growing spanning tree.
  • Select the cheapest vertex that is connected to the growing spanning tree and is not in the growing spanning tree and add it into the growing spanning tree. This can be done using Priority Queues. Insert the vertices, that are connected to growing spanning tree, into the Priority Queue.
  • Check for cycles. To do that, mark the nodes which have been already selected and insert only those nodes in the Priority Queue that are not marked.

In Prim’s Algorithm, we will start with an arbitrary node (it doesn’t matter which one) and mark it. In each iteration we will mark a new vertex that is adjacent to the one that we have already marked.

As a greedy algorithm, Prim’s algorithm will select the cheapest edge and mark the vertex. So we will simply choose the edge with weight 1. In the next iteration, we have three options, edges with weight 2, 3, and 4. So, we will select the edge with weight 2 and mark the vertex. Now again we have three options, edges with weight 3, 4, and 5. But we can’t choose an edge with weight 3 as it is creating a cycle. So we will select the edge with weight 4 and we end up with the minimum spanning tree of total cost 7 ( = 1 + 2 +4).

मिनिमम स्पॅनिंग ट्रीज़
Prim’s algorithm

C++ Program to Implement Prim’s Algorithm

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <utility>

using namespace std;
const int MAX = 1e4 + 5;
typedef pair<long long, int> PII;
bool marked[MAX];
vector <PII> adj[MAX];

long long prim(int x)
{
    priority_queue<PII, vector<PII>, greater<PII> > Q;
    int y;
    long long minimumCost = 0;
    PII p;
    Q.push(make_pair(0, x));
    while(!Q.empty())
    {
        // Select the edge with minimum weight
        p = Q.top();
        Q.pop();
        x = p.second;
        // Checking for cycle
        if(marked[x] == true)
            continue;
        minimumCost += p.first;
        marked[x] = true;
        for(int i = 0;i < adj[x].size();++i)
        {
            y = adj[x][i].second;
            if(marked[y] == false)
                Q.push(adj[x][i]);
        }
    }
    return minimumCost;
}

int main()
{
    int nodes, edges, x, y;
    long long weight, minimumCost;
    cin >> nodes >> edges;
    for(int i = 0;i < edges;++i)
    {
        cin >> x >> y >> weight;
        adj[x].push_back(make_pair(weight, y));
        adj[y].push_back(make_pair(weight, x));
    }
    // Selecting 1 as the starting node
    minimumCost = prim(1);
    cout << minimumCost << endl;
    return 0;
}

Applications of Minimum Spanning Trees

  • Minimum spanning trees are used for network designs (i.e., telephone or cable networks). They are also used to find approximate solutions for complex mathematical problems like the ‘Traveling Salesman Problem”.
  • Cluster Analysis
  • Real-time face tracking and verification (i.e., locating human faces in a video stream)
  • Protocols in computer science to avoid network cycles
  • Entropy-based image registration
  • Dithering (adding white noise to a digital recording in order to reduce distortion)
  • Handwriting recognition
  • Image segmentation

Image Credit: Background vector created by vector_corp – www.freepik.com

{"email":"Email address invalid","url":"Website address invalid","required":"Required field missing"}
>