算法 8：巧妙的鄰接表（數(shù)組實現(xiàn)）

之前我們介紹過圖的鄰接矩陣存儲法，它的空間和時間復(fù)雜度都是 N2，現(xiàn)在我來介紹另外一種存儲圖的方法：鄰接表，這樣空間和時間復(fù)雜度就都是 M。對于稀疏圖來說，M 要遠(yuǎn)遠(yuǎn)小于 N2。先上數(shù)據(jù)，如下。

    4 5
    1 4 9
    4 3 8
    1 2 5
    2 4 6
    1 3 7

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/8.1.png" alt="picture8.1" />

第一行兩個整數(shù) n m。n 表示頂點個數(shù)（頂點編號為 1~n），m 表示邊的條數(shù)。接下來 m 行表示，每行有 3 個數(shù) x y z，表示頂點 x 到頂點 y 的邊的權(quán)值為 z。下圖就是一種使用鏈表來實現(xiàn)鄰接表的方法。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/8.2.png" alt="picture8.2" />

上面這種實現(xiàn)方法為圖中的每一個頂點（左邊部分）都建立了一個單鏈表（右邊部分）。這樣我們就可以通過遍歷每個頂點的鏈表，從而得到該頂點所有的邊了。使用鏈表來實現(xiàn)鄰接表對于痛恨指針的的朋友來說，這簡直就是噩夢。這里我將為大家介紹另一種使用數(shù)組來實現(xiàn)的鄰接表，這是一種在實際應(yīng)用中非常容易實現(xiàn)的方法。這種方法為每個頂點 i（i 從 1~n）也都保存了一個類似“鏈表”的東西，里面保存的是從頂點 i 出發(fā)的所有的邊，具體如下。

首先我們按照讀入的順序為每一條邊進行編號（1~m）。比如第一條邊“1 4 9”的編號就是 1，“1 3 7”這條邊的編號是 5。

這里用 u、v 和 w 三個數(shù)組用來記錄每條邊的具體信息，即 u[i]、v[i]和 w[i]表示 第i 條邊是從第 u[i]號頂點到 v[i]號頂點（u[i]àv[i]），且權(quán)值為 w[i]。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/8.3.png" alt="picture8.3" />

再用一個 first 數(shù)組來存儲每個頂點其中一條邊的編號。以便待會我們來枚舉每個頂點所有的邊（你可能會問：存儲其中一條邊的編號就可以了？不可能吧，每個頂點都需要存儲其所有邊的編號才行吧！甭著急，繼續(xù)往下看）。比如1號頂點有一條邊是 “1 4 9”（該條邊的編號是 1），那么就將 first[1]的值設(shè)為 1。如果某個頂點 i 沒有以該頂點為起始點的邊，則將 first[i]的值設(shè)為-1。現(xiàn)在我們來看看具體如何操作，初始狀態(tài)如下。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/8.4.png" alt="picture8.4" />

咦？上圖中怎么多了一個 next 數(shù)組，有什么作用呢？不著急，待會再解釋，現(xiàn)在先讀入第一條邊“1 4 9”。

讀入第 1 條邊（1 4 9），將這條邊的信息存儲到 u[1]、v[1]和 w[1]中。同時為這條邊賦予一個編號，因為這條邊是最先讀入的，存儲在 u、v 和 w 數(shù)組下標(biāo)為 1 的單元格中，因此編號就是 1。這條邊的起始點是 1 號頂點，因此將 first[1]的值設(shè)為 1。

另外這條“編號為 1 的邊”是以 1 號頂點（即 u[1]）為起始點的第一條邊，所以要將 next[1]的值設(shè)為-1。也就是說，如果當(dāng)前這條“編號為 i 的邊”，是我們發(fā)現(xiàn)的以 u[i]為起始點的第一條邊，就將 next[i]的值設(shè)為-1（貌似的這個 next 數(shù)組很神秘啊⊙_⊙）。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/8.5.png" alt="picture8.5" />

讀入第 2 條邊（4 3 8），將這條邊的信息存儲到 u[2]、v[2]和 w[2]中，這條邊的編號為 2。這條邊的起始頂點是 4 號頂點，因此將 first[4]的值設(shè)為 2。另外這條“編號為 2 的邊”是我們發(fā)現(xiàn)以 4 號頂點為起始點的第一條邊，所以將 next[2]的值設(shè)為-1。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/8.6.png" alt="picture8.6" />

