1 votes 1 votes I tried by taking n=2 , and took points (1,1) ,(1,2) ,(2,2),(2,1) and I got the minimum weight to be 3 , which is n+1 but according to answer it is n-1 Algorithms graph-algorithms minimum-spanning-tree virtual-gate-test-series + – radha gogia asked Feb 20, 2016 • retagged Jul 8, 2022 by Lakshman Bhaiya radha gogia 409 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes The length of an MST (number of edges required to make it) in an nXn grid where each square is a vertex is always n^2-1 ...(1) Further, if an edge is axial (vertical or horizontal), then its weight should be 1 according to the formula given in the problem. ...(2) Now since we are taking only axial edges, the total weight of the MST from (1) & (2) comes out to be: (n^2-1)*1 So the weight of the MST of this graph should be n^2-1 according to me. Somesh Singh answered Feb 21, 2016 • edited Feb 21, 2016 by Somesh Singh Somesh Singh comment Share Follow See all 0 reply Please log in or register to add a comment.