Prim's MST: Special Subtree

Given a graph which consists of several edges connecting its nodes, find a subgraph of the given graph with the following properties:

The subgraph contains all the nodes present in the original graph.
The subgraph is of minimum overall weight (sum of all edges) among all such subgraphs.
It is also required that there is exactly one, exclusive path between any two nodes of the subgraph.

One specific node is fixed as the starting point of finding the subgraph using Prim's Algorithm.
Find the total weight or the sum of all edges in the subgraph.

Example

Starting from node , select the lower weight edge, i.e. , weight .

Choose between the remaining edges, , weight , and , weight .

The lower weight edge is weight .

All nodes are connected at a cost of . The edge is not included in the subgraph.

Function Description

Complete the prims function in the editor below.

prims has the following parameter(s):

int n: the number of nodes in the graph
int edges[m][3]: each element contains three integers, two nodes numbers that are connected and the weight of that edge
int start: the number of the starting node

Returns

int: the minimum weight to connect all nodes in the graph

Input Format

The first line has two space-separated integers and , the number of nodes and edges in the graph.

Each of the next lines contains three space-separated integers , and , the end nodes of , and the edge's weight.
The last line has an integer , the starting node.

Constraints

There may be multiple edges between two nodes.

Sample Input 0

Sample Output 0

Explanation 0

The graph given in the test case is shown as :

The starting node is (in the given test case)

Applying the Prim's algorithm, edge choices available at first are :

(WT. 3) and (WT. 4) , out of which is chosen (smaller weight of edge).

Now the available choices are :

(WT. 4) , (WT. 5) , (WT. 2) and (WT. 6) , out of which is chosen by the algorithm.

Following the same method of the algorithm, the next chosen edges , sequentially are :

and .

Hence the overall sequence of edges picked up by Prim's are:

and the total weight of the MST (minimum spanning tree) is :

Solution

By Nadeesha Jayamanne

#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);

/*
 * Complete the 'prims' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER n
 *  2. 2D_INTEGER_ARRAY edges
 *  3. INTEGER start
 */

int prims(int n, vector<vector<int>> edges, int start) {
    vector<vector<pair<int, int>>> adj(n + 1);

    for (auto &edge : edges) {
        int u = edge[0];
        int v = edge[1];
        int w = edge[2];
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
    }

    vector<bool> visited(n + 1, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    pq.push(make_pair(0, start));
    int totalCost = 0;

    while (!pq.empty()) {
        pair<int, int> top = pq.top();
        pq.pop();

        int w = top.first;
        int u = top.second;

        if (visited[u]) continue;
        visited[u] = true;
        totalCost += w;

        for (size_t i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].first;
            int weight = adj[u][i].second;
            if (!visited[v]) {
                pq.push(make_pair(weight, v));
            }
        }
    }

    return totalCost;
}


int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string first_multiple_input_temp;
    getline(cin, first_multiple_input_temp);

    vector<string> first_multiple_input = split(rtrim(first_multiple_input_temp));

    int n = stoi(first_multiple_input[0]);

    int m = stoi(first_multiple_input[1]);

    vector<vector<int>> edges(m);

    for (int i = 0; i < m; i++) {
        edges[i].resize(3);

        string edges_row_temp_temp;
        getline(cin, edges_row_temp_temp);

        vector<string> edges_row_temp = split(rtrim(edges_row_temp_temp));

        for (int j = 0; j < 3; j++) {
            int edges_row_item = stoi(edges_row_temp[j]);

            edges[i][j] = edges_row_item;
        }
    }

    string start_temp;
    getline(cin, start_temp);

    int start = stoi(ltrim(rtrim(start_temp)));

    int result = prims(n, edges, start);

    fout << result << "\n";

    fout.close();

    return 0;
}

string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
    );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
        s.end()
    );

    return s;
}

vector<string> split(const string &str) {
    vector<string> tokens;

    string::size_type start = 0;
    string::size_type end = 0;

    while ((end = str.find(" ", start)) != string::npos) {
        tokens.push_back(str.substr(start, end - start));

        start = end + 1;
    }

    tokens.push_back(str.substr(start));

    return tokens;
}