AMAN RELATIVES

Last Updated on March 29, 2022 by Ria Pathak

CONCEPTS USED:

Greedy algorithm,Prim’s minimum spanning tree.

DIFFICULTY LEVEL:

Hard.

PROBLEM STATEMENT(SIMPLIFIED):

Aman came home after a long time and he wants to visit all the relatives. The total number of Aman’s relatives is N and all of them are living in different cities. He begins from the nearest 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 Prim’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

Aman 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 Prim’s algorithm says.

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).

In computer science, Prim’s (also known as Jarník’s) algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. 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. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

Follow these steps:

1. Initialize a tree with a single vertex, chosen arbitrarily from the graph.

2. Grow the tree by one edge: of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.

3. Repeat step 2 (until all vertices are in the tree).

Refer to the pseudo code:

visitedSet = {0};
UnvisitedSet = {1, 2, ..., N-1};
SpanningTree = {};
while ( UnvisitedSet ≠ empty )
    {
        Find edge e = (x, y) such that:
         1. x ∈ visitedSet
         2. y ∈ UnvisitedSet
         3. e has smallest cost
        SpanningTree = SpanningTree ∪ {e};
        visitedSet   = visitedSet ∪ {y};
        UnvisitedSet = UnvisitedSet - {y};
    }

SOLUTIONS:

#include <limits.h> 
    #include <stdbool.h> 
    #include <stdio.h> 
    #define V 10000
     int minKey(int key[], bool mstSet[]) 
    {  
    int min = INT_MAX, min_index; 

    for (int v = 0; v < V; v++) 
        if (mstSet[v] == false && key[v] < min) 
            min = key[v], min_index = v; 

    return min_index; 
    } 
    void primMST(int graph[V][V]) 
    { 
    int parent[V]; 
    int key[V]; 
    bool mstSet[V]; 
    for (int i = 0; i < V; i++) 
        key[i] = INT_MAX, mstSet[i] = false; 
    key[0] = 0; 
    parent[0] = -1;
    for (int count = 0; count < V - 1; count++) { 
        int u = minKey(key, mstSet); 
        mstSet[u] = true; 
        for (int v = 0; v < V; v++) 

            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) 
                parent[v] = u, key[v] = graph[u][v]; 
    } 
    printMST(parent, graph); 
    } 

#include <limits.h> 
    #include <stdbool.h> 
    #include <stdio.h> 
    #define V 10000
     int minKey(int key[], bool mstSet[]) 
    {  
    int min = INT_MAX, min_index; 

    for (int v = 0; v < V; v++) 
        if (mstSet[v] == false && key[v] < min) 
            min = key[v], min_index = v; 

    return min_index; 
    } 
    void primMST(int graph[V][V]) 
    { 
    int parent[V]; 
    int key[V]; 
    bool mstSet[V]; 
    for (int i = 0; i < V; i++) 
        key[i] = INT_MAX, mstSet[i] = false; 
    key[0] = 0; 
    parent[0] = -1;
    for (int count = 0; count < V - 1; count++) { 
        int u = minKey(key, mstSet); 
        mstSet[u] = true; 
        for (int v = 0; v < V; v++) 

            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) 
                parent[v] = u, key[v] = graph[u][v]; 
    } 
    printMST(parent, graph); 
    } 

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

    class MST { 
    private static final int V = 10000; 
    int minKey(int key[], Boolean mstSet[]) 
    { 
        int min = Integer.MAX_VALUE, min_index = -1; 

        for (int v = 0; v < V; v++) 
            if (mstSet[v] == false && key[v] < min) { 
                min = key[v]; 
                min_index = v; 
            } 

        return min_index; 
    }

    void primMST(int graph[][]) 
    { 
        int parent[] = new int[V]; 
        int key[] = new int[V]; 
        Boolean mstSet[] = new Boolean[V]; 
        for (int i = 0; i < V; i++) { 
            key[i] = Integer.MAX_VALUE; 
            mstSet[i] = false; 
        } 
        key[0] = 0; 
        parent[0] = -1;  
        for (int count = 0; count < V - 1; count++) { 
            int u = minKey(key, mstSet); 
            mstSet[u] = true; 

            for (int v = 0; v < V; v++) 

                if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] < key[v]) { 
                    parent[v] = u; 
                    key[v] = graph[u][v]; 
                } 
        } 
        printMST(parent, graph); 
    } 

This article tried to discuss the concept of Greedy algorithm. Hope this blog helps you understand and solve the problem. To practice more problems on Greedy algorithm you can check out MYCODE | Competitive Programming.