1. 概念

鏈?zhǔn)较蚯靶谴a是基于向前星代碼的優(yōu)化，這是極大多數(shù)算法競賽以及高效率圖論算法喜歡適用的創(chuàng)建方法，與鄰接表和鄰接矩陣比較容易的理解方式，向前星算法并不容易理解。

在理解鏈?zhǔn)较蚯靶侵拔覀冃枰私馐裁词窍蚯靶?，前向星是一種特殊的邊集數(shù)組，我們把邊集數(shù)組中的每一條邊按照起點(diǎn)從小到大排序，如果起點(diǎn)相同就按照終點(diǎn)從小到大排序，并記錄下以某個點(diǎn)為起點(diǎn)的所有邊在數(shù)組中的起始位置和存儲長度,那么前向星就構(gòu)造好了。

鏈?zhǔn)较蚯靶堑谋举|(zhì)是利用鏈表的特性（一個結(jié)點(diǎn)指向另一個結(jié)點(diǎn)），以達(dá)到不需要像向前星那樣排序（排序的平均情況需要O(nlogn)的代價(jià)）就可以直接搜索到目標(biāo)，從而達(dá)到減少計(jì)算機(jī)運(yùn)算時(shí)間使用的情況。

2.結(jié)構(gòu)設(shè)計(jì)

與前文不同，本文我們先展示代碼再做具體講解，鏈?zhǔn)较蚯靶堑慕Y(jié)構(gòu)模板代碼如下：

struct Edge{    //表示邊
    int w;
int to;
    int next;
}edge[10005];
 
int cnt=0;      //用以控制并統(tǒng)計(jì)邊的數(shù)量
 
int head[10005];    //表示來源的邊序號

具體的解釋為：

a)Edge表示邊，這個結(jié)構(gòu)體數(shù)組將逐步記錄邊信息，其中包含有三個元素

l  w為權(quán)重即邊之間的權(quán)值，下圖中為默認(rèn)的1，不演示

l  to表示為第i條邊指向哪一個結(jié)點(diǎn)

l  edge[i].next表示第i條邊的下一條邊的序號

b)Cnt表示邊的數(shù)量，在輸入時(shí)利用他逐個+1

c)Head表示第x個結(jié)點(diǎn)所需要訪問的邊

同樣的我們以這個結(jié)構(gòu)的圖為例，鏈?zhǔn)较蚯靶侵行枰鎯θ缦聝?nèi)容：

（例圖，并且假設(shè)所有邊的權(quán)值均為1）

上圖可以得到一個這樣的運(yùn)算表格（不唯一）

可以見的，比如我們訪問與1相互聯(lián)通的所有結(jié)點(diǎn)，我們首先訪問head[1]的內(nèi)容，head的下標(biāo)表示1結(jié)點(diǎn)，其內(nèi)容表示我們應(yīng)該訪問邊的標(biāo)號，此時(shí)我們得到了數(shù)據(jù)1，表明我們需要訪問邊1，此時(shí)我們找到edge[1]并獲取第一個to的內(nèi)容，表示1結(jié)點(diǎn)與3結(jié)點(diǎn)相連通，接下來訪問next的內(nèi)容，在edge[1].next中獲得了下一條邊的標(biāo)號0，因此接下來訪問edge[0]的內(nèi)容，得到了新得信息，edge[0].to=2，表示1結(jié)點(diǎn)與2結(jié)點(diǎn)相互聯(lián)通，在訪問next的內(nèi)容為-1時(shí)表示沒有下一條了，結(jié)束向下訪問，自此，我們獲得了與1相互聯(lián)通的所有結(jié)點(diǎn)的信息。

因此可以得到如下的信息表：

添加邊信息時(shí)使用以下代碼

void add_edge(int from, int to, int w) {
    edge[cnt].to = to;
    edge[cnt].w = w;
    edge[cnt].next = head[from];
    head[from] = cnt++;
}

注意，我們需要對全體數(shù)組進(jìn)行賦-1的初值，這對于出錯和檢驗(yàn)錯誤都是很有幫助的，因?yàn)?1正是本算法的判定邊界點(diǎn)，當(dāng)然，這個邊界點(diǎn)也可以由自己定位任意一個負(fù)數(shù)。

3. 優(yōu)勢

鏈?zhǔn)较蚯靶堑挠悬c(diǎn)在于高效，訪問速度較快，是圖論算法的熱門構(gòu)建方法，這點(diǎn)在算法競賽中體現(xiàn)尤為重要，缺點(diǎn)也很明顯，不易理解和構(gòu)造麻煩。

鏈?zhǔn)奖旧砭陀性L問此結(jié)點(diǎn)會自動體現(xiàn)下一節(jié)點(diǎn)的效果，因此很適合遍歷和訪問的算法代碼構(gòu)建，這點(diǎn)在后文會提到。

注：建議初學(xué)者多次閱讀本章內(nèi)容