鄰接表與鄰接矩陣的異同點(diǎn)有哪些？（1）連接：鄰接表中每個鏈頭后的所有邊表節(jié)點(diǎn)對應(yīng)鄰接矩陣的每一行，鄰接表中的每個邊表節(jié)點(diǎn)對應(yīng)鄰接矩陣行的一個非零元素。（2） 區(qū)別：①對于任意給定的無向圖，鄰接矩陣是唯

鄰接表與鄰接矩陣的異同點(diǎn)有哪些？

（1）連接：鄰接表中每個鏈頭后的所有邊表節(jié)點(diǎn)對應(yīng)鄰接矩陣的每一行，鄰接表中的每個邊表節(jié)點(diǎn)對應(yīng)鄰接矩陣行的一個非零元素。（2） 區(qū)別：①對于任意給定的無向圖，鄰接矩陣是唯一的（行數(shù)和列數(shù)與頂點(diǎn)數(shù)一致），但鄰接表不是唯一的（鏈接順序與頂點(diǎn)數(shù)無關(guān)）。② 鄰接矩陣的空間復(fù)雜度為0（N2），鄰接表的空間復(fù)雜度為0（n+e）。③ 在鄰接表中很容易找到任意頂點(diǎn)的第一個和下一個相鄰節(jié)點(diǎn)，但要確定任意兩個頂點(diǎn)（VI，VJ）是否通過邊或弧連接，需要搜索I或j鏈表，這不如鄰接矩陣方便。④ 鄰接矩陣主要用于存儲稠密圖（E接近n（n-1）/2），鄰接表主要用于存儲稀疏圖（E

無向圖的鄰接矩陣一定是什么矩陣？

是對稱矩陣。根據(jù)矩陣的性質(zhì)，我們可以知道其中的原因：鄰接矩陣：它是表示頂點(diǎn)之間鄰接關(guān)系的矩陣。設(shè)g=（V，e）是一個圖，其中V={V1，V2，vn}。g的鄰接矩陣是一個n階方陣，具有以下性質(zhì)：對于無向圖，鄰接矩陣必須是對稱的，對角線必須是零。無向圖的鄰接矩陣必須是對稱的，而有向圖的鄰接矩陣不一定是對稱的。因此，用鄰接矩陣表示n個頂點(diǎn)的有向圖時，需要n^2個單元來存儲鄰接矩陣；對于n個頂點(diǎn)的無向圖，在去掉左上右下對角線上的0元素后，只在上（下）三角矩陣中存儲剩余的元素，所以只需要1 2。。。（n-1）=n（n-1）/2個單元格。無向圖鄰接矩陣第i行（或第i列）中非零元素的個數(shù)正是第i頂點(diǎn)的次。