Prim's (MST) : Special Subtree

  • + 3 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