7.17.1★圖的結構定義Graph=(V,R)VR＝{<v,w>|v,w∈VP(v,w<v,w>表示從頂點v到頂點w的一條弧P(v,w)定義了弧<v,w>的意義或信息,表示v和w之間有特定的關聯屬性P。}3★★圖的抽象數據類型的定義ADTGraphR={VRVR＝{<vw>|v,w∈VP(v,w),<v,w>表示從頂點vw一條弧P(v,w)v,w表示v和w之間有特定的結構的建立LocateVex(G,對頂點操,則4對鄰接點和刪除5InsertAcr(&G,InsertAcr(&G,v,和刪除 }ADT6★圖的基本術語★圖的基本術語若<v，w>VR，則<v，w>表示從頂點v到頂點w的一條弧(arc),并稱v為弧尾(tail)或起始點,稱w為弧頭(head)或終端點。由于此時圖中的“弧”是有方向的因此由ABECDG1=(V1,V1={A,B,C,D,E}<B,C>,<C,D>,<D,A>,<E,C>7無無向若<v,w>∈VR,且有<w,v>∈VR,即VR是對稱關系,則以無序對(v,w)代替這兩個有序對v和w之間的一條邊(edge頂點集合和邊集合構成的圖稱作無向BCADFEV2={A,B,C,D,E,VR2={(A,B),(A,(B,E),(C,D),(D,(B,F),(C,F)8設n表示圖中頂點數目，用e表示圖的邊或弧的數目，且對于無向圖，其邊數e的取值范圍是0~n(n-1)/2。稱有n(n-1)/2條邊(即圖中每個頂點和其余n-1個頂點都有邊對于有向圖，其弧數e的取值范圍是0~n(n-1)。稱n(n-1)條弧(即圖中每個頂點和其余n-1個頂點都有弧相連的有向圖為有向完全圖對于有很少條邊或弧(如e<nlogn)的圖稱為稀疏圖之稱為稠密圖 14234 9權權與125A9663B7E6354C2F’’子子假設有兩個圖G=(V{E})和圖G’=(V’E’}),如果V且EE則稱圖G’為G的子圖12111123433434有向圖G1及其子圖1211 22333 545無向圖G2及其子圖鄰鄰接對于無向圖G=(V,{E}),如果邊(v,v’)∈E,則稱頂點v和互為鄰接點,即vv’相鄰接。邊(v,v’)依附于頂點v和v’,或者說邊(v,v’)與頂點v和v’相關聯。對于有向圖G=(V,{A}),如果弧v,v>∈A,則稱頂點鄰接到頂點v’,頂點v’鄰接自頂點v,或者說弧<v,v’>與頂 對于無向圖，頂點v的度是指與頂點v相關聯的邊的記作TD(v)BCADTD(B)=TD(A)=FE對于有向圖，頂點v的度有出度和入度兩部分，其中以以頂點v為弧尾的弧的數目稱為該頂點的出度，記作OD(v),頂點v的度為TD(v)=ID(v)+OD(v)。AID(B)= CFOD(B)=TD(B)=一般地，若圖G中有n個頂點，e條邊或弧，則圖中的度與邊的關系e TD(vi1n2無向圖G=(VE})中從頂點v到v’的路徑是一個頂點序列(v=vi0,vi1,vi2,…,vim=v’),其中(vij-1,vij)∈E,1≤j≤m。如果圖G是有向圖,則路徑也是有向的,頂點序列路徑的長度是指路徑上經過的弧或邊的數目。在一個路連連通圖、連通分量、強連通圖、強連通在無向圖G=(VE})中，若從頂點vi到頂點vj有路徑相通vj∈V，vi和vj都是連通的，則稱該無向圖G為連通圖。1G2345①任何連通圖的連通分量只有一個ABABCC GHFF DEIKIKJJLMLM(a)無向圖(b)無向圖G3的3個43432121有向圖G=(V,{A})中,若對于每一對頂點vi,vj∈V且vi≠vj，注意①強連通圖只有一個強連通分量 即是其自身②非強連通的有向圖有多個強連通分量通圖的生成樹是一個極小連通子圖,它含有圖中全部n個頂點,但是只有足以構成一棵樹的n-1條邊,如下 一棵有n個頂點的生成樹有且僅有n-1 入度均為1,則是一棵有向樹。 圖的結 鏈表表基本思想 數據元用一個一維數 頂點的信息 數據關—二維數組(鄰接矩陣 頂點之間的關系鄰接矩陣:表示頂點之間相互關系(邊或弧的信息)的矩陣。以二維數組表示有n個頂點的圖時，需要存放n個頂點信息和n2個弧或邊的信息。對于無向圖,它的鄰接矩陣是對稱矩陣,可只其鄰接 #defineMAX_NAME5//頂點名稱字符串的最大長度+1typedefint typedefchartypedefcharVertexType[MAX_NAME];//對應的一維字符數組用 頂點名#defineINFINITYINT_MAX #defineMAX_VERTEX_NUM20 G1.arcs[i][j].adji,typedefstructArcCell VRType //對無權圖,用1或0表示相鄰否;對帶權圖,則為權值類型InfoType }ArcCell, //弧(二維數組元素)的類型ArcCell定義,二維數組類型AdjMatrix定義typedefstruct{ 可使用scanf(“%s”,G.vexs[i]);輸入各個頂點名字(字符串)VertexTypevexs[MAX_VERTEX_NUM];//頂點向量(頂點信息,一維數組) GraphKind }課堂練習:畫出Mgraph型變量的內存分配示意#define TC umandminimumvaluesforints.#defineGCC是使用ANSIC標準頭文件limits.h中的預定義值。該文件包要判斷某種特定類型可以容納的最大值或最小值，一種簡便的方鄰接矩陣的元素:A[i][j]=0<i,j>或(i,j01<ij>或(ijG1.arcsV1V2V3V2G2.arcsV3V410001010110000101100V4V101010100011V500無向圖的鄰接矩陣一定是對稱有向圖有向圖:頂點Vi的出度是鄰接矩陣A中第i行元 和; 無向圖:頂點Vi的度TD(Vi)是鄰接矩陣A中第i行(或第i列) 網(帶權的圖)的鄰接矩陣的元素A[i][j]={Wi,∞(i,j)或<i,5347189V1V2 16V35V495V6V56有向網及其★★算法講解補u是頂點 字)-是字符intLocateVex(MGraphG,VertexType//操作結果:若G中存在頂點u返回該頂點在圖中的位置;返回-intfor(i=0;i<G.vexnum;++i)if(strcmp(u,G.vexs[i])==0)returni;return-1;}//調用形式LocateVex(Gv):找到v在圖的一維數組vexs中的序號iStatusStatusCreateGraph(MGraph&G //采用數組（鄰接矩陣）表示法，構造圖 {caseDG: returnCreateDG(G); case return //構造有向網caseUDN:return caseUDG:return //構造無向圖} return}基本思想 StatusCreateUNDMGraph&G構造無向網 for(i=0i<G.vexnum; for(i=0;i<G.vexnum;for(j=0;j<G.vexnum;++j)G.arcs[i][j]={INFINITY,NULL};//{adj,{scanf(&v1,&v2,i=LocateVex(G,v1j=LocateVex(G,v2確定v1和v2在G)][);//}return 算法算法采用采用數組(鄰接矩陣表示圖的便于找頂點的鄰接點等缺點n個頂點需要n2個單 邊(弧 空間效率為O(n2)對稀疏圖而言尤其空間V1 V1 V2無向圖的表7.2.2的基本思想：是圖的一種鏈向圖的頂點列好,使之構成一個一維數組(順序表)，之后對圖中每個頂點建立結構,它克服了鄰接矩陣的弊病。先把個單鏈表，第i個單鏈表中的結點表示依附于頂點Vi(單鏈表的頭結點)的邊。每單鏈表的頭結點又構成一個表頭結點表BC01D341034455AFE無向圖的鄰接表01123在無向圖的鄰接表中，頂點vi的度恰好就是第i個單鏈表上結點的個數ABCDEF03114202431320421V1V1 V2021123有向圖的鄰接表03建立一個單鏈表，第i個單鏈表中的結點表示以頂點Vi為弧尾的弧。每個單鏈表以頂點A為弧尾的0AABECD有向圖1234E21032DCB41在有向圖的鄰接表中不易找到指向該頂點的弧解決的方法是逆鄰接表法也就是，在逆鄰接表中，對每個頂 的是指向該頂點的弧以為弧頭的 A 012334 32有向圖的逆鄰接4003102032有向圖G1的逆鄰接表鏈表鏈表中的結點結構(相關弧的結點結構 typedef{該弧的弧頭的頂點的ode*nextarc//指向下一條弧的 //該弧相關信息的 typedefchar頂點的結點結構

01234typedefchartypedefstruct{VertexTypedata; ode* //指向第一條依附該頂點的弧}VNode, 基于基于typedef{AdjListvertices; }結構的圖的類型定義um;//圖的當前頂點數和01234DE在在有向圖鏈表每一條弧用一個結點表示每一個頂點也用一個結點表示7.2.3是有向圖的另一種鏈 結構的和得。 同弧尾的弧結 指向下一個同弧頭的弧結 指向下一個鄰接表以頂點1為弧尾0 ∧1∧ 3 0 1 2圖7.11有向圖鏈02鏈表鏈表中的弧的結點結typedeftypedefstruct//弧的結構{inttailvex,headvex;//該弧的弧尾和弧頭的頂點位置structArcBox*hlink,*tlink;//含義見上面框內InfoType*info; }ArcBox //弧結點的類型定鏈表鏈表中的頂點的結點typedefstruct{VertexType//頂點的結構ArcBox in, //分別指向該頂點第一條入弧和出 //頂點結點的指向該頂點的出指向該頂點的入typedeftypedefstruct um;//有向圖的當前頂點數和}StatusStatusCreateDG(OLGraph&G{//采 鏈 表示，構造有向圖G(G.kind=DG) 算法 scanf( um,&IncInfo//IncInfo為0則各弧不含for(i=0;i<G.vexnum;{//構造} in=NULL; out=NULL;//初始化for(k=0;k<G.vexnum;++k)//輸入各弧{scanf(&v1,//輸入一條邊依附的頂點及鏈 p=(ArcBox*)malloc(sizeof(ArcBox) *p={i,j, in out,NULL}//對弧結點//{tailvex,headvex,hlink,tlink, out=p;//完成在入弧和出弧,;,}}7.2.47.2.4的是無向圖的另一種鏈結構在無向圖的鄰接多重表每一條邊用一個結點表示每一個頂點也用一個結點表示鄰鄰接多重表中的邊的結點其中:mark為標志域,可用以標記該條邊是否被搜索過;ilink用于指向下一條依附于頂點ivex的邊；typedefstruct{ ivex,structEBox*ilink,//該邊依附的兩個頂點的位 鄰鄰接多重表中的頂點的結點結構其中 data與該頂點相關的信edge用于指向第一條依附于該頂點的邊typedefstruct{VertexType //用 頂點的名EBox//用于指向第一條依附該頂點typedeftypedef{VexBox 01234圖7.12無向圖的鄰接多重V32^3^01210jlink4141^2^4^01234^4^2^143212^3^0107.37.3并且使圖中的每個頂點僅被一次的過程。圖中還可能有回路存在，因此在了某個頂點后，可能沿著某條為了保證圖中的各頂點在遍歷過程中且僅一次，必須標記每個已過的頂點，為此，需要為每個頂點設立一個標志。為圖設置一 標志數組visitedn，用于標示圖中每個頂點是否被過，它的初始值為0(“假”,”false”)，表示頂點均未被；一旦某個頂點vi被過，則置標志數組中的visited[i]為1(“真”,“true”)，表示該頂點已。 通常有兩條遍歷圖的路徑：深度優先搜索和搜索。它們對無向圖和有向圖都適用7.3.17.3.1圖的深度優先搜索深度優先搜索遍歷圖的過程是指按照深度方向搜索它類似于樹的先根遍歷，是樹的先根遍歷的推廣采用遞歸的形式說明深度優先搜索遍歷圖的基本思想(1)從圖的某一個頂點V0出發(2)然后依次從v0的的鄰接點出發深度此頂點v0被若此時圖中還有頂點未，則另選圖中一個未直至圖中所有頂點的頂點作為起始點，重復上述深度優先搜索過程到為止例例起深度優先搜索v1→v2→v4→v8→v5→v3→v6→v7例例A GB EHC FI其中：實箭頭代圖的深度優先搜索虛箭頭代表回溯方向方向箭頭旁邊的數字代表搜索順A為起始頂點例例ABCFDGIEHKJLM一般圖的深度優先搜 算法 typedefint,Boolean voidDFSTraverse(GraphG,Status(*Visit)(intv)次。一旦Visit()失敗,則操作失敗int 使for(v=0;v<G.vexnum;++v) 標志數組初始化(開始都未被 for(v=0;v<G.vexnum;if(!visited[v])DFS(G, //對尚 的頂點調用 算法連通圖的深度優先搜索遍voidDFS(GraphG,int 算法 {//從第v個頂點出發遞歸地深度優先遍歷圖Gint //設 VisitFuncG.vexs[v } AdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)）if(!visited[w])DFS(G,w);//對v的尚未 初始條件：圖G存在,v是G中某個頂點,w是v7.3.27.3.2廣度優先搜索的基本思想是(1)從圖中某個頂點v0出發，(2)依此頂點v0的重復(3)分別從這些鄰接點出發，依v0的所有各個未曾，則vi的所有未時應保證：如果vi和vk為當前端結它們的各的鄰接點應的鄰接點之。直到所有端結點均沒有的鄰接被若此時圖中尚有頂點未，則另選圖中一個未例例A GBEHCFI其中：箭頭方向例2例2：起BFS起例BFSv3→v2→v1→→v4→v5→v9→v8→一般一般圖的廣度優先搜索 算法 voidBFSTraverse(MGraphG,:從 intv,u, VertexTypew1,u1;LinkQueue ①fst;{ Visit(G.vexs[v]);EnQueue(&Q,v{DeQueue(&Q, }{visited[w]=TRUE;Visit(G.vexs[w]);EnQueue(&Q,w);}}7.47.4圖的連通性問題7.4.3最小生成 (連通網的)最小生成1、普里姆算法構造最小生成2 算法構造最小生成假設要n之間建立通訊聯絡網，則n需要修建n-1條線路，如何在最節省經費的前提下建立這個通訊網構造網的一棵最小生成樹，e條帶權的邊中選取n-條邊（不構成回路），使“權值之和”為最小1、1、普里姆算法構造基本思想 取有n個頂點的圖中的v作為生成樹的根，之后往生成樹上添加新的頂點w。在待添加的頂點w和已經在生成樹上的頂點v之間必定有一條連通頂v和w的權值取值最小的邊。之后繼續往生成樹上添加頂點，直至生成樹上含有n-1條邊為止。注意：所添加的頂點應滿足下列條件已落在生成樹上的頂點集U和尚未落在生成樹上的頂點集V-U，則應在所有連通U中頂點和V-U