讀入第 3 條邊（1 2 5），將這條邊的信息存儲到 u[3]、v[3]和 w[3]中，這條邊的編號為 3，起始頂點是 1 號頂點。我們發(fā)現(xiàn) 1 號頂點已經(jīng)有一條“編號為 1 的邊”了，如果此時將 first[1]的值設(shè)為 3，那“編號為 1 的邊”豈不是就丟失了？我有辦法，此時只需將 next[3]的值設(shè)為 1即可。現(xiàn)在你知道 next數(shù)組是用來做什么的吧。next[i]存儲的是“編號為i的邊”的“前一條邊”的編號。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/8.7.png" alt="picture8.7" />

讀入第 4 條邊（2 4 6），將這條邊的信息存儲到 u[4]、v[4]和 w[4]中，這條邊的編號為 4，起始頂點是 2 號頂點，因此將 first[2]的值設(shè)為 4。另外這條“編號為 4 的邊”是我們發(fā)現(xiàn)以 2 號頂點為起始點的第一條邊，所以將 next[4]的值設(shè)為-1。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/8.8.png" alt="picture8.8" />

讀入第 5 條邊（1 3 7），將這條邊的信息存儲到 u[5]、v[5]和 w[5]中，這條邊的編號為 5，起始頂點又是 1 號頂點。此時需要將 first[1]的值設(shè)為 5，并將 next[5]的值改為 3。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/8.9.png" alt="picture8.9" />

此時，如果我們想遍歷 1 號頂點的每一條邊就很簡單了。1 號頂點的其中一條邊的編號存儲在 first[1]中。其余的邊則可以通過 next 數(shù)組尋找到。請看下圖。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/8.10.png" alt="picture8.10" />

細(xì)心的同學(xué)會發(fā)現(xiàn)，此時遍歷邊某個頂點邊的時候的遍歷順序正好與讀入時候的順序相反。因為在為每個頂點插入邊的時候都直接插入“鏈表”的首部而不是尾部。不過這并不會產(chǎn)生任何問題，這正是這種方法的其妙之處。

創(chuàng)建鄰接表的代碼如下。

    int n,m,i;
    //u、v和w的數(shù)組大小要根據(jù)實際情況來設(shè)置，要比m的最大值要大1
    int u[6],v[6],w[6];
    //first和next的數(shù)組大小要根據(jù)實際情況來設(shè)置，要比n的最大值要大1
    int first[5],next[5];
    scanf("%d %d",&n,&m);
    //初始化first數(shù)組下標(biāo)1~n的值為-1，表示1~n頂點暫時都沒有邊
    for(i=1;i<=n;i++)
        first[i]=-1;
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d",&u[i],&v[i],&w[i]);//讀入每一條邊
        //下面兩句是關(guān)鍵啦
        next[i]=first[u[i]];
        first[u[i]]=i;
    }

接下來如何遍歷每一條邊呢？我們之前說過其實 first 數(shù)組存儲的就是每個頂點 i（i 從 1~n）的第一條邊。比如 1 號頂點的第一條邊是編號為 5 的邊（1 3 7），2 號頂點的第一條邊是編號為 4 的邊（2 4 6），3 號頂點沒有出向邊，4 號頂點的第一條邊是編號為 2 的邊（2 4 6）。那么如何遍歷 1 號頂點的每一條邊呢？也很簡單。請看下圖：

遍歷 1 號頂點所有邊的代碼如下。

    k=first[1];// 1號頂點其中的一條邊的編號（其實也是最后讀入的邊）
    while(k!=-1) //其余的邊都可以在next數(shù)組中依次找到
    {
        printf("%d %d %d\n",u[k],v[k],w[k]);
        k=next[k];
    }

遍歷每個頂點的所有邊的代碼如下。

    for(i=1;i<=n;i++)
    {
        k=first[i];
        while(k!=-1)
        {
            printf("%d %d %d\n",u[k],v[k],w[k]);
            k=next[k];
        }
    }

可以發(fā)現(xiàn)使用鄰接表來存儲圖的時間空間復(fù)雜度是 O(M)，遍歷每一條邊的時間復(fù)雜度是也是 O(M)。如果一個圖是稀疏圖的話，M 要遠(yuǎn)小于 N2。因此稀疏圖選用鄰接表來存儲要比鄰接矩陣來存儲要好很多。

【啊哈！算法】系列 8：巧妙的鄰接表（數(shù)組實現(xiàn)）
http://ahalei.blog.51cto.com/4767671/1391988