圖的鄰接表存儲(chǔ)方式

圖的鄰接表存儲(chǔ)方式——數(shù)組實(shí)現(xiàn)初探焦作市外國(guó)語中學(xué)岳衛(wèi)華在圖論中，圖的存儲(chǔ)結(jié)構(gòu)最常用的就是就是鄰接表和鄰接矩陣。一旦頂點(diǎn)的個(gè)數(shù)超過5000，鄰接矩陣就會(huì)“爆掉〞空間，那么就只能用鄰接表來存儲(chǔ)。比方noip09的第三題，如果想過掉全部數(shù)據(jù)，就必須用鄰接表來存儲(chǔ)。但是，在平時(shí)的教學(xué)中，發(fā)現(xiàn)用動(dòng)態(tài)的鏈表來實(shí)現(xiàn)鄰接表實(shí)現(xiàn)時(shí)，跟蹤調(diào)試很困難，一些學(xué)生于是就覺得鄰接表的存儲(chǔ)方式很困難。經(jīng)過查找資料，發(fā)現(xiàn)，其實(shí)完全可以用靜態(tài)的數(shù)組來實(shí)現(xiàn)鄰接表。本文就是對(duì)這種方式進(jìn)行探討。我們知道，鄰接表是用一個(gè)一維數(shù)組來存儲(chǔ)頂點(diǎn)，并由頂點(diǎn)來擴(kuò)展和其相鄰的邊。具體表示如下列圖：其相應(yīng)的類型定義如下：typepoint=^node;node=recordv:integer;//另一個(gè)頂點(diǎn)next:point;//下一條邊end;vara:array[1..maxv]ofpoint;而用數(shù)組實(shí)現(xiàn)鄰接表，那么需要定義兩個(gè)數(shù)組：一個(gè)是頂點(diǎn)數(shù)組，一個(gè)是邊集數(shù)組。頂點(diǎn)編號(hào)結(jié)點(diǎn)相臨邊的總數(shù)s第一條鄰接邊next此邊的另一鄰接點(diǎn)邊權(quán)值下一個(gè)鄰接邊對(duì)于上圖來說，具體的鄰接表就是：由上圖我們可以知道，和編號(hào)為1的頂點(diǎn)相鄰的有3條邊，第一條邊在邊集數(shù)組里的編號(hào)是5，而和編號(hào)為5同一個(gè)頂點(diǎn)的下條邊的編號(hào)為3，再往下的邊的編號(hào)是1，那么和頂點(diǎn)1相鄰的3條邊的編號(hào)分別就是5，3，1。同理和頂點(diǎn)3相鄰的3條邊的編號(hào)分別是11，8，4。如果理解數(shù)組表示鄰接表的原理，那么實(shí)現(xiàn)就很容易了。類型定義如下：typenode=record//點(diǎn)集數(shù)組s,next:longint;//s為與第i個(gè)點(diǎn)相臨的邊有多少個(gè)，next為第一條邊的編號(hào)為多少？end;edge=record//邊集數(shù)組y,v,next:longint;//y為這條邊的另一個(gè)頂點(diǎn)，v為權(quán)值，next為和第i個(gè)節(jié)點(diǎn)相臨的另一條邊，next為0那么表示結(jié)束。end;vara:array[1..maxn]ofnode;e:array[1..maxm]ofedge;見圖的代碼和動(dòng)態(tài)鄰接表類似：readln(x1,y1,v1);inc(m);e[m].y:=y1;e[m].v:=v1;e[m].next:=a[x1].next;a[x1].next:=m;inc(a[x1].s);inc(m);e[m].y:=x1;e[m].v:=v1;e[m].next:=a[y1].next;a[y1].next:=m;inc(a[y1].s);下面提供一道例題邀請(qǐng)卡分發(fā)deliver.pas/c/cpp【題目描述】AMS公司決定在元旦之夜舉辦一個(gè)盛大展覽會(huì)，將廣泛邀請(qǐng)各方人士參加?，F(xiàn)在公司決定在該城市中的每個(gè)汽車站派一名員工向過往的行人分發(fā)邀請(qǐng)卡。

但是，該城市的交通系統(tǒng)非常特別，每條公共汽車線路都是單向的，且只包含兩個(gè)車站，即起點(diǎn)站與終點(diǎn)站，汽車從起點(diǎn)到終點(diǎn)站后空車返回。

假設(shè)AMS公司位于1號(hào)車站，每天早上，這些員工從公司出發(fā)，分別到達(dá)各自的崗位進(jìn)行邀請(qǐng)卡的分發(fā)，晚上再回到公司。

請(qǐng)你幫AMS公司編一個(gè)程序，計(jì)算出每天要為這些分發(fā)邀請(qǐng)卡的員工付的交通費(fèi)最少為多少？【輸入文件】輸入文件的第一行包含兩個(gè)整數(shù)P和Q〔1<=P<=10000,0<=Q<=20000〕。P為車站總數(shù)〔包含AMS公司〕，Q為公共汽車線路數(shù)目。接下來有Q行，每行表示一條線路，包含三個(gè)數(shù)：起點(diǎn)，終點(diǎn)和車費(fèi)。所有線路上的車費(fèi)是正整數(shù)，且總和不超過1000000000。并假設(shè)任何兩個(gè)車站之間都可到達(dá)?！据敵鑫募枯敵鑫募H有一行為公司花在分發(fā)邀請(qǐng)卡員工交通上的最少費(fèi)用?！緲永斎搿緾ase1:22

