圖練習(xí)與答案

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

4.已知一個(gè)無(wú)向圖如下圖所示，要求分別用Prim和Kruskal算法生成最小樹（假設(shè)以①為起點(diǎn)，試畫出構(gòu)造過程）O答.Prim算法構(gòu)造最小生成樹的步驟如構(gòu)造最小生成樹過程如下：（下圖也可選24題所示，為節(jié)省篇幅，這里僅用Kruskal算法,4.已知一個(gè)無(wú)向圖如下圖所示，要求分別用Prim和Kruskal算法生成最小樹（假設(shè)以①為起點(diǎn)，試畫出構(gòu)造過程）O答.Prim算法構(gòu)造最小生成樹的步驟如構(gòu)造最小生成樹過程如下：（下圖也可選24題所示，為節(jié)省篇幅，這里僅用Kruskal算法,(2,4)代替(3,4),(5,6)代替(1,5))1105211G=（V,E）是一個(gè)帶有權(quán)的連通圖，則：.請(qǐng)回答什么是G的最小生成樹；.G為下圖所示，請(qǐng)找出G的所有最小生成樹。答.（1）最小生成樹的定義見上面26題（2）最小生成樹有兩棵。答.（1）最小生成樹的定義見上面26題（2）最小生成樹有兩棵。（限于篇幅，下面的生成樹只給出頂點(diǎn)集合和邊集合，邊以三元組（W弋表權(quán)值。Vi,Vj,W)形式），其中V(G)={1,2,3,4,5}E1(G)={(4,5,2),(2,5,4),(2,3,5),E2(G尸{(4,5,2),(2,4,4),(2,3,5),(1,2,7)};(1，2,7)}6.請(qǐng)看下邊的無(wú)向加權(quán)圖。（1）.寫出它的鄰接矩陣。（2）.按Prim算法求其最小生成樹,并給出構(gòu)造最小生成樹過程中輔助數(shù)組的各分量值。輔助數(shù)組內(nèi)各分量值：YClosedge2345678UV.-UVexLowcostVexLowcostVexLowcostVexLowcostVexLowcostVexLowcostVexLowcostVexLowcost7.已知世界六大城市為：北京(Pe)、紐約(N)、巴黎(Pa)、倫敦(L)、東京(T)、墨西哥(M),下表給定了這六大城市之間的交通里程：世界六大城市交通里程表(單位：百公里)PENPALTMPE109828121124N109585510832PA825839792L815539589T211089795113M124329289113(1).畫出這六大城市的交通網(wǎng)絡(luò)圖；(2).畫出該圖的鄰接表表示法；(3).畫出該圖按權(quán)值遞增的順序來(lái)構(gòu)造的最小(代價(jià))生成樹.8.已知頂點(diǎn)1-6和輸入邊與權(quán)值的序列(如右圖所示)：每行三個(gè)數(shù)表示一條邊的兩個(gè)端點(diǎn)和其權(quán)值，共11行。請(qǐng)你：.采用鄰接多重表表示該無(wú)向網(wǎng)，用類PASCA陰言描述該數(shù)據(jù)結(jié)構(gòu)，畫出存儲(chǔ)結(jié)構(gòu)示意圖，要求符合在邊結(jié)點(diǎn)鏈表頭部插入的算法和輸入序列的次序。.分別寫出從頂點(diǎn)1出發(fā)的深度優(yōu)先和廣度優(yōu)先遍歷頂點(diǎn)序列，以及相應(yīng)的生成樹。.按prim算法列表計(jì)算，從頂點(diǎn)1始求最小生成樹，并圖示該樹。1251381432462323443513610457461156159.用最短路徑算法，求如下圖中a到z的最短通路。【(4).由頂點(diǎn)V1到頂點(diǎn)V3的最短路徑?！局猩酱髮W(xué)1994四(12分)】.用最短路徑算法，求如下圖中a到z的最短通路。.已知圖的鄰接矩陣為:

V1V2V3V4V5V6V7V8V9V10V10111000000V20001100000V30001010000V40000011010V50000001000V60000000110V70000000010V80000000001V90000000001V100000000000當(dāng)用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)，且鄰接表都按序號(hào)從大到小排序時(shí)，試寫出(1).以頂點(diǎn)V1為出發(fā)點(diǎn)的唯一的深度優(yōu)先遍歷;(2).以頂點(diǎn)V1為出發(fā)點(diǎn)的唯一的廣度優(yōu)先遍歷;(3).該圖唯一的拓?fù)溆行蛐蛄小?已知一圖如下圖所示：.寫出該圖的鄰接矩陣；.寫出全部拓?fù)渑判颍?以v1為源點(diǎn)，以v8為終點(diǎn)，給出所有事件允許發(fā)生的最早時(shí)間和最晚時(shí)間，并給出關(guān)鍵路徑；.求V1結(jié)點(diǎn)到各點(diǎn)的最短距離。(1).對(duì)于有向無(wú)環(huán)圖，敘述求拓?fù)溆行蛐蛄械牟襟E；2).對(duì)于以下的圖，寫出它的四個(gè)不同的拓?fù)溆行蛐虼鮑。.設(shè)無(wú)向圖G有n個(gè)頂點(diǎn)，m條邊。試編寫用鄰接表存儲(chǔ)該圖的算法。(設(shè)頂點(diǎn)值用1?n或0?n-1編號(hào))答：voidCreatGraph(AdjListg)//建立有n個(gè)頂點(diǎn)和m條邊的無(wú)向圖的鄰接表存儲(chǔ)結(jié)構(gòu){intn,m;scanf("%d%d",&n,&m);for(i=1,i<=n;i++)〃輸入頂點(diǎn)信息，建立頂點(diǎn)向量{scanf(&g[i].vertex);g[i].firstarc=null;}for(k=1;k<=m;k++)//輸入邊信息{scanf(&v1,&v2);//輸入兩個(gè)頂點(diǎn)i=GraphLocateVertex(g,v1);j=GraphLocateVertex(g,v2);//頂點(diǎn)定位p=(ArcNode*)malloc(sizeof(ArcNode));//申請(qǐng)邊結(jié)點(diǎn)p->adjvex=j;p->next=g[i].firstarc;g[i].firstarc=p;//將邊結(jié)點(diǎn)鏈入p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=i;p->next=g[j].firstarc;g[j].frstarc=p;}}//算法CreatGraph結(jié)束.請(qǐng)用流程圖或類高級(jí)語(yǔ)言(c)表示算法。已知有向圖有n個(gè)頂點(diǎn)，請(qǐng)寫算法，根據(jù)用戶輸入的偶對(duì)建立該有向圖的鄰接表。即接受用戶輸入的<vi,vj>(以其中之一為0標(biāo)志Z束)，對(duì)于每條這樣的邊，申請(qǐng)一個(gè)結(jié)點(diǎn)，并插入到的單鏈表中，如此反復(fù)，直到將圖中所有邊處理完畢。提示：先產(chǎn)生鄰接表的n個(gè)頭結(jié)點(diǎn)(其結(jié)點(diǎn)數(shù)值域從1到n)。答.voidCreatAdjList(AdjListg)//建立有向圖的鄰接表存儲(chǔ)結(jié)構(gòu){intn;scanf("%d",&n);for(i=1;i<=n;j++){scanf(&g[i].vertex);g[i].firstarc=null;}〃輸入頂點(diǎn)信息scanf(&v1,.&v2);while(v1&&v2)//題目要求兩頂點(diǎn)之一為0表示結(jié)束{i=GraphLocateVertex(g2,v1);p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->next=g[i].firstarc;g[i].firstarc=p;scanf(&v1,&v2);}}.設(shè)有向G圖有n個(gè)點(diǎn)(用1,2,…,n表示),e條邊，寫一算法根據(jù)其鄰接表生成其反向鄰接表，要求算法復(fù)雜性為O(n+e)。答.

