Problem StatementLet, $G(V,E)$ be a graph with a weight function $w(v)$ defined for all vertices. We need to find a tree $T(V',E')$ such that the resulting tree have maximum sum of weights of vertices, where $V' \in V$ and $E' \in E$. In short, we need to remove some vertices(along with all their edges) from $G(V,E)$ such that the resulting graph is a tree and have maximum weight among all such trees. $T(V'.E')$ should be an induced subgraph of $G(V,E)$.My AttemptFirst, sort the vertices in descending order. Then, pick the vertices in that order ensuring that adding a vertex won't create cycles. If it creates cycles, don't consider that vertex. To check if adding a particular vertex adds cycles, I thought of assigning each component a uniaue number. Hence, if adding a vertex results in joining that vertex to two vertices of the same component, we don't add that vertex. But, I couldn't find an efficient way on how should we keep track of which vertex belongs of which component. Can DSU help me with this approach?
Maximum weight tree with weights on vertices
algorithms;graphs;graph theory;data structures