數(shù)據(jù)結(jié)構(gòu)圖習(xí)題介紹

1、第S章圖第8章圖8T畫出1個頂點、2個頂點、3個頂點、4個頂點和5個頂點的無向完全圖。試證明在n個頂點的無向完全圖中，邊的條數(shù)為n(n-l)/2?！窘獯稹?15【證明】4個頂點的無向完全圖5個頂點的 無向完全圖O1個頂點的無向完全圖002個頂點的無向完全圖A3個頂點的無向完全圖在有n個頂點的無向完全圖中，每一個頂點都有一條邊與其它某一頂點相連，所以每一個頂點有nT條邊與其他rl個頂點相連，總計n個頂點有n(rl)條邊。但在無向圖中，頂點1到頂點j與頂點j到頂點i是同一條邊，所以總共有n(r1)/2條邊。8-2右邊的有向圖是強(qiáng)連通的嗎？請列出所有的簡單路徑?！窘獯稹颗袛嘁粋€有向圖是否強(qiáng)連通，要看

2、從任一頂點出發(fā)是否能夠回到該頂點。右面的有向圖做不到這一點，它不是強(qiáng)連通的有向圖。各個頂點自成強(qiáng)連通分量。所謂簡單路徑是指該路徑上沒有重復(fù)的頂點。從頂點A出發(fā)，到其他的各個頂點的簡單路徑有A-B,AfDfB,A-B-C,A-D-B->C,AfD,AfBfE,AfDfE,ABCfpfE,AfDfBfCfFfE,A->B->C->F,AfDfBCfF。從頂點B出發(fā),從頂點C出發(fā),從頂點D出發(fā),DfBfCfFfE。從頂點E出發(fā),從頂點F出發(fā),到其他各個頂點的簡單路徑有B->C,B->CfF,BfE,BfC-FfE。到其他各個頂點的簡單路徑有C-F,C-F-Eo到其

3、他各個頂點的簡單路徑有DfB,D-B-C,D-BfCfF,D-E,D-B-E,到其他各個頂點的簡單路徑無。到其他各個頂點的簡單路徑有F-E。8-3給出右圖的鄰接矩陣、鄰接表和鄰接多重表表示?！窘獯稹?1)鄰接矩陣Edge=0100-10100001001000000010（2）鄰接表（出邊表）（入邊表）（3）鄰接多重表8-4用鄰接矩陣表示圖時，若圖中有1000個頂點，1000條邊，則形成的鄰接矩陣有多少矩陣元素？有多少非零元素？是否稀疏矩陣？【解答】一個圖中有1000個頂點，其鄰接矩陣中的矩陣元素有1000=1000000個。它有1000個非零元素（對于有向圖）或2000個非零元素（對于無向圖

4、），因此是稀疏矩陣。8-5用鄰接矩陣表示圖時，矩陣元素的個數(shù)與頂點個數(shù)是否相關(guān)？與邊的條數(shù)是否相關(guān)？【解答】用鄰接矩陣表示圖，矩陣元素的個數(shù)是頂點個數(shù)的平方，與邊的條數(shù)無關(guān)。矩陣中非零元素的個數(shù)與邊的條數(shù)有關(guān)。8-6有n個頂點的無向連通圖至少有多少條邊？有n個頂點的有向強(qiáng)連通圖至少有多少條邊？試舉例說明?！窘獯稹縩個頂點的無向連通圖至少有n-l條邊，n個頂點的有向強(qiáng)連通圖至少有n條邊。例如:特例情況是當(dāng)n=l時，此時至少有0條邊。8-7對于有n個頂點的無向圖，采用鄰接矩陣表示，如何判斷以下問題：圖中有多少條邊？任意兩個頂點i和J之間是否有邊相連？任意一個頂點的度是多少？【解答】用鄰接矩陣表示無

