1、、應(yīng)用題1首先將如下圖所示的無向圖給出其存儲結(jié)構(gòu)的鄰接鏈表表示，然后寫出對其分別進(jìn)行深度，廣度優(yōu)先遍歷的結(jié)果。答深度優(yōu)先遍歷序列：125967384寬度優(yōu)先遍歷序列：123456789注：（1）鄰接表不唯一，這里頂點的鄰接點按升序排列（2）在鄰接表確定后，深度優(yōu)先和寬度優(yōu)先遍歷序列唯一（3）這里的遍歷，均從頂點1開始2給出圖G：畫出G的鄰接表表示圖;1）畫出G的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。3.在什么情況下，Prim算法與Kruskual算法生成不同的MST?答.在有相同權(quán)值邊時生成不同的MST,在這種情況下，用Prim或Kruskal也會生成不同的MST4已知一個無向圖如下圖所示，要求分別

2、用Prim和Kruskal算法生成最小樹（假設(shè)以為起點，試畫出構(gòu)造過程）。答.Prim算法構(gòu)造最小生成樹的步驟如24題所示，為節(jié)省篇幅，這里僅用Kruskal算法,構(gòu)造最小生成樹過程如下：（下圖也可選（2,4）代替（3,4）,（5,6）代替（1,5）G=（V,E）是一個帶有權(quán)的連通圖，則：（1）.請回答什么是G的最小生成樹；（2）.G為下圖所示,請找出G的所有最小生成樹。答（1）最小生成樹的定義見上面26題（2）最小生成樹有兩棵。邙限于篇幅，下面的生成樹只給出頂點集合和邊集合，邊以三元組Vi,Vj,W）形式），其中W代表權(quán)值。V（G）=1，2，3，4，5E1（G）=（4，5，2），（2，5，4

3、），（2，3，5），（1，2，7）；E2（G）=（4，5，2），（2，4，4），（2，3，5），（1，2，7）請看下邊的無向加權(quán)圖。（1）.寫出它的鄰接矩陣。（2）.按Prim算法求其最小生成樹,并給出構(gòu)造最小生成樹過程中輔助數(shù)組的各分量值。輔助數(shù)組內(nèi)各分量值：已知世界六大城市為:北京(Pe)、紐約(N)、巴黎(Pa)、倫敦(L)、東京(T)、墨西哥(M),下表給定了這六大城市之間的交通里程：世界六大城市交通里程表(單位:百公里)PENPALTMPE109828121124N109585510832PA825839792L815539589T211089795113M124329289113畫

4、出這六大城市的交通網(wǎng)絡(luò)圖;畫出該圖的鄰接表表示法;畫出該圖按權(quán)值遞增的順序來構(gòu)造的最小(代價)生成樹.8已知頂點1-6和輸入邊與權(quán)值的序列(如右圖所示)：每行三個數(shù)表示一條邊的兩個端點和其權(quán)值，共11行。請你：.采用鄰接多重表表示該無向網(wǎng)，用類PASCAL語言描述該數(shù)據(jù)結(jié)構(gòu)，畫出存儲結(jié)構(gòu)示意圖，要求符合在邊結(jié)點鏈表頭部插入的算法和輸入序列的次序。（2）分別寫出從頂點1出發(fā)的深度優(yōu)先和廣度優(yōu)先遍歷頂點序列，以及相應(yīng)的生成樹。（3）按prim算法列表計算，從頂點1始求最小生成樹，并圖示該樹。1251381432462323443513610457461156159.用最短路徑算法，求如下圖中a到z

5、的最短通路?！荆?）.由頂點VI到頂點V3的最短路徑?！局猩酱髮W(xué)1994四（12分）】9.用最短路徑算法，求如下圖中a到z的最短通路。題10已知圖的鄰接矩陣為：VIV2V3V4V5V6V7V8V9V10V10111000V20001100V30001010V40000011V50000001V60000000V70000000V80000000V90000000V100000000000000000010000110010001001000當(dāng)用鄰接表作為圖的存儲結(jié)構(gòu)，且鄰接表都按序號從大到小排序時，試寫出（1）以頂點V1為出發(fā)點的唯一的深度優(yōu)先遍歷；（2）以頂點V1為出發(fā)點的唯一的廣度優(yōu)先遍歷

