In this post, we will solve HackerRank Prim’s (MST) : Special Subtree Problem Solution.
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 S 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
n = 3
edges = [[1, 2, 2], [2, 3, 2], [1, 3, 3]]
start = 1
Starting from node 1, select the lower weight edge, i.e. 1 → 2, weight 2.
Choose between the remaining edges, 13, weight 3, and 2 → 3, weight 2.
The lower weight edge is 2 + 3 weight 2.
All nodes are connected at a cost of 2 + 2 = 4. The edge 1 → 3 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 n and m, the number of nodes and edges in
the graph.
Each of the next m lines contains three space-separated integers u. v and w, the end nodes of edges[i], and the edge’s weight.
The last line has an integer start, the starting node.
Sample Input 0
5 6
1 2 3
1 3 4
4 2 6
5 2 2
2 3 5
3 5 7
1
Sample Output 0
15
Explanation 0
The graph given in the test case is shown as :
- The starting node is 1 (in the given test case)
Applying the Prim’s algorithm, edge choices available at first are:
1 → 2 (WT. 3) and 1→ 3 (WT. 4), out of which 1→ 2 is chosen (smaller weight of edge). Now the available choices are:
1→ 3 (WT. 4), 2 →3 (WT. 5), 25 (WT. 2) and 2 → 4 (WT. 6), out of which 2 → 5 is chosen by the algorithm.
Following the same method of the algorithm, the next chosen edges, sequentially are:
1 → 3 and 2 → 4.
Hence the overall sequence of edges picked up by Prim’s are:
12:25:13:2 → 4
and the total weight of the MST (minimum spanning tree) is: 3+2+4+6=15
Prim’s (MST) : Special Subtree C Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
struct nodes {
int mark;
int pre;
int val;
};
int n;
int m;
int s;
int e[3001][3001];
struct nodes node[3001];
int min_mark() {
int j,m=0,max=100001;
for(j=1;j<=n;j++) if(node[j].mark!=1 && node[j].val < max) {m=j; max=node[j].val;}
return m;
}
void SP(int s) {
int j;
for(j=1;j<=n;j++)
if(e[s][j]!=-1 && node[j].mark!=1) {
if(node[j].pre==0) {node[j].pre=s; node[j].val= e[s][j];}
else if(node[j].pre!=0 && node[j].val > e[s][j]) {node[j].pre=s; node[j].val= e[s][j];}
}
}
int main() {
int i,j,k,l,d;
scanf("%d",&n); scanf("%d",&m);
for(k=1;k<=n;k++)
for(l=1;l<=n;l++) e[k][l]=-1;
for(j=0;j<m;j++) {
scanf("%d",&k); scanf("%d",&l); scanf("%d",&d);
if(e[k][l]==-1) e[k][l]=d;
else if(e[k][l] > d) e[k][l]=d;
e[l][k]=e[k][l];
}
scanf("%d",&s);
//s=1;
for(k=1;k<=n;k++) {
if(k==s) {node[k].mark=1; node[k].pre=0; node[k].val=0;}
else {node[k].mark=0; node[k].pre=0; node[k].val= 100000;}
}
SP(s);
d=min_mark();
while(d!=0) {node[d].mark=1; SP(d); d=min_mark();}
d=0;
for(k=1;k<=n;k++) if(node[k].pre!=0) d+=e[k][node[k].pre];
printf("%d",d);
//printf("%d:\tmark= %d\tpre= %d\tval= %d\n",k,node[k].mark,node[k].pre,node[k].val);
return 0;
}
Prim’s (MST) : Special Subtree C++ Solution
#include<bits/stdc++.h>
# define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> iPair;
class Graph{
int V;
list<iPair> *adj;
public:
Graph(int V);
void addEdge(int u,int v,int w);
void prim(int s);
};
Graph::Graph(int V){
this->V = V;
adj = new list<iPair>[V];
}
void Graph::addEdge(int u,int v,int w){
adj[v].push_back(make_pair(u,w));
adj[u].push_back(make_pair(v,w));
}
void Graph::prim(int s){
priority_queue< iPair, vector<iPair> , greater<iPair> > pq;
vector<int> key(V,INF);
vector<int> parent(V,-1);
vector<bool> inMst(V,false);
key[s]=0;
pq.push(make_pair(key[s],s));
while(!pq.empty()){
int u = pq.top().second;
pq.pop();
inMst[u]=true;
list<iPair>::iterator i;
for(i = adj[u].begin();i!=adj[u].end();i++){
int v = (*i).first;
int w = (*i).second;
if(!inMst[v]&&key[v]>w){
parent[v]=u;
key[v]=w;
pq.push(make_pair(key[v],v));
}
}
}
int count=0;
for(int i=1;i<V;i++){
if(parent[i]!=-1){
count+=key[i];
//cout<<parent[i]<<"---"<<i<<endl;
}
}
cout<<count<<endl;
}
int main(){
int N,M,x,y,w,S;
cin>>N>>M;
Graph g(N+1);
for(int i=0;i<M;i++){
cin>>x>>y>>w;
g.addEdge(x,y,w);
}
cin>>S;
g.prim(S);
return 0;
}
Prim’s (MST) : Special Subtree C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
class Solution {
public class Edge {
public int D, W;
public Edge(int dest, int weight) { D = dest; W = weight; }
public Edge N;
}
public static Edge R = null;
public static void Add(Edge e) {
if(R == null) {
R = e;
} else if(e.W < R.W) {
e.N = R;
R= e;
} else {
Edge x = R;
while(x.N != null && x.N.W < e.W) {
x = x.N;
}
e.N = x.N;
x.N = e;
}
}
static void Main(String[] args) {
string[] line = Console.ReadLine().Split(' ');
int N = Int32.Parse(line[0]);
int M = Int32.Parse(line[1]);
List<Edge>[] edges = new List<Edge>[N+1];
for(int n=1; n<N+1; n++) { edges[n] = new List<Edge>(); }
for(int m=0; m<M; m++) {
line = Console.ReadLine().Split(' ' );
int x = Int32.Parse(line[0]);
int y = Int32.Parse(line[1]);
int w = Int32.Parse(line[2]);
edges[x].Add(new Edge(y,w));
edges[y].Add(new Edge(x,w));
}
int S = Int32.Parse(Console.ReadLine());
foreach(Edge e in edges[S]) {
Add(e);
}
bool[] done = new bool[N+1];
done[S] = true;
int cnt = 1;
int sum = 0;
while(cnt < N && R != null) {
Edge e = R;
R = e.N;
if(!done[e.D]) {
sum += e.W;
done[e.D] = true;
cnt++;
foreach(Edge ee in edges[e.D]) {
if(!done[ee.D]) Add(ee);
}
}
}
Console.WriteLine(sum);
}
}
Prim’s (MST) : Special Subtree Java Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Cost implements Comparable<Cost> {
public int r, v;
public Cost(int cost, int vertex) {
r = cost;
v = vertex;
}
@Override
public int compareTo(Cost c) {
if (r < c.r) return -1;
if (r> c.r) return 1;
if (v < c.v) return -1;
if (v > c.v) return 1;
return 0;
}
}
class Result {
/*
* 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
*/
// Slide mst.p52
public static boolean[] marked;
public static PriorityQueue<Cost> pq;
public static List<Cost> mstCosts;
public static void visit(List<List<Cost>> danhsachlienke, int v) {
marked[v] = true;
for(Cost cost : danhsachlienke.get(v)) {
if (!marked[cost.v]) {
pq.add(cost);
}
}
}
public static int prims(int n, List<List<Integer>> edges, int start) {
List<List<Cost>> danhsachlienke = new ArrayList<>(n + 1);
pq = new PriorityQueue<Cost>();
marked = new boolean[n+1];
mstCosts = new ArrayList<Cost>();
for(int i = 0; i < n + 1; ++i) {
danhsachlienke.add(new ArrayList<Cost>());
}
for (List<Integer> edge : edges) {
// System.out.println(edge.get(0) + " " + edge.get(1) + " " + edge.get(2));
danhsachlienke.get(edge.get(0)).add(new Cost(edge.get(2), edge.get(1)));
danhsachlienke.get(edge.get(1)).add(new Cost(edge.get(2), edge.get(0)));
}
visit(danhsachlienke, start);
// mstCosts.size() == mstEdges.size()
while (!pq.isEmpty() && mstCosts.size() < n - 1) {
Cost cost = pq.poll();
if (marked[cost.v]) {
continue;
} else {
mstCosts.add(cost);
visit(danhsachlienke, cost.v);
}
}
int total = 0;
for (Cost cost : mstCosts) {
total += cost.r;
}
return total;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
int n = Integer.parseInt(firstMultipleInput[0]);
int m = Integer.parseInt(firstMultipleInput[1]);
List<List<Integer>> edges = new ArrayList<>();
IntStream.range(0, m).forEach(i -> {
try {
edges.add(
Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList())
);
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
int start = Integer.parseInt(bufferedReader.readLine().trim());
int result = Result.prims(n, edges, start);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
}
Prim’s (MST) : Special Subtree JavaScript Solution
function calc(graph, edges, s) {
var total = 0;
var tree = [];
tree[s] = [];
while(true) {
var min = [-1, -1, 1000000];
for(var i=0; i<edges.length; i++) {
if(tree[edges[i][0]] && !tree[edges[i][1]] && edges[i][2] <= min[2])
min = edges[i];
}
if(min[0] == -1) return total;
//console.log(min[0], min[1], min[2]);
tree[min[0]].push([min[1], min[2]]);
tree[min[1]] = [];
total += min[2];
}
}
function processData(input) {
var lines = input.split('\n');
var index = 0;
var tokens = lines[index++].split(' ');
var N = parseInt(tokens[0]);
var M = parseInt(tokens[1]);
var graph = [];
for(var i=0; i<=N; i++) graph[i] = [];
var edges = [];
for(var j = 0; j < M; j++) {
var tokens = lines[index++].split(' ');
var a = parseInt(tokens[0]);
var b = parseInt(tokens[1]);
var w = parseInt(tokens[2]);
edges.push([a, b, w]);
edges.push([b, a, w]);
graph[a].push([b, w]);
graph[b].push([a, w]);
}
var s = parseInt(lines[index++]);
var total = calc(graph, edges, s);
console.log(total);
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});
Prim’s (MST) : Special Subtree Python Solution
import operator
n, m = map(int, input().split())
edges = {}
for __ in range(0, m):
x, y, r = map(int, input().split())
x -= 1
y -= 1
x, y = min(x, y), max(x, y)
if (x, y) in edges:
edges[x, y] = min(edges[x, y], r)
else:
edges[x, y] = r
s = int(input()) - 1
trees = []
sorted_edges = sorted(edges.items(), key=operator.itemgetter(1), reverse=True)
s = 0
while len(sorted_edges) > 0:
(x, y), r = sorted_edges.pop()
ok = True
xi = None
yi = None
for k in range(0, len(trees)):
if x in trees[k] and y in trees[k]:
ok = False
break
elif x in trees[k]:
trees[k].add(y)
xi = k
elif y in trees[k]:
trees[k].add(x)
yi = k
if ok:
s += r
if xi != None and yi != None:
trees[xi] |= trees[yi]
trees.pop(yi)
elif xi != None:
trees[xi].add(y)
elif yi != None:
trees[yi].add(x)
else:
trees.append({x, y})
print(s)