5、向圖時，因為是對稱矩陣，對矩陣的上三角部分或下三角部分檢測一遍，統(tǒng)計其中的非零元素個數(shù)，就是圖中的邊數(shù)。如果鄰接矩陣中不為零，說明頂點1與頂點J之間有邊相連。此外統(tǒng)計矩陣第1行或第1列的非零元素個數(shù)，就可得到頂點1的度數(shù)。8-8對于如右圖所示的有向圖，試寫出：(1)從頂點出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2)從頂點出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹；【解答】(1)以頂點為根的深度優(yōu)先生成樹(不唯一)：(2)以頂點為根的廣度優(yōu)先生成樹:8-9試擴(kuò)充深度優(yōu)先搜索算法，在遍歷圖的過程中建立生成森林的左子女-右兄弟鏈表。算法的首部為voidGraph:DFS(constintv,i

6、ntvisited,TreeNode<int>*t)其中，指針t指向生成森林上具有圖頂點V信息的根結(jié)點。(提示：在繼續(xù)按深度方向從根V的某一未訪問過的鄰接頂點W向下遍歷之前，建立子女結(jié)點。但需要判斷是作為根的第一個子女還是作為其子女的右兄弟鏈入生成樹。)【解答】為建立生成森林，需要先給出建立生成樹的算法，然后再在遍歷圖的過程中，通過一次次地調(diào)用這個算法，以建立生成森林。teinplate<Type>voidGraph<Irpe>:DFS.Tree(constintv,intvisited,TreeNode<lpe>*t)從圖的頂點V出發(fā)，深度優(yōu)先

7、遍歷圖，建立以t(已在上層算法中建立)為根的生成樹。Visitedv-1;intfirst-1;TreeNode<lpe>*p,*q;intw-GetFirstNeighbor(v);取第一個鄰接頂點while(w!-1)若鄰接頂點存在if(vositedfw-0)p-newTreeNode<Type>(GetValue(w);if(first-1)t->setFirstChild(p);first-0;elseq->setNextSiblmg(p);q-p；DFS.Tiee(w.visited,q);w-GetNextNeighbor(v,w);且該鄰接結(jié)

8、點未訪問過建立新的生成樹結(jié)點若根*t還未鏈入任一子女新結(jié)點*P成為根*t的第一個子女否則新結(jié)點*p成為*q的下一個兄弟指針q總指示兄弟鏈最后一個結(jié)點從*q向下建立子樹取頂點V排在鄰接頂點W的下一個鄰接頂點頂點個數(shù)建立訪問標(biāo)記數(shù)組逐個頂點檢測若尚未訪問過建立新結(jié)點*P原來是空的生成森林，新結(jié)點成為根否則新結(jié)點*p成為*q的下一個兄弟建立以*p為根的生成樹卜.一個算法用于建立以左子女-右兄弟鏈表為存儲表示的生成森林。template<lpe>voidGiaph<l>rpe>:DFS_Forest(Tree<Type>&T)從圖的頂點v出發(fā)，深度優(yōu)先

9、遍歷圖，建立以左子女-右兄弟鏈表表示的生成森林T。Troot-NULL;intn-NumberOfVreitices();TreeNode<Type>*p,*q;int*visited-newintn;for(intv-0;v<n;v+)visitedv-0;for(v-0;v<n;v+h-)if(visitedv0)p-newTieeNode<Type>(GetValue(v);if(Troot-NULL)T.ioot-p;elseq->setNextSiblmg(p);q-p；DFS_Tiee(v,visited,p);8-10用鄰接表表示圖時，頂

10、點個數(shù)設(shè)為n,邊的條數(shù)設(shè)為e,在鄰接表上執(zhí)行有關(guān)圖的遍歷操作時，時間代價是O(n*e)?還是O(n+e)?或者是O(max(n,e)?【解答】在鄰接表上執(zhí)行圖的遍歷操作時，需要對鄰接表中所有的邊鏈表中的結(jié)點訪問一次，還需要對所有的頂點訪問一次，所以時間代價是O(n+e)。8-11右圖是一個連通圖，請畫出(1)以頂點為根的深度優(yōu)先生成樹；(2)如果有關(guān)節(jié)點，請找出所有的關(guān)節(jié)點。(3)如果想把該連通圖變成重連通圖，至少在圖中加幾條邊?如何加？【解答】(1)以頂點為根的深度優(yōu)先生成樹:(2)關(guān)節(jié)點為，(3)至少加四條邊(1,10),(3,4),(4,5),(5,6)o從的子孫結(jié)點到的祖先結(jié)點引一條邊

11、，從的子孫結(jié)點到根的另一分支引一條邊，并將的子孫結(jié)點、與結(jié)點連結(jié)起來，可使其變?yōu)橹剡B通圖。8-12試證明在一個有n個頂點的完全圖中，生成樹的數(shù)目至少有2口工1?！咀C明】略8-13編寫一個完整的程序，首先定義堆和并查集的結(jié)構(gòu)類型和相關(guān)操作，再定義Krnskal求連通網(wǎng)絡(luò)的最小生成樹算法的實現(xiàn)。并以右圖為例，寫出求解過程中堆、并查集和最小生成樹的變化?！窘獯稹壳蠼膺^程的第一步是對所有的邊，按其權(quán)值大小建堆：加(2,4)加(3,4)力口(3,6)力口(3,5)力口(5,6)求解過程中并查集與堆的變化:選(1,2,7)選(3,6,8),在同一連通分量上，不加選(2,4,9),結(jié)束最后得到的生成樹如卜0

12、123456并查集的存儲表示完整的程序如下：include<iostieam.h>templateclassTypeclassMinHeappublic:enumMaxHeapSize-50；MinHeap(intMaxsize-MaxHeapSize)；MinHeap(TypeAiray,intn);voidInsert(constType&ele);voidRemoveMin(Type&NIin);voidOutput0；private:voidFilterDown(intstart,intend);voidFilterUp(intend);Tpe*pHeap;

13、intHMaxSize；intCurrentSize；classUFSetspublic:enumMaxUmonSize-50;UFSets(intMaxSize-MaxUmonSize);UFSets0deletem_pParent;voidUnion(intRootl,intRoot2);intFind(intx);private:intm_iSize;int*m_pPaient;classGraphpublic:enumMaxVerticesNum-50；Graph(intWrtices-0)CunentWrtices-Wrtices；ImtGiaph(j；voidInitGraph()

14、;voidKruskal0；intGetWrticesNum()returnCuirentWrtices;private:intEdgeMaxVeiticesNumMaxVeiticesNum;intCunentVeitices;);classGrapliEdgepublic:inthead,tail；intcost；intoperator<-(GraphEdge&ed)；);GraphEdge:operator<一(GiaphEdge&ed)returnthis->cost<-ed.cost；)UFSets:UFSets(intMaxSize)m_iS

