算法與數(shù)據(jù)結構 C語言版 第二版 (陳守孔 孟佳娜 武秀川 著) 機械工業(yè)出版社課后答案 第7章 圖

第 7 章 圖一、基礎知識題 7.1設無向圖的頂點個數(shù)為n，則該圖最多有多少條邊？【解答】n(n-1)/2 7.2一個n個頂點的連通無向圖，其邊的個數(shù)至少為多少？【解答】n-1  7.3要連通具有n個頂點的有向圖，至少需要多少條弧?【解答】n 7.4 n個頂點的完全有向圖含有弧的數(shù)目是多少?【解答】n(n-1) 7.5一個有n個頂點的無向圖，最少有多少個連通分量，最多有多少個連通分量?！窘獯稹?, n 7.6圖的BFS生成樹的樹高要小于等于同圖DFS生成樹的樹高，對嗎？【解答】對 7.7無向圖G=(V,E)，其中：V=a,b,c,d,e,f，E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，寫出對該圖從頂點a出發(fā)進行深度優(yōu)先遍歷可能得到的全部頂點序列。【解答】abedfc, acfdeb, aebdfc, aedfcb 7.8 在圖采用鄰接表存儲時，求最小生成樹的 Prim 算法的時間復雜度是多少？【解答】O(n+e) 7.9若一個具有n個頂點，e條邊的無向圖是一個森林，則該森林中必有多少棵樹？【解答】n-e 7.10 n個頂點的無向圖的鄰接矩陣至少有多少非零元素？【解答】0 7.11證明:具有n個頂點和多于n-1條邊的無向連通圖G一定不是樹。【證明】具有n個頂點n-1條邊的無向連通圖是自由樹，即沒有確定根結點的樹，每個結點均可當根。若邊數(shù)多于n-1條，因一條邊要連接兩個結點，則必因加上這一條邊而使兩個結點多了一條通路，即形成回路。形成回路的連通圖不再是樹。 7.12證明對有向圖頂點適當編號，使其鄰接矩陣為下三角形且主對角線為全零的充要條件是該圖是無環(huán)圖?！咀C明】該有向圖頂點編號的規(guī)律是讓弧尾頂點的編號大于弧頭頂點的編號。由于不允許從某頂點發(fā)出并回到自身頂點的弧，所以鄰接矩陣主對角元素均為0。先證明該命題的充分條件。由于弧尾頂點的編號均大于弧頭頂點的編號，在鄰接矩陣中，非零元素（Aij=1）自然是落到下三角矩陣中；命題的必要條件是要使上三角為0，則不允許出現(xiàn)弧頭頂點編號大于弧尾頂點編號的弧，否則，就必然存在環(huán)路。（對該類有向無環(huán)圖頂點編號，應按頂點出度的大小進行順序編號。） 7.13設G=(V，E)以鄰接表存儲，如圖所示，試畫出從頂點1出發(fā)所得到的深度優(yōu)先和廣度優(yōu)先生成樹。        習題7.13 的圖【解答】深度優(yōu)先生成樹12345   寬度優(yōu)先生成樹：12345       7.14 已知一個圖的頂點集V和邊集E分別為：V=0，1，2，3，4，5，6，7；E=<0，2>，<1，3>，<1，4>，<2，4>，<2，5>，<3，6>，<3，7>，<4，7>，<4，8>，<5，7>，<6，7>，<7，8>；若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照頂點序號從小到大的次序鏈接的，則按教材中介紹的進行拓撲排序的算法，寫出得到的拓撲序列。【解答】1-3-6-0-2-5-4-7-8  7.15一帶權無向圖的鄰接矩陣如下圖 ，試畫出它的一棵最小生成樹。 習題7.15 的圖 習題7.16 的圖【解答】設頂點集合為1，2，3，4，5，6， 由下邊的邏輯圖可以看出，在1，2，3和4，5，6回路中，各任選兩條邊，加上（2，4），則可構成9棵不同的最小生成樹。 12111113123456       7.16如圖所示是一帶權有向圖的鄰接表法存儲表示。其中出邊表中的每個結點均含有三個字段，依次為邊的另一個頂點在頂點表中的序號、邊上的權值和指向下一個邊結點的指針。試求：（1）該帶權有向圖的圖形；（2）從頂點V1為起點的廣度優(yōu)先遍歷的頂點序列及對應的生成樹；（3）以頂點V1為起點的深度優(yōu)先遍歷生成樹；（4）由頂點V1到頂點V3的最短路徑。333625181029383042143265【解答】(1)       (2)V1,V2,V4,V6,V3,V5124635       (3)  頂點集合V(G)=V1,V2,V3,V4,V5,V6 邊的集合 E(G)=<V1,V2>,<V2,V3>,<V1,V4>,<V4,V5>,<V5,V6>(4)  V1到V3最短路徑為67: (V1V4V3) 迭代 集合 S 選擇頂點 D D2 D3 D4 D5 D6初值 v1  33 29 251v1, v6v6 33 29 252 v1, v6, v4v433 67 29 71 3 v1, v6, v4, v2v233 67 71 4v1,v6, v4, v2,v3v3 67 71 5v1,v6,v4, v2,v3,v5v 71          7.17已知一有向網(wǎng)的鄰接矩陣如下，如需在其中一個頂點建立娛樂中心，要求該頂點距其它各頂點的最長往返路程最短，相同條件下總的往返路程越短越好，問娛樂中心應選址何處？給出解題過程。習題7.18的圖 習題7.17 的圖【解答】下面用FLOYD算法求出任意兩頂點的最短路徑（如圖A（6）所示）。題目要求娛樂中心“距其它各結點的最長往返路程最短”，結點V1，V3，V5和V6最長往返路徑最短都是9。按著“相同條件下總的往返路徑越短越好”，選頂點V5，總的往返路徑是34。A(0)= A(1)= A(2)= A(3)= A(4)= A(5)= A(6)= 7.18求出圖中頂點1到其余各頂點的最短路徑?！窘獯稹勘颈碇蠨IST中各列最下方的數(shù)字是頂點1到頂點的最短通路。 所選頂點S（已確定最短路徑的頂點集合）T(尚未確定最短路徑的頂點集合) DIST2345678初態(tài)12,3,4,5,6,7,830¥6010¥¥¥5 1,52,3,4,6,7,825¥601017¥¥61,5,62,3,4,7,8 203360 1725¥21,5,6,23,4,7,8203360  25¥71,5,6,2,73,4,8 3128  253541,5,6,2,7,43,8 3128   3531,5,6,2,7,4,35,8 31    3581,5,6,2,7,4,3,88      35頂點1到其它頂點的最短路徑依次是20，31，28，10，17，25，35。按Dijkstra算法所選頂點依次是5，6，2，7，4，3，8。  7.19對圖示的AOE網(wǎng)絡，計算各活動弧的e(ai)和l(ai)的函數(shù)值，各事件（頂點）的ve（vi）和vl (vi)的函數(shù)值，列出各條關鍵路徑?！窘獯稹宽旤cABCDEFGHWVe(i)016342413392252Vl(i)02924373113392252 活動a1a2a3a4a5a6a7a8a9a10a11a12a13a14a15a16a17e(i)000016633424131313392222l(i)281803292431343731203613392240aCFHGW，長52。 關鍵路徑是：  活動與頂點的對照表：a1<,A> a2<,B> a3<,C> a4<,D> a5<A,E> a6<B,E> a7<B,W> a8<C,G>a9<C,F> a10<D,F> a11<E,G> a12<F,E> a13<F,W> a14<F,H> a15<G,W> a16<H,G> a17<H,W> 7.20            利用弗洛伊德算法，寫出如圖所示相應的帶權鄰接矩陣的變化。3214596823110           【解答】A0= A1= A2= A3= A4=  二、算法設計題7.21 設無向圖G有n個頂點，m條邊。試編寫用鄰接表存儲該圖的算法。void CreatGraph (AdjList g)建立有n個頂點和m 條邊的無向圖的鄰接表存儲結構int n,m; scanf("%d%d",&n,&m);for(i=0,i<n;i+)輸入頂點信息,建立頂點向量 scanf(&gi.vertex); gi.firstarc=null;for(k=0;k<m;k+)輸入邊信息scanf(&v1,&v2);輸入兩個頂點i=GraphLocateVertex (g,v1); j=GraphLocateVertex (g,v2);頂點定位p=(ArcNode *)malloc(sizeof(ArcNode);申請邊結點p->adjvex=j; p->next=gi.firstarc; gi.firstarc=p; 將邊結點鏈入 p=(ArcNode *)malloc(sizeof(ArcNode);p->adjvex=i;p->next=gj.firstarc;gj.frstarc=p;for 算法CreatGraph結束 7.22 已知有向圖有n個頂點，請編寫算法，根據(jù)用戶輸入的偶對建立該有向圖的鄰接表。void CreatAdjList(AdjList g)建立有向圖的鄰接表存儲結構int n;scanf("%d",&n);for(i=0;i<n;j+)scanf(&gi.vertex); gi.firstarc=null;輸入頂點信息,下標從0開始scanf(&v1,.&v2); while(v1 && v2)題目要求兩頂點之一為0表示結束 i=GraphLocateVertex(g,v1); p=(ArcNode*)malloc(sizeof(ArcNode); p->adjvex=j;p->next=gi.firstarc;gi.firstarc=p;scanf(&v1,&v2);while  7.23 給出以十字鏈表作存儲結構，建立圖的算法，輸入(i，j，v)其中i，j為頂點號，v為權值。void CreatOrthList(OrthList g)建立有向圖的十字鏈表存儲結構int i,j,v; 假定權值為整型scanf("%d",&n);for(i=0,i<n;i+) 建立頂點向量 scanf(&gi.vertex); gi.firstin=null; gi.firstout=null; scanf("%d%d%d",&i,&j,&v); while(i && j && v) 當輸入i,j,v之一為0時,結束算法運行 p=(OrArcNode *)malloc(sizeof(OrArcNode); 申請結點 p->headvex=j;p->tailvex=i;p->weight=v;弧結點中權值域 p->headlink=gj.firstin; gj.firstin=p; p->tailink=gi.firstout; gi.firstout=p;scanf("%d%d%d",&i,&j,&v);while 算法結束算法討論 本題已假定輸入的i和j是頂點號,否則,頂點的信息要輸入,且用頂點定位函數(shù)求出頂點在頂點向量中的下標。圖建立時，若已知邊數(shù)（如上面1和2題），可以用for循環(huán)；若不知邊數(shù)，可用while循環(huán)（如本題），規(guī)定輸入特殊數(shù)（如本題的零值）時結束運行。本題中數(shù)值設為整型，否則應以和數(shù)值類型相容的方式輸入。 7.24 設有向圖G有n個點(用1，2，n表示)，e條邊，寫一算法根據(jù)G的鄰接表生成G的反向鄰接表，要求算法時間復雜性為O(n+e)。void InvertAdjList(AdjList gin,gout)將有向圖的出度鄰接表改為按入度建立的逆鄰接表 for(i=0;i<n;i+)設有向圖有n個頂點，建逆鄰接表的頂點向量。 gini.vertex=gouti.vertex; gini.firstarc=null; for(i=0;i<n;i+) 鄰接表轉為逆鄰接表。 p=gouti.firstarc;取指向鄰接點的指針 while(p!=null) j=p->adjvex; s=(ArcNode *)malloc(sizeof(ArcNode);申請結點空間 s->adjvex=i; s->next=ginj.firstarc; ginj.firstarc=s; p=p->next;下一個鄰接點。 while for  7.25 寫出從圖的鄰接表表示轉換成鄰接矩陣表示的算法。void AdjListToAdjMatrix(AdjList gl, AdjMatrix gm)將圖的鄰接表表示轉換為鄰接矩陣表示for(i=0;i<n;i+) 設圖有n個頂點，鄰接矩陣初始化 for(j=0;j<n;j+) gmij=0; for(i=0;i<n;i+) 取第一個鄰接點，填鄰接矩陣元素值，并求下一個鄰接點 p=gli.firstarc; while(p!=null) gmip->adjvex=1;p=p->next; for 算法結束 7.26 試寫出把圖的鄰接矩陣表示轉換為鄰接表表示的算法。void AdjMatrixToAdjList(AdjMatrix gm, AdjList gl)將圖的鄰接矩陣表示轉換為鄰接表表示for(i=0;i<n;i+) 鄰接表表頭向量初始化。 scanf(&gli.vertex); gli.firstarc=null; for(i=0;i<n;i+) for(j=0;j<n;j+) if(gmij=1) p=(ArcNode *)malloc(sizeof(ArcNode) ;申請結點空間p->adjvex=j;頂點I的鄰接點是jp->next=gli.firstarc; gli.firstarc=p; 鏈入頂點i的鄰接點鏈表中if end 7.27 試編寫建立有n個頂點，m條邊且以鄰接多重表為存儲結構表示的無向圖的算法。void CreatMGraph(AdjMulist g)建立有n個頂點e條邊的無向圖的鄰接多重表的存儲結構int n,e;scanf("%d%d",&n,&e); for(i=0,i<n;i+) 建立頂點向量 scanf(&gi.vertex);gi.firstedge=null; for(k=0;k<e;k+) 建立邊結點scanf(&v1,&v2); i=GraphLocateVertex(g,v1);j=GraphLocateVertex(g,v2);p=(ENode *)malloc(sizeof(ENode);p->ivex=i; p->jvex=j; p->ilink=gi.firstedge; p->jlink=gj.firstedge;gi.firstedge=p; gj.firstedge=p;for 算法結束 7.28 已知某有向圖（n個結點）的鄰接表，求該圖各結點的入度數(shù)?！绢}目分析】在有向圖的鄰接表存儲結構中求頂點的入度，需要遍歷整個鄰接表。void Indegree(AdjList g)求以鄰接表為存儲結構的n個頂點有向圖的各頂點入度for(i=0;i<n;j+)num=0;入度初始為0for(j=0;j<n;j+) 遍歷整個鄰接表，求一個頂點的入度if(i!=j)p=gj.firstarc; while(p) if(p->adjvex=i) num+; p=p->next; printf(“頂點%d的入度為：%dn”,gi.vexdata,num); 設頂點數(shù)據(jù)為整型  7.29 已知無向圖G=(V，E)，給出求圖G的連通分量個數(shù)的算法?！绢}目分析】使用圖的遍歷可以求出圖的連通分量。進入dfs或bfs一次，就可以訪問到圖的一個連通分量的所有頂點。void dfs (v)visitedv=1; printf (“%3d”,v); 輸出連通分量的頂點。p=gv.firstarc;while(p!=null) if（visitedp->adjvex=0） dfs(p->adjvex); p=p->next;while dfs void Count() 求圖中連通分量的個數(shù) int k=0 ; static AdjList g ; 設無向圖g有n個結點 for(i=0;i<n;i+ ) if(visitedi=0) printf ("n第%d個連通分量:n",+k); dfs(i);if Count【算法討論】算法中visited數(shù)組是全程變量，每個連通分量的頂點集按遍歷順序輸出。這里設頂點信息就是頂點編號，否則應取其gi.vertex分量輸出。 7.30 已知無向圖采用鄰接表存儲方式，試寫出刪除邊(i，j)的算法。void DeletEdge(AdjList g,int i,j) 在用鄰接表方式存儲的無向圖g中，刪除邊(i,j)p=gi.firstarc; pre=null; 刪頂點i 的邊結點(i,j),pre是前驅指針while(p) if(p->adjvex=j) if(pre=null)gi.firstarc=p->next; else pre->next=p->next; free(p);釋放空間 else pre=p; p=p->next; 沿鏈表繼續(xù)查找p=gj.firstarc; pre=null; 刪頂點j 的邊結點(j,i)while(p) if(p->adjvex=i) if(pre=null)gj.firstarc=p->next; else pre->next=p->next; free(p);釋放空間 else pre=p; p=p->next; 沿鏈表繼續(xù)查找 DeletEdge【算法討論】 算法中假定給的i，j 均存在，否則應檢查其合法性。若未給頂點編號，而給出頂點信息，則先用頂點定位函數(shù)求出其在鄰接表頂點向量中的下標i和j。 7.31 假設有向圖以鄰接表存儲，試編寫算法刪除弧<Vi，Vj>的算法。void DeleteArc（AdjList g,vertype vi,vj） 刪除以鄰接表存儲的有向圖g的一條弧<vi,vj>，假定頂點vi和vj存在i=GraphLocateVertex(g,vi); j=GraphLocateVertex(g,vj); 頂點定位 p=gi.firstarc; pre=null;while(p) if(p->adjvex=j) if(pre=null) gi.firstarc=p->next;else pre->next=p->next;free(p);釋放結點空間 else pre=p; p=p->next;結束 7.32  設計一個算法利用遍歷圖的方法判別一個有向圖G中是否存在從頂點Vi到Vj的長度為k的簡單路徑，假設有向圖采用鄰接表存儲結構?！绢}目分析】本題利用深度優(yōu)先遞歸的搜索方法判斷有向圖G的頂點i到j是否存在長度為k的簡單路徑，先找到i的第一個鄰接點m，再從m出發(fā)遞歸的求是否存在m到j的長度為k-1的簡單路徑。int existpathlen(AlGraph G,int i,int j,int k) /判斷鄰接表方式存儲的有向圖G的頂點i到j是否存在長度為k的簡單路徑 if(i=j&&k=0) return 1; /找到了一條路徑,且長度符合要求 else if(k>0) visitedi=1; for(p=G.verticesi.firstarc;p;p=p->next) m=p->adjvex; if(!visitedm) if(existpathlen(G,m,j,k-1) return 1; /剩余路徑長度減一 visitedi=0; /本題允許曾經(jīng)被訪問過的結點出現(xiàn)在另一條路徑中 return 0; /沒找到  7.33  設有向圖G采用鄰接矩陣存儲，編寫算法求出G中頂點i到頂點j的不含回路的、長度為k的路徑數(shù)。int GetPathNum(AdjMatrix GA,int i,int j,int k,int n) /求鄰接矩陣方式存儲的有向圖G的頂點i到j之間長度為k的簡單路徑條數(shù)/n為頂點個數(shù) if(i=j&&k=0) return 1; /找到了一條路徑,且長度符合要求 else if(k>0) sum=0; /sum表示通過本結點的路徑數(shù) visitedi=1; for(k=0;k<n;k+) if(GAik!=0&&!visitedk) sum+=GetPathNum(GA,k,j,k-1,n) /剩余路徑長度減一 visitedi=0; /本題允許曾經(jīng)被訪問過的結點出現(xiàn)在另一條路徑中 return sum;  7.34  設計算法求出以鄰接表存儲的有向圖G中由頂點u到v的所有的簡單路徑。 void AllSPdfs(AdjList g,vertype u,vertype v)求有向圖g中頂點u到頂點v的所有簡單路徑 int top=0,s; s+top=u; visitedu=1; while(top>0 | p) p=gstop.firstarc; 第一個鄰接點 while(p!=null && visitedp->adjvex=1) p=p->next; 下一個訪問鄰接點表 if(p=null) top-; 退棧 else i=p->adjvex; 取鄰接點（編號） if(i=v) 找到從u到v的一條簡單路徑，輸出 for(k=1;k<=top;k+)printf( "%3d",sk); printf( "%3dn",v);if else visitedi=1; s+top=i; else深度優(yōu)先遍歷 else while AllSPdfs 7.35 以鄰接表作存儲結構，編寫拓撲排序的算法。7.36 試寫一算法，判斷以鄰接表方式存儲的有向圖中是否存在由頂點Vi到頂點Vj的路徑（i<>j）。【題目分析】從Vi深度優(yōu)先遍歷,若在未退出深度優(yōu)先遍歷時遍歷到Vj，說明Vi間Vj存在路徑int visitedn; 設有向圖有n個頂點int Pathitoj(AdjList g,int Vi,int Vj) 判斷以鄰接表方式存儲的有向圖中是否存在由頂點Vi到頂點Vj的路徑if(Vi=Vj) return 1; Vi到頂點Vj存在路徑 elsevisitedVi=1; for(p=gVi.firstarc;p;p=p->next) k=p->adjvex; if(!visitedk && Pathitoj(g,k, Vj) return 1; for return 0; Vi到頂點Vj不存在路徑else 結束 【算法討論】若頂點vi和vj 不是編號，必須先用頂點定位函數(shù),查出其在鄰接表頂點向量中的下標。下面再對本題用非遞歸算法求解如下。 int Connectij (AdjList g , vertype Vi , Vj ) 判斷n個頂點以鄰接表表示的有向圖g中，頂點 Vi 各Vj 是否有路徑，有則返回1，否則返回0for(i=1;i<n;i+) visitedi=0;訪問標記數(shù)組初始化 i=GraphLocateVertex(g, Vi); 頂點定位，不考慮 Vi或 Vj不在圖中的情況 j=GraphLocateVertex(g, Vj); int stack,top=0;stack+top=i; while(top>0)k=stacktop-; p=gk.firstarc;while(p && visitedp->adjvex=1) p=p->next;查第k個鏈表中第一個未訪問的弧結點 if(p=null) top-; else i=p->adjvex;if(i=j) return(1); 頂點Vi和Vj 間有路徑else visitedi=1; stack+top=i;else whilereturn(0); 頂點Vi和Vj間無通路  7.37假設有向圖G以十字鏈表形式存儲，試寫一個判斷該有向圖中是否有環(huán)路（回路）的算法。【題目分析】有幾種方法判斷有向圖是否存在環(huán)路，這里使用拓撲排序法。對有向圖的頂點進行拓撲排序，若拓撲排序成功，則無環(huán)路；否則，存在環(huán)路。題目已假定有向圖用十字鏈表存儲，為方便運算，在頂點結點中，再增加一個入度域indegree，存放頂點的入度。入度為零的頂點先輸出。為節(jié)省空間，入度域還起棧的作用。值得注意的是，在鄰接表中，頂點的鄰接點非常清楚，頂點的單鏈表中的鄰接點域都是頂點的鄰接點。由于十字鏈表邊（?。┙Y點個數(shù)與邊（弧）個數(shù)相同（不象無向圖邊結點個數(shù)是邊的二倍），因此，對某頂點v, 要判斷其鄰接點是headvex還是tailvex。int Topsor(OrthList g)判斷十字鏈表為存儲結構的有向圖g是否有環(huán)，如是返回1，否則返回0int top=-1; 用作棧頂指針 for(i=0;i<n;i+)求各頂點的入度。設有向圖g有n個頂點，初始時入度域均為0 p=gi.firstin; 設頂點信息就是頂點編號，否則，要進行頂點定位 while(p) gi.indegree+; 入度域增1if(p->headvex=i) p=p->headlink; else p=p->taillink; 找頂點i的鄰接點while(p) forfor(i=1;i<=n;i+) if(gi.indegree=0)gi.indegree=top;top=i;建入度為0頂點的棧m=0; m為計數(shù)器，記輸出頂點個數(shù)while(top<>-1) i=top; top=gtop.indegree; m+; top指向下一入度為0的頂點 p=gi.firstout; while(p) 處理頂點i的各鄰接點的入度 if(p->tailvex=i) k=p->headvex; else k=p->tailvex; 找頂點i的鄰接點 gk.indegree-; 鄰接點入度減1 if(gk.indegree=0) gk.indegree=top; top=k; 入度為0的頂點再入棧if(p->headvex=i) p=p->headlink; else p=p->taillink;找頂點i的下一鄰接點 while(p) while(top<>0)if(m<n) retun(1)有向圖存在環(huán)路; else return(0); 有向圖無環(huán)路算法結束 7.38已知n個頂點的有向圖，用鄰接矩陣表示，編寫函數(shù)，計算每對頂點之間的最短路徑。本題用FLOYD算法直接求解如下： void ShortPath_FLOYD(AdjMatrix g) 求具有n個頂點的有向圖每對頂點間的最短路徑 AdjMatrix length; 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+lengthkj<lengthij) lengthij=lengthik+lengthkj; 算法結束 7.39設計算法求距離頂點V0的最短路徑長度(以弧數(shù)為單位)為K的所有頂點，要求盡可能地節(jié)省時間?！绢}目分析】 本題應用寬度優(yōu)先遍歷求解。若以v0作生成樹的根為第層，則距頂點v0最短路徑長度為K的頂點均在第K+1層?？捎藐犃写娣彭旤c，將遍歷訪問頂點的操作改為入隊操作。隊列中設頭尾指針f和r，用level表示層數(shù)。void bfs_K(graph g,int v0,K)輸出無向連通圖g中距頂點v0最短路徑長度為K的頂點 int Q; Q為頂點隊列，容量足夠大 int f=0,r=0,t=0; f和r分別為隊頭和隊尾指針，t指向當前層最后頂點 int level=0,flag=0;層數(shù)和訪問成功標記 visitedv0=1; 設v0為根 Q+r=v0; t=r; level=1; v0入隊 while(f<r && level<=K+1) v=Q+f; w=GraphFirstAdj(g,v); while(w!=0) w!=0 表示鄰接點存在 if(visitedw=0) Q+r=w; visitedw=1;鄰接點入隊列 if(level=K+1) printf("距頂點v0最短路徑為k的頂點%d ",w); flag=1; if w=GraphNextAdj(g ,v ,w); while(w!=0) if(f=t) level+；t=r; 當前層處理完，修改層數(shù)，t指向下一層最后一個頂點 while(f<r && level<=K+1) if(flag=0) printf( "圖中無距v0頂點最短路徑為%d的頂點。n",K);算法結束 算法討論本題亦可采取另一個算法。由于在生成樹中結點的層數(shù)等于其雙親層次數(shù)加1，故可設頂點和層次數(shù)個隊列，其入隊和出隊操作同步，其核心語句段如下：QueueInit(Q1) ; QueueInit(Q2); Q1和Q2是頂點和頂點所在層次數(shù)的隊列 visitedv0=1; 訪問數(shù)組初始化，置v0被訪問標記 level=1; flag=0; 是否有層次為K的頂點的標志 QueueIn(Q1,v0); QueueIn(Q2,level); 頂點和層數(shù)入隊列 while(!empty(Q1) && level<=K+1) v=QueueOut(Q1); level=QueueOut(Q2);頂點和層數(shù)出隊 w=GraphFirstAdj(g,v0); while(w!=0) 鄰接點存在 if(visitedw=0) if(level=K+1) printf("距離頂點v0最短路徑長度為K的頂點是%dn",w); visitedw=1; flag=1; QueueIn(Q1 ,w); QueueIn(Q2,level+1); w=GraphNextAdj(g ,v ,w); while(w!=0) while(!empty(Q1) && level<K+1) if(flag=0) printf( "圖中無距v0頂點最短路徑為%d的頂點。n",K); 7.40 設有n(n>0)個頂點的無向連通圖G， 可以鄰接矩陣Anxn存儲，由于鄰接矩陣的對稱性，只將其下三角順序存儲在數(shù)組S中。請編寫對以數(shù)組S存儲的圖G進行寬度優(yōu)先遍歷的算法?！绢}目分析】 由寬度優(yōu)先遍歷的定義，首先訪問任一頂點，然后訪問該頂點的未曾訪問的鄰接點，如此下去，直至全部頂點訪問完成。在鄰接矩陣中，第i行非零元素都是第i個頂點的鄰接點，而在壓縮存儲下，找某頂點的鄰接點要遍歷整個數(shù)組。矩陣元素的下標i和j和其在一維數(shù)組S中的序號k的關系：由 得 和j=k-i(i+1)/2在一維數(shù)組中，只有非零元素才是頂點。為簡單計，當訪問完一個頂點后，就將其在一維數(shù)組中的位序置零；由于是圖的遍歷，當全部頂點訪問完后就直接結束算法。#define n 用戶圖的頂點數(shù)#define m n(n+1)/2int nodes=0, visitedn=0; 頂點計數(shù)和訪問標志數(shù)組void index(int k,*i,*k) 由非零元素在一維數(shù)組S中的序號k計算其在鄰接矩陣中的下標i和j *i= é(-3+sqrt(9+8*k)/2ù *j=k-(*i)*(*i+1)/2 void Tri_bfs(int v) 對下三角存儲的無向連通圖作寬度優(yōu)先遍歷，v是遍歷的開始頂點nodes+; QueueInit(Q); QueueIn(Q,v); printf(v); visitedv=1; 初始化 while(!QueueEmpty(Q) && nodes<=n) v=QueueOut(Q); for(k=0; k<m; k+) if(sk!=0) index(k,&i,&j); 求非零元素在鄰接矩陣中的下標 if(i=v | j=v) 頂點i或j是頂點v if(i=v) 頂點i是頂點v if(visitedj=0) 頂點j是頂點v的鄰接點，且尚未訪問 nodes+; printf(j); visitedj=1; sk=0; QueueIn(Q,j); else 頂點j是頂點v if(visitedi=0) 頂點i是頂點v的鄰接點，且尚未訪問 nodes+; printf(i); visitedi=1; sk=0; QueueIn(Q,i); 算法結束算法討論對于連通圖，進入BFS一次就可訪問完圖的全部頂點；對于非連通圖，進入BFS一次就可訪問完圖的一個連通分量。若要遍歷全部頂點，在調用BFS的函數(shù)中加入語句：for(vi=0; vi<n;vi+) if(visitedvi=0) Tri_bfs(vi);