逆鄰接鏈表是什么？

逆鄰接鏈表是作為圖的一種存儲方式，在存儲稀疏圖上相對于鄰接矩陣有相當(dāng)大的空間節(jié)省。

如一個稀疏圖的頂點(diǎn)個個數(shù)為n，邊數(shù)為e。用鄰接矩陣存儲需要n^2空間，而真正進(jìn)行存儲的只有2e個空間， 剩下的n^2-2e都浪費(fèi)了。

但是對于鄰接表來講，存儲空間只需要n+2e個，相對于鄰接矩陣減少了很多。

逆鄰接鏈表反映的是節(jié)點(diǎn)的出度鄰接情況,圖的逆鄰接表反映的是節(jié)點(diǎn)的入度鄰接情況。