15、ize-MaxSize;mjpParent-newintm_iSize;for(inti-0;i<m_iSize;iH)m_jpPaienti-1;)voidUFSets：Umon(intRootl,intRoot2)m_pPaientRoot2-Rootl；intUFSets:Fmd(intx)while(m_pPaientx>-0)x-m_pParentx;returnx;)template<classTXpe>MniHeap<Type>:MinHeap(intMaxsize)HMaxSize-Maxsize;pHeap-newTypeHMaxSize;

16、CunentSize1;)templateclassTpe>MniHeap<Type>:MinHeap(lypeAiiay,intn)HMaxSize-(n<MaxHeapSize)?MaxHeapSize：n；pHeap-newTypeHMaxSize；for(inti-O;i<n;iH)pHeapfi-Arrayi；CunentSize-n-1；intiPos-(CunentSize-1)/2；while(iPos>-0)FilterDown(iPos,CunentSize);iPos一；)templateclassTpe>voidMniHeap&

17、lt;Type>:FilterDown(intstart,intend)inti-start,j-2*stait+1；TpeTemp-pHeapi；while(j<-end)if(j<end&&pHeap。+1<-pHeapj)j+;if(Temp<-pHeapj)break;pHeapi-pHeap|j；*j+l；pHeapi-Temp;templateclassTpe>voidMniHeap<Type>:FilterUp(intend)inti-end,j-(end-1)/2;TjpeTemp-pHeapi；while(i&g

18、t;0)if(pHeapj<一Temp)break;pHeapi-pHeap|j;1)/2;)pHeapi-Temp;templateclassTpe>voidMHiHeap<Tpe>:Insert(constTjpe&ele)CurrentSize-H-;if(CurrentSize-HMaxSize)return;pHeapCurrentSize-ele;FilterUp(CunentSize);templateclassTpe>voidMuiHeap<Type>:RemoveMm(Tjpe&Mm)if(CurrentSize<

19、;0)return;Min-pHeapO；pHeap0-pHeapCurrentSize-;FilterDown(0.CunentSize);templateclassTpe>voidMHiHeap<Tpe>:Output()for(inti-0;i<-CurrentSize;i+)cout«pHeapi«H*;cout«endl;voidGraph:IiutGiaph()Edge00-l;Edge0l-28;Edge02-1;Edge03-1;Edge04-1;Edge05-10;Edge06-1;Edgell-1;Edgel2-16;E

