無向圖丝蹭，是指在圖中的每條邊都是無向的贱田，無向圖G=<V,E>湘换，其中V是非空集合，稱為頂點集统阿，E是V中元素構(gòu)成的無序二元組的集合彩倚，成為邊集。
如圖所示扶平，這是一張無向圖
如果我們需要存儲這份圖帆离，通過鄰接矩陣，我們將上圖表示為 ：
? ? ? A? ? ? ? ? B? ? ? ? ?C? ? ? ? D? ? ? ? ? E? ? ? ? ?F? ? ? ? G
A? ? 0? ? ? ? ? 0? ? ? ? ?1? ? ? ? ?0? ? ? ? ? 1? ? ? ? ?0? ? ? ? 0
B? ? 0? ? ? ? ? 0? ? ? ? ?0? ? ? ? ?0? ? ? ? ? 0? ? ? ? ?1? ? ? ? 0?
C? ? 1? ? ? ? ? 0? ? ? ? ?0? ? ? ? ?0? ? ? ? ? 1? ? ? ? ?0? ? ? ? 0
D? ?0? ? ? ? ? 0? ? ? ? ?0? ? ? ? ?0? ? ? ? ? 0? ? ? ? ?0? ? ? ? 1
E? ? 1? ? ? ? ? 0? ? ? ? ?1? ? ? ? ?0? ? ? ? ? 0? ? ? ? ?0? ? ? ? 0
F? ? 0? ? ? ? ? 1? ? ? ? ?0? ? ? ? ?0? ? ? ? ? 0? ? ? ? ?0? ? ? ? 1
G? ?0? ? ? ? ? 1? ? ? ? ?0? ? ? ? ?1? ? ? ? ? 0? ? ? ? ?1? ? ? ? 0? ??
從這張表中结澄，我們可以發(fā)現(xiàn)哥谷，無向圖的鄰接矩陣是根據(jù)正對角線對稱的，這種情況是因為無向圖不區(qū)分方向麻献。
有了這樣一個鄰接矩陣后们妥。我們就可通過矩陣，可以得到那兩個頂點之間存在一條邊勉吻，甚至可以通過鄰接矩陣去驗證一張圖是否為鄰接矩陣监婶。
但是，鄰接矩陣只能對簡單的圖進(jìn)行表示齿桃，即圖的邊和點沒有什么特殊含義惑惶，那么，如果又這樣一張圖：
在圖中短纵，我們可以知道這是一張無向加權(quán)圖带污，現(xiàn)在如果我們需要表示這樣一張圖，該采用什么樣的數(shù)據(jù)結(jié)構(gòu)呢香到？
或許你可以說鱼冀，我還是用鄰接矩陣來存儲數(shù)據(jù)报破，存儲方式如下：
? ? ? ?a? ? ? ? ? b? ? ? ? ?c? ? ? ? ?d? ? ? ? ? e? ? ? ? ?f? ? ? ??
a? ? 0? ? ? ? ? 20? ? ? ? ?1? ? ? ?0? ? ? ? 10? ? ? ? ?9? ? ? ?
b? ? 20? ? ? ? ?0? ? ? ? ?5? ? ? ? ?6? ? ? ? ?0? ? ? ? ?11? ? ? ??
c? ? 0? ? ? ? ? ?5? ? ? ? ?0? ? ? ? ?6? ? ? ? ? 0? ? ? ? ?0? ? ? ??
d? ?0? ? ? ? ? ?6? ? ? ? ?6? ? ? ? ?0? ? ? ? ? 18? ? ? ? ?14? ? ? ??
e? ? 10? ? ? ? ?0? ? ? ? 0? ? ? ? ?18? ? ? ? ?0? ? ? ? ?10? ? ? ??
f? ? 9? ? ? ? ? ?11? ? ? ? ?0? ? ? ? ?14? ? ? ? ? 10? ? ? ? ?0? ? ? ??
這樣的話，鄰接矩陣存儲的值就有了多重含義雷绢，不僅僅表示兩個頂點之間存在關(guān)系泛烙，還知道了存在什么樣的關(guān)系，但是翘紊，情況是會不斷復(fù)雜的蔽氨，當(dāng)我們每條邊的含義不僅僅只有權(quán)重，還有了最大流通量帆疟，最小流通量等屬性時鹉究，而且當(dāng)我們的頂點也具有了相應(yīng)的屬性時（如權(quán)重），鄰接矩陣就不在適用于這樣的情況下了踪宠，那么自赔，這個時候我們需要用什么樣的數(shù)據(jù)結(jié)構(gòu)來應(yīng)對，能讓它能面對復(fù)雜的情況呢柳琢？
這個時候绍妨，我們就可以考慮鄰接鏈表了：
這是一張用于表示無向圖的鄰接鏈表，圖中先將所有的頂點一次標(biāo)了序號0,1,2,3柬脸，接著再鏈接到的節(jié)點中用標(biāo)號來表示下一個節(jié)點是哪個節(jié)點他去，因為是無向圖，所以存在重復(fù)的部分倒堕，當(dāng)這個無向圖的頂點需要增加新的屬性時灾测，我們只需要對節(jié)點添加一個屬性即可，這樣看來的話垦巴，可擴(kuò)展性顯然是比臨街矩陣要好的媳搪，有些人可能會有這樣一個疑惑，這鄰接鏈表還是不能解決邊屬性增加的問題爸栊秦爆？針對這個問題，我們來看看下面這張圖:
這張圖中憔披，鄰接鏈表中的節(jié)點多了一個屬性專門用來存儲邊值鲜结，這樣看來的話，無論是點對象的屬性增加還是變得屬性增加活逆，我們都可以通過鄰接鏈表來實現(xiàn)了精刷。
但是，真正使用過相關(guān)數(shù)據(jù)結(jié)構(gòu)的朋友就會發(fā)現(xiàn)一個問題蔗候，當(dāng)在處理問題時怒允，可能我們經(jīng)常需要獲取一條邊來進(jìn)行操作，但是在只有一個頂點的情況下锈遥，針對鄰接鏈表獲取一條邊是一件很痛苦的事情纫事，每一次獲取我們都需要遍歷所有與該頂點相連的邊勘畔，這樣的話是很消耗時間和內(nèi)存的，但是鄰接矩陣雖然可以隨機(jī)訪問丽惶，但是他不能處理復(fù)雜的業(yè)務(wù)炫七，那究竟該怎么辦呢？
縱觀計算機(jī)歷史中钾唬，這樣的問題我們遇到了很多万哪，向計算機(jī)操作系統(tǒng)的頁面置換算法，調(diào)度算法等抡秆，都是有連個互相在對立方面具有優(yōu)勢的情況（A精通A領(lǐng)域奕巍，但不熟悉B領(lǐng)域；B精通B領(lǐng)域儒士，但不熟悉A領(lǐng)域）的止，這樣看來的話，我們可以借鑒一下先人們的解決思路着撩，我們可以先將完整的圖使用鄰接鏈表存儲诅福，然后僅僅對點與點之間的聯(lián)系使用臨接矩陣進(jìn)行存儲，這樣的話拖叙，我們就可以兼顧兩者的優(yōu)點氓润，代價就是多一點空間存儲鄰接矩陣。到這里就結(jié)束了憋沿，整個文章就一句話總結(jié)：中庸之道。