voidInvertAdjList(AdjListgin,gout)//將有向圖的出度鄰接表改為按入度建立的逆鄰接表{for(i=1;i<=n;i++)〃設(shè)有向圖有n個(gè)頂點(diǎn)，建逆鄰接表的頂點(diǎn)向量。{gin[i].vertex=gout[i].vertex;gin.firstarc=null;}for(i=1;i<=n;i++)//鄰接表轉(zhuǎn)為逆鄰接表。{p=gout[i].firstarc;//取指向鄰接表的指針。while(p!=null){j=p->adjvex;s=(ArcNode*)malloc(sizeof(ArcNode));//申請(qǐng)結(jié)點(diǎn)空間。s->adjvex=i;s->next=gin[j].firstarc;gin[j].firstarc=s;p=p->next;//下一個(gè)鄰接點(diǎn)。}//while}//for}.試寫一算法，判斷以鄰接表方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)V到頂點(diǎn)V的路徑(i<>j)。注意：算法中涉及的圖的基本操作必須在存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)。答.[題目分析]在有向圖中，判斷頂點(diǎn)Vi和頂點(diǎn)Vj間是否有路徑，可采用遍歷的方法，從頂點(diǎn)Vi出發(fā)，不論是深度優(yōu)先遍歷(dfs)還是寬度優(yōu)先遍歷(bfs),在未退出dfs或bfs前，若訪問到Vj,則說明有通路，否則無(wú)通路。設(shè)一全程變量flag。初始化為0,若有通路，則flag=1。intvisited[]=0;//全局變量，訪問數(shù)組初始化intdfs(AdjListg,vi)//以鄰接表為存儲(chǔ)結(jié)構(gòu)的有向圖g,判斷頂點(diǎn)Vi到Vj是否有通路，返回1或0表示有或無(wú){visited[vi]=1;//visited是訪問數(shù)組，設(shè)頂點(diǎn)的信息就是頂點(diǎn)編號(hào)。p=g[vi].firstarc;//第一個(gè)鄰接點(diǎn)。while(p!=null){j=p->adjvex;if(vj==j){flag=1;return(1);}//vi和vj有通路。if(visited[j]==0)dfs(g,j);p=p->next;}//whileif(!flag)return(0);}//結(jié)束.設(shè)有向圖用鄰接表表示，圖有n個(gè)頂點(diǎn)，表示為1至n,試寫一個(gè)算法求頂點(diǎn)k的入度(1<k<n)。答.[題目分析]在有向圖的鄰接表中，求頂點(diǎn)的出度容易，只要簡(jiǎn)單在該頂點(diǎn)的鄰接點(diǎn)鏈表中查結(jié)點(diǎn)個(gè)數(shù)即可。而求頂點(diǎn)的入度，則要遍歷整個(gè)鄰接表。intcount(AdjListg,intk){intcount=0;for(i=1;i<=n;i++)//

