𝗚𝗿𝗮𝗽𝗵 𝗥𝗲𝗽𝗿𝗲𝘀𝗲𝗻𝘁𝗮𝘁𝗶𝗼𝗻: A 𝗖𝗼𝗺𝗺𝗼𝗻 𝗠𝗶𝘀𝗰𝗼𝗻𝗰𝗲𝗽𝘁𝗶𝗼𝗻𝘀 For graph representation, we all know that there are two main way to represent a graph. (𝘛𝘩𝘦𝘳𝘦 𝘢𝘳𝘦 𝘧𝘦𝘸 𝘮𝘰𝘳𝘦 𝘸𝘢𝘺𝘴 𝘵𝘰 𝘳𝘦𝘱𝘳𝘦𝘴𝘦𝘯𝘵 𝘨𝘳𝘢𝘱𝘩)   

• 𝗔𝗱𝗷𝗮𝗰𝗲𝗻𝗰𝘆 𝗠𝗮𝘁𝗿𝗶𝘅  

• 𝗔𝗱𝗷𝗮𝗰𝗲𝗻𝗰𝘆 𝗟𝗶𝘀𝘁

We were taught that 𝗔𝗱𝗷𝗮𝗰𝗲𝗻𝗰𝘆 𝗟𝗶𝘀𝘁 is memory efficient from space complexity perspective than 𝗔𝗱𝗷𝗮𝗰𝗲𝗻𝗰𝘆 𝗠𝗮𝘁𝗿𝗶𝘅. (Not true in worst case)

But how? let's see,

We have a graph G of 𝙣=𝟰 vertices and we have edges 𝙣(𝙣-𝟭)/𝟮 = 𝟲 (maximum possible edge).  If we store this graph using 𝗔𝗱𝗷𝗮𝗰𝗲𝗻𝗰𝘆 𝗠𝗮𝘁𝗿𝗶𝘅, we will have simply a matrix representation like below.     

  𝟭  𝟮  𝟯  𝟰 
-------------- 
𝟭| 𝟬  𝟭   𝟭   𝟭 
𝟮| 𝟭  𝟬   𝟭   𝟭 
𝟯| 𝟭  𝟭   𝟬   𝟭 
𝟰| 𝟭  𝟭   𝟭   𝟬 

which takes at most 𝙣^𝟮 (𝟭𝟲𝗯𝗶𝘁𝘀 𝗳𝗼𝗿 𝗻=𝟰)

_____________________________________________

But what if we represent the same graph using 𝗔𝗱𝗷𝗮𝗰𝗲𝗻𝗰𝘆 𝗟𝗶𝘀𝘁?

How it will looks like?

Showing below

𝟭: 𝟮, 𝟯, 𝟰 
𝟮: 𝟭, 𝟯, 𝟰 
𝟯: 𝟭, 𝟮, 𝟰 
𝟰: 𝟭, 𝟮, 𝟯

Here we can see each vertex has (𝙣-𝟭) 𝗻𝗲𝗶𝗴𝗵𝗯𝗼𝘂𝗿𝘀 (𝗳𝗼𝗿 𝙣=𝟰, 𝗻𝗲𝗶𝗴𝗵𝗯𝗼𝘂𝗿𝘀 𝗶𝘀 𝟯), so for 𝙣 neighbors its 𝙣(𝙣-𝟭) bits of space (𝗳𝗼𝗿 𝙣=𝟰, 𝟰𝙭(𝟰-𝟭)=𝟭𝟮 𝗯𝗶𝘁𝘀  and for each vertex requires 𝙡𝙤𝙜𝟮𝙣 bits to represent itself.

So the total memory required is 𝙣(𝙣-𝟭)𝙡𝙤𝙜_𝟮𝙣

𝟭𝟮+𝙡𝙤𝙜_𝟮(𝟰) = 𝟮𝟰𝙗𝙞𝙩𝙨  𝙛𝙤𝙧 𝙣=𝟰

_____________________________________________

From the above example, we can say 𝗔𝗱𝗷𝗮𝗰𝗲𝗻𝗰𝘆 𝗟𝗶𝘀𝘁 takes more space than 𝗔𝗱𝗷𝗮𝗰𝗲𝗻𝗰𝘆 𝗠𝗮𝘁𝗿𝗶𝘅, which is 𝙣^𝟮𝙡𝙤𝙜_𝟮𝙣 > 𝙣^𝟮.