The GATE Grind

GATE 2020 CS – Question 59

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Numerical answer

Consider a graph $G=(V,E)$, where $V=\{v_1,v_2,\dots,v_{100}\}$, $E=\{(v_i,v_j)\mid 1\le i<j\le 100\}$, and weight of the edge $(v_i,v_j)$ is $|i-j|$. The weight of minimum spanning tree of $G$ is ______.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 99 to 99

Explanation

The path $v_1-v_2-\dots-v_{100}$ uses the 99 lightest edges, each of weight 1. Total weight 99.