前幾天在寫了兩篇介紹運籌學的文章，在簡友@三余尋真的提示之下蹬铺，決定從今天開始，把關(guān)于圖論的問題詳細介紹一下匈庭。
圖論里面的東西挺多的夫凸，從哪里開始講呢？考慮到每一個算法其實都是基于數(shù)據(jù)的存儲結(jié)構(gòu)來決定的阱持，圖里面尤其如此夭拌，用不同的方法存儲圖，會產(chǎn)生不同的算法衷咽。第一講啼止，我決定從圖在計算機中怎么存儲表示的開始講起。
圖在計算機中主要有鄰接矩陣和鄰接表兩種存儲方式兵罢，這兩種存儲方式之下還有好幾種變形。
先說鄰接矩陣：
鄰接矩陣是一個方陣滓窍，它的i行j列元素是連接頂點i和頂點j的邊的屬性（比如邊的長度卖词，權(quán)重之類的）。比如下面就是一個圖的鄰接矩陣表示的例子吏夯。圖的一些性質(zhì)可以很好的映射到矩陣上去此蜈。比如在無向圖中，邊是沒有方向的噪生，所以頂點i連到頂點j和頂點j連到頂點i是一回事裆赵。對應到鄰接矩陣中就表示鄰接矩陣是沿對角線對稱了。
用鄰接矩陣存儲圖的一個主要好處就是方便計算跺嗽。原因是用鄰接矩陣的方式存儲圖战授，可以將很多圖中的運算轉(zhuǎn)換成矩陣之間的運算，方便了分析過程桨嫁。比如求解最短路徑問題時會提到一個Floyd算法植兰，就是利用鄰接矩陣循環(huán)相乘若干次得到結(jié)果。用鄰接矩陣表示圖璃吧，不僅方便了分析過程楣导，而且方便了計算過程。首先畜挨，網(wǎng)上有各種矩陣運算的庫筒繁，可以很方便的調(diào)用。其次巴元，在許多矩陣運算中毡咏，對每個元素的求值都是相互獨立的。比如矩陣相乘务冕，求Matrix[2,9]的值和Matrix[7,4]的值的過程相互獨立血当，所以能夠很方便的使用并行加速過程。
鄰接矩陣存儲圖的主要缺點就是占用太多內(nèi)存了，鄰接矩陣需要的內(nèi)存數(shù)量是圖頂點數(shù)量的平方臊旭，當點的數(shù)量比較大的時候需要消耗很多內(nèi)存落恼，如果圖中邊的數(shù)量不是很多，那就是很大的浪費离熏。比如QQ有上億用戶佳谦，但每個用戶的好友一般也就幾百個，QQ好友關(guān)系就是一個典型的稀疏圖滋戳。我想騰訊再壕也不會用鄰接矩陣存儲用戶的好友關(guān)系钻蔑。在處理大規(guī)模稀疏矩陣的時候特別嚴重。鄰接矩陣另一個主要的缺點就是不能存儲帶重邊的圖（所謂重邊奸鸯，是指兩個頂點之間有多于一條的邊連接）咪笑。
然后是圖的鄰接表
所謂鄰接表，就是用一個數(shù)組來存儲所有的點娄涩，然后把從同一個頂點發(fā)出的邊存儲在一條鏈表中窗怒。如下圖所示。
在上圖的例子中蓄拣，每一條邊都是從左邊數(shù)組中出發(fā)的邊扬虚，所以又叫做出邊表。相應的球恤，我們還有入邊表辜昵。
鄰接表最大的缺點就是不方便使用。舉個簡單的例子咽斧，即使是要在鄰接表中確定a堪置，b兩個點之間是否存在一條邊，也需要遍歷連接在a和b兩個頂點上的鏈表收厨。而這在鄰接矩陣中直接就讀出來了晋柱。想想就能感覺到用鄰接表實現(xiàn)兩個矩陣相乘是多么的令人DT。鄰接表做運算的時候不只難以理解诵叁，而且運算速度比較慢雁竞。遍歷鏈表是鄰接表中的基本操作，每次遍歷鏈表都需要一次次的讀取內(nèi)存拧额，特別耗時耗力碑诉。
相比于鄰接矩陣，鄰接表的優(yōu)勢是表達能力強侥锦，可以表示任何類型的圖进栽，包括重邊圖。而且結(jié)構(gòu)靈活恭垦，節(jié)約內(nèi)存快毛，特別適合存儲系數(shù)矩陣格嗅。