20、dgel3-1;Edgel4-1;Edgel5-1;Edgel6-14;Edge22-1;Edge23-12;Edge24-1;Edge5-l;Edge26-1;Edge33-1;Edge34-22;Edge35-1;Edge36-18;Edge44-1;Edge45-25;Edge46-24;Edge55-1；Edge56-1；Edge66-1；for(inti-1;i<6;i+)fdr(intj-O;j<i;j+)EdgeiJj-Edgeji；voidGraph:Kiuskal()GraphEdgee;intVerticesNum-GetVerticesNum()；intij,

21、count；MmHeap<GiapliEdge>heap(WiticesNum*VerticesNum)；UFSetsset(VerticesNum)；for(i-0；i<VerticesNum；i-H-)for(j-i+1;j<VerticesNum；j-H-)if(EdgeiU>0)e.head-i;e.tad-j;e.cost-Edgeij；heap.Insert(e);count-1;while(count<VerticesNum)lieap.RemoveMui(e);i-set.Fmd(e.head);j-set.Fmd(e.tail);set.U

22、nion(i,j)；count十十;cout«1*(M«e.head«M«e.tail«M«e.cost«")M«endl;8-14利用Dijkstra算法的思想，設(shè)計一個求最小生成樹的算法?！窘獯稹坑嬎氵B通網(wǎng)絡(luò)的最小生成樹的Dijkstra算法可描述如下：將連通網(wǎng)絡(luò)中所有的邊以方便的次序逐步加入到初始為空的生成樹的邊集合T中。每次選擇并加入一條邊時，需要判斷它是否會與先前加入T的邊構(gòu)成回路。如果構(gòu)成了回路，則從這個回路中將權(quán)值最大的邊退選。并以并查集作為判斷是否出現(xiàn)回路的工具，分析算法的下面以鄰接矩陣作

23、為連通網(wǎng)絡(luò)的存儲表示,執(zhí)行過程。(0160O00142i0590O19060O00018110260Edge =16191411(2一最終得到的最小生成樹為實現(xiàn)算法的過程為constintMaxNum-10000;voidGraph:Dijkstra()GraphEdgee；intVeiticesNum-GetVerticesNum()；并查集并查集初始化檢查所有的邊邊存在判結(jié)點i與j是否在同一連通分量上intk；mtdisJomtVeiticesNum;for(i-0;i<WrticesNum;i+)disjoin®-1;for(i-0；i<VerticesNum-1；

24、iH)for(j-1+1;j<VerticesNum;jH)if(Edgeij<MaxNuni)p-i;q-j;while(disJointp>-0)p-disJointp;i與j不在同一連通分量上，連通之 i與j在同一連通分量上尋找離結(jié)點i與j最近的祖先結(jié)點每變動一個P、就對q到根的路徑檢測一遍while(disJomtfq>-0)p-disJointfq;if(p!-q)disJointfj-i；elsep-i；while(disJomtp>-0)q-j;while(disJomtq>-0&&disJomtqdisJomtp)q-disJ

25、ointq；if(disJomtfq-disJointp)break;elsep-disJointp；k-disJointp；結(jié)點k是i和j的最近的共同祖先p-i;q-disJointfp；max-MaxNum；從i到k找權(quán)值最大的邊(si.s2)while(q<-k)if(Edgeqp>max)max-Edgeqp;si-p;s2-q;p-q;q-disJomtp;p-j;q-disJointp;max-MaxNum;/從j到k找權(quán)值最大的邊(tLt2)while(q<-k)if(Edgeqp>max)max-Edgeqp;tl-p；t2-q；p-q；q-disJom

26、tp;niax-Edgeij;kl-i；k2-j；if(max<Edgesls2)max-Edgesls2；kl-si；k2-s2；if(max<Edgetlt2)max-Edgetlt2;kl-tl;k2-12;if(max!-Edgeij)當(dāng)Edgeijmax時邊不改if(disJointfkl-k2)disJomtkl-1；elsedisJomtk2-1；刪除權(quán)值最大的邊disJointj-i;加入新的邊EdgeOi-Edgebi;8-15以右圖為例，按Dijkstia算法計算得到的從頂點(A)到其它各個頂點的最短路徑和最短路徑長度?！窘獯稹吭袋c終點最短路徑最短路徑長度AB(

27、A、B)(A、B)(A,B)(A、B)|io|回同0C(AC)(AC)(AC)(AC)IS18ISISD(ABD)(ABD)(ABD)8151515E(ABD.E)(ABD,E)80017178T6在以下假設(shè)下，重寫Dijkstra算法：(1)用鄰接表表示帶權(quán)有向圖G,其中每個邊結(jié)點有3個域：鄰接頂點vertex,邊上的權(quán)值lengtli和邊鏈表的鏈接指針link。(2)用集合T=V(G)-S代替S(已找到最短路徑的頂點集合)，利用鏈表來表示集合T。試比較新算法與原來的算法，計算時間是快了還是慢了，給出定量的比較?！窘獯稹坑绵徑颖肀硎镜膸?quán)有向圖的類定義:constintDefaultSize

28、-10；classGraph；structEdgefriendclassGraph;intvertex;floatlength;Edge*link;Edge()缺省頂點個數(shù)圖的前視類定義邊的定義/邊的另一頂點位置/邊上的權(quán)值下一條邊鏈指針構(gòu)造函數(shù)Edge(intnuni,floatwh):vertex(num),length(wh),link(NULL)intoperator<(constEdge&E)constreturnlength!-E.length;構(gòu)造函數(shù)判邊上權(quán)值小否structVertexfriendclassGraph;chardata；Edge*adj；頂點的定

29、義頂點的名字邊鏈表的頭指針圖的類定義classGraphprivate:Vertex*NodeTable；頂點表(各邊鏈表的頭結(jié)點)intNumVertices；當(dāng)前頂點個數(shù)intNumEdges；當(dāng)前邊數(shù)intGetVertexPos(constTypevertex);給出頂點vertex在圖中的位置public:Graph(intsz);構(gòu)造函數(shù)Giaph();析構(gòu)函數(shù)intNumberOfreitices()returnNumVertices;返回圖的頂點數(shù)intNumberOfEdges()returnNuniEdges;"返回圖的邊數(shù)charGetValue(inti)取位

30、置為i的頂點中的值returni>-0&&i<NumVertices?NodeTablei.data：4>；float Get Weight (int vl, int v2 )；int GetFirstNeiglibor (int v )；int GetNextNeighboi ( int v, int w )；返回邊(vl, v2)上的權(quán)值取頂點V的第一個鄰接頂點取頂點V的鄰接頂點W的下一個鄰接頂點(2)用集合T=V(G)-S代替S(已找到最短路徑的頂點集合)，利用鏈表來表示集合T。8-17試證明：對于一個無向圖G=(V,E),若G中各頂點的度均大于或等于2

31、,則G中必有回路。【解答】反證法：對于一個無向圖G=(V,E),若G中各頂點的度均大于或等于2,則G中沒有回路。此時從某一個頂點出發(fā)，應(yīng)能按拓?fù)溆行虻捻樞虮闅v圖中所有頂點。但當(dāng)遍歷到該頂點的另一鄰接頂點時,又可能回到該頂點，沒有回路的假設(shè)不成立。8-18設(shè)有一個有向圖存儲在鄰接表中。試設(shè)計一個算法，按深度優(yōu)先搜索策略對其進(jìn)行拓?fù)渑判?。并以右圖為例檢驗?zāi)愕乃惴ǖ恼_性?！窘獯稹?1)利用題8-16定義的鄰接表結(jié)構(gòu)。增加兩個輔助數(shù)組和一個工作變量：記錄各頂點入度 hit indegieefNumVeitices。記錄各頂點訪問順序int visitedNumVertices,初始時讓 visite

32、di = 0, i = 1, 2,NumVerticeso訪問計數(shù)intcount,初始時為0。(2)拓?fù)渑判蛩惴╲oidGraph:dfs(intvisited,&count)count十十；visitedv-count;cout«NodeTablev.data«endl;Edge*p-NodeTablev.adj;while(p!-NULL)intw-p->vertex;mdegieew一;if(visitedfw-0&&indegieew-0)dfs(visited,mdegree.w,count);p-p->link;)主程序inti,j;Edge*p;floatw;cin»NumWrtices;int*visited-newintNumVertices-t-1;int*mdegiee=newintNumWitices+1;for(i-l;i<-NuniVeitices;i+)NodeTablei.adj-NULL;cin»NodeTablei.data;cout«endl;visitedi-0;mdegreefi一