6、；（3）該圖唯一的拓?fù)溆行蛐蛄小?1已知一圖如下圖所示：（1）寫出該圖的鄰接矩陣；（2）寫出全部拓?fù)渑判颍唬?）.以v1為源點，以v8為終點，給出所有事件允許發(fā)生的最早時間和最晚時間，并給出關(guān)鍵路徑；（4）求V1結(jié)點到各點的最短距離。12（1）對于有向無環(huán)圖，敘述求拓?fù)溆行蛐蛄械牟襟E；2）對于以下的圖，寫出它的四個不同的拓?fù)溆行蛐蛄小６?算法設(shè)計題設(shè)無向圖G有n個頂點，m條邊。試編寫用鄰接表存儲該圖的算法。(設(shè)頂點值用1n或0n-1編號)答:voidCreatGraph(AdjListg)/建立有n個頂點和m條邊的無向圖的鄰接表存儲結(jié)構(gòu)intn,m;scanf(%d%d,&n,&m);for(

7、i=1,i二n;i+)/輸入頂點信息,建立頂點向量scanf(&gi.vertex);gi.firstarc=null;for(k=1;kadjvex;s=(AreNode*)malloc(sizeof(ArcNode);/申請結(jié)點空間。s-adjvex=i;s-next=ginj.firstare;ginj.firstare=s;p=p-next;/下一個鄰接點。/while/for4試寫一算法，判斷以鄰接表方式存儲的有向圖中是否存在由頂點Vi到頂點Vj的路徑ij(ij)。注意：算法中涉及的圖的基本操作必須在存儲結(jié)構(gòu)上實現(xiàn)。答.題目分析在有向圖中，判斷頂點Vi和頂點Vj間是否有路徑，可采用遍

8、歷的方法，從頂點Vi出發(fā)，不論是深度優(yōu)先遍歷(dfs)還是寬度優(yōu)先遍歷(bfs)，在未退出dfs或bfs前，若訪問到Vj,則說明有通路，否則無通路。設(shè)一全程變量flag。初始化為0若有通路，則flag=1。intvisited=0;/全局變量，訪問數(shù)組初始化intdfs(AdjListg，vi)/以鄰接表為存儲結(jié)構(gòu)的有向圖g，判斷頂點Vi到Vj是否有通路，返回1或0表示有或無visitedvi=1;/visited是訪問數(shù)組，設(shè)頂點的信息就是頂點編號。p=gvi.firstarc;/第一個鄰接點。while(p!=null)j=p-adjvex;if(vj=j)flag=1;return(1)

9、;/vi和vj有通路。if(visitedj=0)dfs(g，j);p=p-next；/whileif(!flag)return(0);/結(jié)束5設(shè)有向圖用鄰接表表示，圖有n個頂點，表示為1至n,試寫一個算法求頂點k的入度(1kn)。答題目分析在有向圖的鄰接表中，求頂點的出度容易，只要簡單在該頂點的鄰接點鏈表中查結(jié)點個數(shù)即可。而求頂點的入度，則要遍歷整個鄰接表。intcount(AdjListg，intk)/在n個頂點以鄰接表表示的有向圖g中，求指定頂點k(1=k=n)的入度。intcount=0;for(i=1;iadjvex=k)count+;p=p-next;/while/ifreturn

10、(count);/頂點k的入度.試編寫求無向圖G的連通分量的算法。要求輸出每一連通分量的頂點值。(設(shè)圖G已用鄰接表存儲)答.題目分析使用圖的遍歷可以求出圖的連通分量。進(jìn)入dfs或bfs一次，就可以訪問到圖的一個連通分量的所有頂點。voiddfs()visitedv=1;printf(“%3d”,v);/輸出連通分量的頂點。p=gv.firstarc;while(p!=null)if(visitedp-adjvex=0)dfs(p-adjvex);p=p-next;/while/dfsvoidCount()/求圖中連通分量的個數(shù)intk=0;staticAdjListg;/設(shè)無向圖g有n個結(jié)點f

11、or(i=1;i0|p!=null)while(p)if(p&visitedp-adjvex)p=p-next;elseprintf(p-adjvex);visitedp-adjvex=1;stack+top=p;p=gp-adjvex.firstarc;/elseif(top0)p=stacktop-;p=p-next;/while/算法結(jié)束。算法討論以上算法適合連通圖，若是非連通圖，則再增加一個主調(diào)算法,其核心語句是for(vi=1;vi=n;vi+)if(!visitedvi)Traver(g,vi);8已知個n頂點的有向圖，用鄰接矩陣表示，編寫函數(shù)計算每對頂點的最短路徑。答本題用FLO

12、YD算法直接求解如下：voidShortPath_FLOYD(AdjMatrixg)/求具有n個頂點的有向圖每對頂點間的最短路徑AdjMatrixlength;/lengthij存放頂點vi到vj的最短路徑長度。for(i=1;i=n;i+)for(j=1;j=n;j+)lengthij=gij;/初始化。for(k=1;k=n;k+)for(i=1;i=n;i+)for(j=1;j=n;j+)if(lengthik+lengthkjlengthij)lengthij=lengthik+lengthkj;/算法結(jié)束9欲用四種顏色對地圖上的國家涂色，有相鄰邊界的國家不能用同一種顏色(點相交不算相

13、鄰)。.試用一種數(shù)據(jù)結(jié)構(gòu)表示地圖上各國相鄰的關(guān)系，(6分)。.描述涂色過程的算法。(不要求證明)(12分)?！菊憬髮W(xué)2002八(18分)】答.題目分析地圖涂色問題可以用“四染色“定理。將地圖上的國家編號1到n),從編號1開始逐一涂色，對每個區(qū)域用1色，2色，3色，4色(下稱“色數(shù)”)依次試探，若當(dāng)前所取顏色與周圍已涂色區(qū)域不重色，則將該區(qū)域顏色進(jìn)棧；否則，用下一顏色。若1至4色均與相鄰某區(qū)域重色，則需退?；厮?修改棧頂區(qū)域的顏色。用鄰接矩陣數(shù)據(jù)結(jié)構(gòu)Cnn描敘地圖上國家間的關(guān)系。n個國家用n階方陣表示，若第i個國家與第j個國家相鄰，則C=1,否則C=0。用棧s記錄染色結(jié)果，棧的下標(biāo)值為區(qū)域號，元素值是色數(shù)。ijijvoidMapColor(AdjMatrixC)/以鄰接矩陣C表示的n個國家的地區(qū)涂色ints;/棧的下標(biāo)是國家編號，內(nèi)容是色數(shù)s1=1；/編號01的國家涂