鄰接表的數組實作
之前我們介紹過圖的鄰接矩陣存儲法，它的空間和時間複雜度都是N2，現在我來介紹另外一種存儲圖的方法：鄰接表，這樣空間和時間複雜度就都是M。對于稀疏圖來說，M要遠遠小于N2。先上資料，如下。
<a target="_blank" href="http://bbs.ahalei.com/data/attachment/forum/201404/08/091650e0f00oqrcjcfnq93.png"></a>
第一行兩個整數n m。n表示頂點個數（頂點編号為1~n），m表示邊的條數。接下來m行表示，每行有3個數x y z，表示頂點x到頂點y的邊的權值為z。下圖就是一種使用連結清單來實作鄰接表的方法。
<a target="_blank" href="http://bbs.ahalei.com/data/attachment/forum/201404/08/091650gyll6hbqbjyxls8s.png"></a>
上面這種實作方法為圖中的每一個頂點（左邊部分）都建立了一個單連結清單（右邊部分）。這樣我們就可以通過周遊每個頂點的連結清單，進而得到該頂點所有的邊了。使用連結清單來實作鄰接表對于痛恨指針的的朋友來說，這簡直就是噩夢。這裡我将為大家介紹另一種使用數組來實作的鄰接表，這是一種在實際應用中非常容易實作的方法。這種方法為每個頂點i（i從1~n）也都儲存了一個類似“連結清單”的東西，裡面儲存的是從頂點i出發的所有的邊，具體如下。
首先我們按照讀入的順序為每一條邊進行編号（1~m）。比如第一條邊“1 4 9”的編号就是1，“1 3 7”這條邊的編号是5。
這裡用u、v和w三個數組用來記錄每條邊的具體資訊，即u[i ]、v[i ]和w[i ]表示第i條邊是從第u[i ]号頂點到v[i ]号頂點（u[i ]->[i ]），且權值為w[i ]。
<a target="_blank" href="http://bbs.ahalei.com/data/attachment/forum/201404/08/091650h35zq3wgx30x3oe3.png"></a>
再用一個first數組來存儲每個頂點其中一條邊的編号。以便待會我們來枚舉每個頂點所有的邊（你可能會問：存儲其中一條邊的編号就可以了？不可能吧，每個頂點都需要存儲其所有邊的編号才行吧！甭着急，繼續往下看）。比如1号頂點有一條邊是 “1 4 9”（該條邊的編号是1），那麼就将first[1]的值設為1。如果某個頂點i沒有以該頂點為起始點的邊，則将first[i
]的值設為-1。現在我們來看看具體如何操作，初始狀态如下。
<a target="_blank" href="http://bbs.ahalei.com/data/attachment/forum/201404/08/091650zw3988qpj5iljj8g.png"></a>
咦？上圖中怎麼多了一個next數組，有什麼作用呢？不着急，待會再解釋，現在先讀入第一條邊“1 4 9”。
讀入第1條邊（1 4 9），将這條邊的資訊存儲到u[1]、v[1]和w[1]中。同時為這條邊賦予一個編号，因為這條邊是最先讀入的，存儲在u、v和w數組下标為1的單元格中，是以編号就是1。這條邊的起始點是1号頂點，是以将first[1]的值設為1。
另外這條“編号為1的邊”是以1号頂點（即u[1]）為起始點的第一條邊，是以要将next[1]的值設為-1。也就是說，如果目前這條“編号為i的邊”，是我們發現的以u[i ]為起始點的第一條邊，就将next[i ]的值設為-1（貌似的這個next數組很神秘啊⊙_⊙）。
<a target="_blank" href="http://bbs.ahalei.com/data/attachment/forum/201404/08/091651kwo5g0aycy07wfwd.png"></a>
讀入第2條邊（4 3 8），将這條邊的資訊存儲到u[2]、v[2]和w[2]中，這條邊的編号為2。這條邊的起始頂點是4号頂點，是以将first[4]的值設為2。另外這條“編号為2的邊”是我們發現以4号頂點為起始點的第一條邊，是以将next[2]的值設為-1。
<a target="_blank" href="http://bbs.ahalei.com/data/attachment/forum/201404/08/091651fkswcj34c05k8w4k.png"></a>
讀入第3條邊（1 2 5），将這條邊的資訊存儲到u[3]、v[3]和w[3]中，這條邊的編号為3，起始頂點是1号頂點。我們發現1号頂點已經有一條“編号為1 的邊”了，如果此時将first[1]的值設為3，那“編号為1的邊”豈不是就丢失了？我有辦法，此時隻需将next[3]的值設為1即可。現在你知道next數組是用來做什麼的吧。next[i
]存儲的是“編号為i的邊”的“前一條邊”的編号。
<a target="_blank" href="http://bbs.ahalei.com/data/attachment/forum/201404/08/091651df28foy9ct7fl7qf.png"></a>
讀入第4條邊（2 4 6），将這條邊的資訊存儲到u[4]、v[4]和w[4]中，這條邊的編号為4，起始頂點是2号頂點，是以将first[2]的值設為4。另外這條“編号為4的邊”是我們發現以2号頂點為起始點的第一條邊，是以将next[4]的值設為-1。
<a target="_blank" href="http://bbs.ahalei.com/data/attachment/forum/201404/08/091652vf4eg69f5zfsese9.png"></a>
讀入第5條邊（1 3 7），将這條邊的資訊存儲到u[5]、v[5]和w[5]中，這條邊的編号為5，起始頂點又是1号頂點。此時需要将first[1]的值設為5，并将next[5]的值改為3。
<a target="_blank" href="http://bbs.ahalei.com/data/attachment/forum/201404/08/091652li6mzammza242tmp.png"></a>
此時，如果我們想周遊1号頂點的每一條邊就很簡單了。1号頂點的其中一條邊的編号存儲在first[1]中。其餘的邊則可以通過next數組尋找到。請看下圖。
<a target="_blank" href="http://bbs.ahalei.com/data/attachment/forum/201404/08/091652rtjh5qe2211eee58.png"></a>
細心的同學會發現，此時周遊邊某個頂點邊的時候的周遊順序正好與讀入時候的順序相反。因為在為每個頂點插入邊的時候都直接插入“連結清單”的首部而不是尾部。不過這并不會産生任何問題，這正是這種方法的其妙之處。
建立鄰接表的代碼如下。
接下來如何周遊每一條邊呢？我們之前說過其實first數組存儲的就是每個頂點i（i從1~n）的第一條邊。比如1号頂點的第一條邊是編号為5的邊（1 3 7），2号頂點的第一條邊是編号為4的邊（2 4 6），3号頂點沒有出向邊，4号頂點的第一條邊是編号為2的邊（2 4 6）。那麼如何周遊1号頂點的每一條邊呢？也很簡單。請看下圖：
周遊1号頂點所有邊的代碼如下。
周遊每個頂點的所有邊的代碼如下。
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)