【坐在馬桶上看算法】算法8：巧妙的鄰接表（數(shù)組實(shí)現(xiàn)）

作者：ahalei 2014-04-08 15:52:03

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

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

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

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

首先我們按照讀入的順序?yàn)槊恳粭l邊進(jìn)行編號(hào)（1~m）。比如***條邊“1 4 9”的編號(hào)就是1，“1 3 7”這條邊的編號(hào)是5。

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

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

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

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

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

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

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

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

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

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

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

int n,m,i;   
//u、v和w的數(shù)組大小要根據(jù)實(shí)際情況來設(shè)置，要比m的***值要大1   
int u[6],v[6],w[6];   
//first和next的數(shù)組大小要根據(jù)實(shí)際情況來設(shè)置，要比n的***值要大1   
int first[5],next[5];   
scanf("%d %d",&n,&m);   
//初始化first數(shù)組下標(biāo)1~n的值為-1，表示1~n頂點(diǎn)暫時(shí)都沒有邊   
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;   
}

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

遍歷1號(hào)頂點(diǎn)所有邊的代碼如下。

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

遍歷每個(gè)頂點(diǎn)的所有邊的代碼如下。

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];   
    }   
}