engineering recuitment GATE CSE 2023-24 Test Series Algorithms Graphs/Spanning Tree and Shortest Paths Spanning Tree
Consider a weighted undirected graph with vertex set V = {v1, v2, v3, v4, v5, v6} and edge set E = {(v1, v2, 2), (v1, v3, 8), (v1, v6, 3), (v2, v4, 4), (v2, v5, 12), (v3, v4, 7), (v4, v5, 9), (v4, v6, 4)}.
The third value in each tuple represents the weight of the edge specified in the tuple.
List the edges of a minimum spanning tree of the graph.1
{(v1, v2, 2), (v1, v6, 3), (v2, v4, 4), (v3, v4, 7), (v4, v6, 4)}
2
{(v1, v2, 2), (v1, v6, 3), (v2, v4, 4), (v4, v5, 9), (v3, v4, 7)}
3
{(v1, v2, 2), (v1, v6, 3), (v1, v3, 8), (v4, v6, 4), (v3, v4, 7)}
4
none