1213

2133Case2：46

1210

2160

1320

3410

245

4150【樣例輸出】Case1：46Case2：210【分析】此題是一道根本最短路徑問題，但是如果想通過全部數(shù)據(jù)，10000個(gè)點(diǎn)，20000條邊，必須用鄰接表來實(shí)現(xiàn)。下面給出此題目用dijkstra和spfa兩種算法的實(shí)現(xiàn)。programdelive_dijstrkalr;constinf='deliver.in';ouf='deliver.out';maxm=20000;maxn=10000;typenode=records,next:longint;//s為與第i個(gè)點(diǎn)相臨的邊有多少個(gè)，next為第一條邊的編號(hào)為多少？end;edge=recordy,v,next:longint;//y為這條邊的另一個(gè)頂點(diǎn)，v為權(quán)值，next為和第i個(gè)節(jié)點(diǎn)相臨的另一條邊，next為0那么表示結(jié)束。end;vari,j,k,m,n,x1,y1,w1,ans:longint;a,a1:array[1..maxn]ofnode;e,e1:array[1..maxm]ofedge;d,d1:array[1..maxn]oflongint;proceduredij;vari,j,k,min,jj,kk:longint;f:array[1..maxn]ofboolean;beginfillchar(d,sizeof(d),$7f);fillchar(f,sizeof(f),false);j:=a[1].next;fori:=1toa[1].sdobegink:=e[j].y;d[k]:=e[j].v;j:=e[j].next;end;//用鄰接表來找和第1個(gè)點(diǎn)相臨的點(diǎn)，并給d數(shù)組賦初值。。。。f[1]:=true;d[1]:=0;fori:=2tondobeginmin:=maxlongint;k:=0;forj:=1tondoif(notf[j])and(d[j]<min)thenbeginmin:=d[j];k:=j;end;ifk=0thenexit;f[k]:=true;jj:=a[k].next;forj:=1toa[k].sdobeginkk:=e[jj].y;if(notf[kk])and(d[k]+e[jj].v<d[kk])thend[kk]:=d[k]+e[jj].v;jj:=e[jj].next;end;//鄰接表的使用，要好好注意。。。end;end;beginassign(input,inf);reset(input);assign(output,ouf);rewrite(output);fillchar(a,sizeof(a),0);fillchar(e,sizeof(e),0);fillchar(a1,sizeof(a1),0);fillchar(e1,sizeof(e1),0);readln(n,m);fori:=1tomdobeginreadln(x1,y1,w1);e[i].y:=y1;e[i].v:=w1;e[i].next:=a[x1].next;a[x1].next:=i;inc(a[x1].s);e1[i].y:=x1;e1[i].v:=w1;e1[i].next:=a1[y1].next;a1[y1].next:=i;inc(a1[y1].s);end;dij;d1:=d;a:=a1;e:=e1;dij;ans:=0;fori:=2tondoans:=ans+d[i]+d1[i];writeln(ans);close(input);close(output);gramdeliver;constinf='deliver.in';ouf='deliver.out';maxm=20000;maxn=10000;typenode=records,next:longint;//s為與第i個(gè)點(diǎn)相臨的邊有多少個(gè)，next為第一條邊的編號(hào)為多少？end;edge=recordy,v,next:longint;//y為這條邊的另一個(gè)頂點(diǎn)，v為權(quán)值，next為和第i個(gè)節(jié)點(diǎn)相臨的另一條邊，next為0那么表示結(jié)束。end;vari,j,k,m,n,x1,y1,w1,ans:longint;a,a1:array[1..maxn]ofnode;e,e1:array[1..maxm]ofedge;d,d1:array[1..maxn]oflongint;q:array[1..100000]oflongint;procedurespfa;//spfa是基于邊的松弛操作的最短路徑求法。根本原理就是vari,j,k,now,min,t,w:longint;f:array[1..maxn]ofboolean;beginfillchar(d,sizeof(d),$7f);fillchar(f,sizeof(f),false);fillchar(q,sizeof(q),0);d[1]:=0;t:=1;f[1]:=true;w:=1;q[t]:=1;repeatk:=q[t];j:=a[k].next;fori:=1toa[k].sdobeginnow:=e[j].y;ifd[now]>d[k]+e[j].vthenbegind[now]:=d[k]+e[j].v;ifnotf[now]thenbegininc(w);q[w]:=now;f[now]:=true;end;end;j:=e[j].next;end;f[k]:=false;inc(t);untilt>w;end;beginassign(input,inf);reset(input);assign(output,ouf);rewrite(output);fillchar(a,sizeof(a),0);fillchar(e,sizeof(e),0);fillchar(a1,sizeof(a1),0);fillchar(e1,sizeof(e1),0);readln(n,m);fori:=1tomdobeginreadln(x1,y1,w1);e[i].y:=y1;e[i].v:=w1;e[i].next:=a[x1].next;a[x1].next:=i;