鄰接表：圖的高效存儲方式，比鄰接矩陣好在哪？
這篇文章介紹了圖的基本概念及兩種核心存儲方式：鄰接矩陣與鄰接表。圖由頂點（如社交網絡用戶）和邊（如好友關係）構成。 鄰接矩陣是二維數組，用0/1表示頂點間是否有邊，空間需n²（n爲頂點數），查找邊時間O(1)，但稀疏圖（邊少）時空間浪費大。鄰接表則爲每個頂點維護鄰居列表（如用戶好友列表），空間n+e（e爲邊數），僅存實際邊，查找需遍歷鄰居表（時間O(degree(i))，i爲頂點），遍歷鄰居更高效。 對比顯示，鄰接表在稀疏圖（多數實際場景）中空間和時間效率均優於鄰接矩陣，是處理圖問題（如最短路徑）的主流存儲方式，更省空間且遍歷更快。
閱讀全文鄰接矩陣：圖的另一種表示方法，優缺點對比
鄰接矩陣是圖的一種基礎表示方式，本質爲n×n二維數組，行與列對應圖的頂點，元素值表示頂點間邊的存在性或權重。無向圖中，元素1表示有邊，0表示無邊；有權圖則直接存儲權重值。 其優點：一是判斷邊存在僅需O(1)時間，計算頂點度高效（無向圖行和，有向圖行/列分別對應出/入度）；二是適合稠密圖（邊數接近n²），空間利用率高，且實現簡單，便於初學者理解。 缺點：空間複雜度爲O(n²)，稀疏圖時浪費大量空間；遍歷鄰接頂點需O(n)時間，效率低於鄰接表；動態調整邊數靈活性不足。 總結：鄰接矩陣以空間換時間，適合稠密圖、需頻繁查詢邊或計算度的場景，不適合稀疏圖或需頻繁遍歷鄰接頂點的場景，是理解圖結構的基礎工具。
閱讀全文