KARAN’S RELATIVES

CONCEPTS USED:

Greedy algorithm, Kruskal's algorithm.

DIFFICULTY LEVEL:

PROBLEM STATEMENT(SIMPLIFIED):

Karan's came home after a long time and he wants to visit all the relatives. The total number of Karan's's relatives is N and all of them are living in different cities. He can begin from any relative and visits all of them one after another. He doesn't know the cost of visiting all relative, so he asks you to find the minimum cost of visiting all relatives.
Note: solve this problem with the help of kruskal’s Algorithm.

See original problem statement here

For Example :

5 5
1 5 3
1 2 1
2 3 4
3 4 5
4 5 2

10

Karan starts from vertex (relative) 3,then goes to 2 (0+4), then 1 (0+4+1) ,then 5 (0+4+1+3) and then finally to relative 4 (0+4+1+3+2).
Therefore,the total minimum cost incurred is 10.

OBSERVATION:

The idea is simple, to visit all relatives by spending minimum cost means all vertices must be connected. So the two disjoint subsets of vertices must be connected to make a Spanning Tree. And they must be connected with the minimum weight edge to make it a Minimum Spanning Tree.

This is what Kruskal’s algorithm says in basic python programming.

SOLVING APPROACH:

Visiting all the relatives by spending minimum cost is very similar to finding the minimum spanning tree for the given graph(the path diagram between each).

Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest.[1] It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.[1] This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).

Follow these steps:
>1. Sort all the edges in non-decreasing order of their weight.
>
>2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it.
>
>3. Repeat step 2 until there are (N-1) edges in the spanning tree.

SOLUTIONS:

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

    using namespace std;
    const int MAX = 100001;
    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;
    }   

 import java.util.*; 
     import java.lang.*; 
     import java.io.*; 

     class Graph 
    { 
    class Edge implements Comparable<Edge> 
    { 
        int src, dest, weight; 
        public int compareTo(Edge compareEdge) 
        { 
            return this.weight-compareEdge.weight; 
        } 
    }; 
    class subset 
    { 
        int parent, rank; 
    }; 

    int V, E;   
    Edge edge[]; 
    Graph(int v, int e) 
    { 
        V = v; 
        E = e; 
        edge = new Edge[E]; 
        for (int i=0; i<e; ++i) 
            edge[i] = new Edge(); 
    } 
    int find(subset subsets[], int i) 
    { 
        if (subsets[i].parent != i) 
            subsets[i].parent = find(subsets, subsets[i].parent); 

        return subsets[i].parent; 
    } 

    void Union(subset subsets[], int x, int y) 
    { 
        int xroot = find(subsets, x); 
        int yroot = find(subsets, y); 

        if (subsets[xroot].rank < subsets[yroot].rank) 
            subsets[xroot].parent = yroot; 
        else if (subsets[xroot].rank > subsets[yroot].rank) 
            subsets[yroot].parent = xroot; 
        else
        { 
            subsets[yroot].parent = xroot; 
            subsets[xroot].rank++; 
        } 
    } 
    void KruskalMST() 
    { 
        Edge result[] = new Edge[V];  // Tnis will store the resultant MST 
        int e = 0;  
        int i = 0;  
        for (i=0; i<V; ++i) 
            result[i] = new Edge(); 

        Arrays.sort(edge); 
        subset subsets[] = new subset[V]; 
        for(i=0; i<V; ++i) 
            subsets[i]=new subset(); 
        for (int v = 0; v < V; ++v) 
        { 
            subsets[v].parent = v; 
            subsets[v].rank = 0; 
        } 

        i = 0;  
        while (e < V - 1) 
        { 
            Edge next_edge = new Edge(); 
            next_edge = edge[i++]; 

            int x = find(subsets, next_edge.src); 
            int y = find(subsets, next_edge.dest); 
            if (x != y) 
            { 
                result[e++] = next_edge; 
                Union(subsets, x, y); 
            }  
        }  
    } 

Previous post BECOME KING
Next post FIND SHELTER

Leave a Reply

Your email address will not be published. Required fields are marked *