if(i!=k)//{p=g[i].firstarc;////在{intcount=0;for(i=1;i<=n;i++)//

if(i!=k)//{p=g[i].firstarc;//求頂點(diǎn)k的入度要遍歷整個(gè)鄰接表。頂點(diǎn)k的鄰接鏈表不必計(jì)算取頂點(diǎn)i的鄰接表。while(p){if(p->adjvex==k)count++;p=p->next;}//while}//ifreturn(count);//頂點(diǎn)k的入度.}.試編寫求無(wú)向圖G的連通分量的算法。要求輸出每一連通分量的頂點(diǎn)值。(設(shè)圖G已用鄰接表存儲(chǔ))答.[題目分析]使用圖的遍歷可以求出圖的連通分量。進(jìn)入dfs或bfs一次，就可以訪問到圖的一個(gè)連通分量的所有頂點(diǎn)。voiddfs(){visited[v]=1;printf("%3d,v);//輸出連通分量的頂點(diǎn)。p=g[v].firstarc;while(p!=null){if(visited[p->adjvex==0])dfs(p->adjvex);p=p->next;}//while}//dfsvoidCount()//求圖中連通分量的個(gè)數(shù){intk=0;staticAdjListg;//設(shè)無(wú)向圖g有n個(gè)結(jié)點(diǎn)for(i=1;i<=n;i++)if(visited[i]==0){printf("\n第％~個(gè)連通分量：\n",++k);dfs(i);}//if}//Count算法中visited口數(shù)組是全程變量，每個(gè)連通分量的頂點(diǎn)集按遍歷順序輸出。這里設(shè)頂點(diǎn)信息就是頂點(diǎn)編號(hào)，否則應(yīng)取其g[i].vertex分量輸出。.寫出圖的深度優(yōu)先搜索DFS算法的非遞歸算法。答.voidTraver(AdjListg,vertypev)//圖g以鄰接表為存儲(chǔ)結(jié)構(gòu)，算法從頂點(diǎn)v開始實(shí)現(xiàn)非遞歸深度優(yōu)先遍歷。{structarc*stack口；visited[v]=1;printf(v);//輸出頂點(diǎn)vtop=0;p=g[v].firstarc;stack[++top]=p;while(top>0||p!=null){while(p)if(p&&visited[p->adjvex])p=p->next;else{printf(p->adjvex);visited[p->adjvex]=1;stack[++top]=p;p=g[p->adjvex].firstarc;}//elseif(top>0){p=stack[top--];p=p->next;}}//while}//算法結(jié)束。[算法討論]以上算法適合連通圖，若是非連通圖，則再增加一個(gè)主調(diào)算法，其核心語(yǔ)句

是for(vi=1;vi<=n;vi++)是for(vi=1;vi<=n;vi++)if(!visited[vi])Traver(g,vi);已知個(gè)n頂點(diǎn)的有向圖，用鄰接矩陣表示，編寫函數(shù)計(jì)算每對(duì)頂點(diǎn)的最短路徑。答.本題用FLOYDT法直接求解如下：voidShortPath_FLOYD(AdjMatrixg)//求具有n個(gè)頂點(diǎn)的有向圖每對(duì)頂點(diǎn)間的最短路徑{AdjMatrixlength;//length[i][j]存放頂點(diǎn)vi到vj的最短路徑長(zhǎng)度。for(i=1;i<=n;i++)for(j=1;j<=n;j++)length[i][j]=g[i][j];//初始化。for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(length[i][k]+length[k][j]<length[i][j])length[i][j]=length[i][k]+length[k][j];}//算法結(jié)束欲用四種顏色對(duì)地圖上的國(guó)家涂色，有相鄰邊界的國(guó)家不能用同一種顏色(點(diǎn)相交不算相鄰)。.試用一種數(shù)據(jù)結(jié)構(gòu)表示地圖上各國(guó)相鄰的關(guān)系，(6分)。.描述