We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
MST is by definition an undirected tree that uses edges from the graph and contains all the vertexes. There is no requirement for any starting point.
To solve I used Prims Algorithms for findind MST.
in short:
we will build the MST such that E is the set of all the edges in the MST.
In the begining S is set of all the vertexes and T is an empty set of vertexes and E is an empty set of edges.
Choose random (!) vertex and move it from S to T.
While S is not empty do the following:
1) find the minimal edge connecting T to S. lets mark it u-v when u is vertex in T and v is vertex in S.
2) move v from S to T.
3) add the edge to E
in the and E will contain the edges of the MST. if you want its value you need to sum them. in this question you dont need the value (just the sum) so you dont need to build E, just keep track of its sum
hope it helps, tell me if you need more details
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Prim's (MST) : Special Subtree
You are viewing a single comment's thread. Return to all comments →
MST is by definition an undirected tree that uses edges from the graph and contains all the vertexes. There is no requirement for any starting point. To solve I used Prims Algorithms for findind MST.
in short:
we will build the MST such that E is the set of all the edges in the MST. In the begining S is set of all the vertexes and T is an empty set of vertexes and E is an empty set of edges.
Choose random (!) vertex and move it from S to T.
While S is not empty do the following:
1) find the minimal edge connecting T to S. lets mark it u-v when u is vertex in T and v is vertex in S.
2) move v from S to T.
3) add the edge to E
in the and E will contain the edges of the MST. if you want its value you need to sum them. in this question you dont need the value (just the sum) so you dont need to build E, just keep track of its sum
hope it helps, tell me if you need more details