2018-06-18
今天學(xué)習(xí)了前向星這種數(shù)據(jù)結(jié)構(gòu)，前向星是一種非常節(jié)省空間的存圖方式，在ACM比賽中，常見的的存圖方式有三種。
——鄰接矩陣，即用二維數(shù)組實(shí)現(xiàn)，G[u][v]為<u,v>邊的權(quán)值。鄰接矩陣適用于存儲(chǔ)稠密圖，點(diǎn)不多而邊很多的時(shí)候，鄰接矩陣的優(yōu)點(diǎn)是好寫，可讀性高，方便刪除邊。
——鄰接表，一般用vector<edge>G[MAXN_V]模擬鄰接表，鄰接表適用于疏密圖，相比于鄰接矩陣節(jié)省空間。
其優(yōu)點(diǎn)是寫起來快，可讀性高，方便執(zhí)行STL中的一些函數(shù)。
——前向星，前向星是一種特殊的邊集數(shù)組,我們把邊集數(shù)組中的每一條邊按照起點(diǎn)從小到大排序,如果起點(diǎn)相同就
按照終點(diǎn)從小到大排序,并記錄下以某個(gè)點(diǎn)為起點(diǎn)的所有邊在數(shù)組中的起始位置和存儲(chǔ)長度,那么前向星就構(gòu)造好了.
用len[i]來記錄所有以i為起點(diǎn)的邊在數(shù)組中的存儲(chǔ)長度.，用head[i]記錄以i為邊集在數(shù)組中的第一個(gè)存儲(chǔ)位置.
我們輸入邊的順序?yàn)?
1 2? ? 2 3? ? 3 4? ? 1 3? ? 4 1? ? 1 5? ? 4 5
pair<int,int>G[MAXN_E];
用pair存儲(chǔ)并排序后得到
G[0]=(1,2);?
G[1]=(1,3);
G[2]=(1,5);
G[3]=(2,3);
G[4]=(3,4);
G[5]=(4,1);
G[6]=(4,5);
則head數(shù)組和len數(shù)組為:
head[1]=0;? head[2]=3;? head[3]=4;? ? head[4]=5;? ? head[5]=-1;
len[1]=3;? ? ? len[1]=3;? ? ? len[3]=1;? ? ? ? len[4]=2;? ? ? ? len[5]=0;
但是利用前向星會(huì)有排序操作,如果用快排時(shí)間至少為O(nlog(n))
——如果用鏈?zhǔn)角跋蛐?加入next索引模擬指針指向下一個(gè)點(diǎn)的位置，就可以避免排序.
建立結(jié)構(gòu)體為：
struct edge
{
? ? int to;//邊的終點(diǎn)
? ? int value;//邊的權(quán)值
? ? int next;//表示與第i條邊同起點(diǎn)的下一條邊的存儲(chǔ)位置
};
另外還有一個(gè)數(shù)組head[],它是用來表示以i為起點(diǎn)的索引的第一條邊存儲(chǔ)的位置,實(shí)際上你會(huì)發(fā)現(xiàn)這里的第一條邊存儲(chǔ)的位置其實(shí)
在以i為起點(diǎn)的所有邊的最后輸入的那個(gè)編號(hào).
如果按照索引順序，next表示下一條邊的存儲(chǔ)位置，如果按照添加順序，next即為上一條添加的邊的位置。
所以我們可以得到，輸入順序和存圖順序或者說是遍歷順序是相反的。
還是上面的圖，我們定義全局變量int cnt=0;
并將head[]初始化為-1；
void addedge(int u,int v,int w)
{
? ? e[cnt].value=w;
? ? e[cnt].to=v;
? ? e[cnt].next=head[u];
? ? head[u]=cnt++;
}
模擬插入為下面的過程：
edge[0].to = 2;? ? edge[0].next = -1;? ? ? head[1] = 0;
edge[1].to = 3;? ? edge[1].next = -1;? ? ? head[2] = 1;
edge[2].to = 4;? ? edge[2],next = -1;? ? ? head[3] = 2;
edge[3].to = 3;? ? edge[3].next = 0;? ? ? head[1] = 3;
edge[4].to = 1;? ? edge[4].next = -1;? ? ? head[4] = 4;
edge[5].to = 5;? ? edge[5].next = 3;? ? ? head[1] = 5;
edge[6].to = 5;? ? edge[6].next = 4;? ? ? head[4] = 6;
這樣在遍歷時(shí)是倒著遍歷的,也就是說與輸入順序是相反的,不過這樣不影響結(jié)果的正確性.
比如以上圖為例,以節(jié)點(diǎn)1為起點(diǎn)的邊有3條,它們的編號(hào)分別是0,3,5? 而head[1] = 5
我們?cè)诒闅v以u(píng)節(jié)點(diǎn)為起始位置的所有邊的時(shí)候是這樣的:
for(int i=head[u]; ~i ;i=edge[i].next)
那么就是說先遍歷編號(hào)為5的邊,也就是head[1],然后就是edge[5].next,也就是編號(hào)3的邊,然后繼續(xù)edge[3].next,也
就是編號(hào)0的邊,可以看出是逆序的.
鏈?zhǔn)角跋蛐堑膬?yōu)點(diǎn)：比鄰接表還省空間，可以解決某些卡空間的問題，刪除邊也很方便，只需要更改next指針的指向即可。
總結(jié)：根據(jù)圖的疏密選擇存儲(chǔ)方式，一般情況下用鄰接表，卡空間時(shí)間這些要求比較高的題目或者需要?jiǎng)h除邊操作的用鏈?zhǔn)角跋蛐恰?/b>
——本文部分地方引用了acdream大牛的文章。
