It was mentioned in the below answer that adjacency list representation of sparse graph with 1000 vertices can store 2997 values. https://stackoverflow.com/a/12599289/3184755 But I can only think the answer is 999*2 = 1998 because number of edges in a tree of 'n' nodes is n-1 and in adjacency list of undirected graph will have 2 * no. of edges. Please explain how the value is 2997 for sparse graph? Also how the value is 3000000 for dense graph?

Typing it from my phone so couldn't format the answer

0 Answers