7.1圖的定義和術(shù)語第7章圖和廣義表7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4連通圖的最小生成樹7.5單源最短路徑7.6拓樸排序7.7關(guān)鍵路徑*7.8廣義表7.1圖的定義和術(shù)語第7章圖和廣義表7.2圖的存

圖(graph)是由一個頂點(vertex)的有窮非空集V(G)和一個弧或邊(arc)的集合E(G)組成。記作G={V,E}.圖又分為有向圖和無向圖,圖中的頂點即為數(shù)據(jù)元素。對有向圖沒有箭頭的出發(fā)端稱為弧尾(tail)或始點(initial)。帶箭頭的終止端稱為弧頭(head)或終點(terminalnode)用有序?qū)?lt;v,w>表示從v到w的一條弧。(如圖中<A,B>）對無向圖7.1圖的定義和術(shù)語1圖的定義ABCDFEG(a)有向圖G1圖(graph)是由一個頂點(vertex)7.1圖的定義和術(shù)語1圖的定義ACBEDF(b)無向圖G2

圖(graph)是由一個頂點(vertex)的有窮非空集V(G)和一個弧或邊(arc)的集合E(G)組成。記作G={V,E}.圖又分為有向圖和無向圖,圖中的頂點即為數(shù)據(jù)元素。對有向圖沒有箭頭的出發(fā)端稱為弧尾(tail)或始點(initial)。帶箭頭的終止端稱為弧頭(head)或終點(terminalnode)用有序?qū)?lt;v,w>表示從v到w的一條弧。(如圖中<A,B>）對無向圖,用(v,w)表示一條邊。如(A,B)表示無向圖G2中的一條邊。7.1圖的定義和術(shù)語1圖的定義ACBEDF(b)無ACBEDF(b)無向圖G2圖的表示G1=(V1,E1)V1={A,C,B,F,D,E,G}E1={<A,B>,<B,C>,<B,F>,<B,E>,<C,E>,<E,D>,<D,C>,<E,B>,<F,G>}(a)有向圖G1ABCDFEGG2=(V2,E2)V2={A,B,C,D,E,F}E2={(A,B),(A,C),(B,C),(B,E),(B,F),(C,F),(C,D),(E,F),(C,F)}ACBEDF(b)無向圖G2圖的表示(a)有向圖G1AB假設有兩個圖G=(V,E)和G'=(V',E'),如果V'V且E'E,則稱G'是G的子圖?？梢宰C明,對于具有n個頂點的無向圖的邊和具有n個頂點的有向圖的弧的最大數(shù)目分別為n(n-1)/2和n(n-1)。稱具有n(n-1)/2條邊的無向圖為完全圖(completedgrahp)。稱具有n(n-1)條弧的有向圖為完全有向圖稱邊或弧的數(shù)目e<nlogn的圖為稀疏圖(sparsegraph),反之則稱為稠密圖(densegraph)。

子圖2幾個常用術(shù)語ABCDFEGABFCDE假設有兩個圖G=(V,E)可以證明,對于具有n個頂點的無向圖的邊和具有n個頂點的有向圖的弧的最大數(shù)目分別為n(n-1)/2和n(n-1)。稱具有n(n-1)/2條邊的無向圖為完全圖(completedgrahp)。稱具有n(n-1)條弧的有向圖為完全有向圖稱邊或弧的數(shù)目e<nlogn的圖為稀疏圖(sparsegraph),反之則稱為稠密圖(densegraph)。

子圖2幾個常用術(shù)語ACBEDFACDBEF假設有兩個圖G=(V,E)和G'=(V',E'),如果V'V且E'E,則稱G'是G的子圖?？梢宰C明,對于具有n個頂點的無向圖的邊和具有度、入度和出度

若u→v是有向圖中的一條弧,則稱u鄰接到v,或稱v被鄰接到u。圖中所鄰接到頂點v的弧(即以它為弧頭的弧)的數(shù)目,稱為頂點v的入度(indegree),記作ID(v);反之,從某頂點u出發(fā)的弧(即鄰接自該頂點的弧),稱為該頂點的出度(outdegree),記作OD(u)。有向圖中頂點v的入度和出度之和稱為該頂點的總度,簡稱為度(degree),記作TD(v)ABCDFEG如右所示的有向圖頂點C鄰接到頂點E,vc→vE

ID(vc)=2OD(vc)=1TD(vc)=3度、入度和出度ABCDFEG如右所無向圖中頂點的度定義為與該頂點相連的邊的數(shù)目。如果頂點vi的度記為TD(vi),則一個含n個頂點,e條邊或弧的圖,滿足如下關(guān)系ACBEDFTD(vB)=4度、入度和出度

若u→v是有向圖中的一條弧,則稱u鄰接到v,或稱v被鄰接到u。圖中所鄰接到頂點v的弧(即以它為弧頭的弧)的數(shù)目,稱為頂點v的入度(indegree),記作ID(v);反之,從某頂點u出發(fā)的弧(即鄰接自該頂點的弧),稱為該頂點的出度(outdegree),記作OD(u)。有向圖中頂點v的入度和出度之和稱為該頂點的總度,簡稱為度(degree),記作TD(v)無向圖中頂點的度定義為與該頂點ACBEDFT路徑和回路若有向圖G中k+1個頂點之間都有弧存在(即<v0,v1>,<v1,v2>,…,<vk-1,vk>是圖G中的弧),則這個頂點的序列(v0,v1,...,vk)為從頂點v0到頂點vk的一條有向路徑,路徑中弧的數(shù)目定義為路徑長度。若序列中的頂點都不相同,則稱為簡單路徑。(v0,v1,v2,v4,v1,v5,v6)是v0到v6的一條有向路徑(v0,v1,v5,v6)也是v0到v6的一條有向路徑0123546簡單路徑路徑和回路若路徑和回路若有向圖G中k+1個頂點之間都有弧存在(即<v0,v1>,<v1,v2>,…,<vk-1,vk>是圖G中的弧),則這個頂點的序列(v0,v1,...,vk)為從頂點v0到頂點vk的一條有向路徑,路徑中弧的數(shù)目定義為路徑長度。若序列中的頂點都不相同,則稱為簡單路徑。對于無向圖,相鄰頂點之間存在邊的k+1個頂點序列構(gòu)成一條長度為k的無向路徑。(v0,v1,v2,v4,v5,v2,v3)是v0到v3的一條無向路徑(v0,v1,v2,v3)也是v0到v3的一條有向路徑如果v0和vk是同一個頂點,則是一條由某個頂點出發(fā)又回到該頂點的路徑,稱這種路徑為回路或環(huán)(cycle).簡單路徑021435(v0,v1,v5,v2,v0)是一條回路或環(huán)路路徑和回路若連通圖和連通分量若無向圖中任意兩個頂點之間都存在一條無向路徑,則稱該無向圖為連通圖。若有向圖中任意兩個頂點之間都存在一條有向路徑,則稱該有向圖為強連通圖。非(強)連通圖中各個(強)連通子圖稱為該圖的(強)連通分量.連通圖非連通圖ACBEDFABCDFEG強連通圖非強連通圖2個連通分量4個強連通分量連通圖和連通分量帶權(quán)圖和網(wǎng)邊(弧)上帶有權(quán)值的圖稱為網(wǎng)。帶權(quán)有向圖和帶權(quán)無向圖分別稱為有向網(wǎng)和無向網(wǎng)。1023438659有向網(wǎng)帶權(quán)圖和網(wǎng)圖的基本操作CreateGraph(&G,V,VR)...BFSTraverse(G,v,visit())圖的基本操作CreateGr7.2圖的存儲結(jié)構(gòu)1.圖的數(shù)組(鄰接矩陣)存儲表示2.圖的鄰接表存儲表示7.2圖的存儲結(jié)構(gòu)1.圖的數(shù)組(鄰接矩陣)存7.2圖的存儲結(jié)構(gòu)7.2.1圖的數(shù)組(鄰接矩陣)存儲表示

無權(quán)圖的鄰接矩陣的定義設G=(V,E)是具有n(n＞0)個頂點的圖,頂點的順序依次為(v0,v1,…,vn-1),則G的鄰接矩陣A是n階方陣A[0][0]A[0][1]…A[0][n-1]A[1][0]A[1][1]…A[1][n-1]………A[n-1][0]A[n-1][1]…A[n-1][n-1]A=A[i][j]=1若vi和vj之間有弧或邊存在0反之7.2圖的存儲結(jié)構(gòu)7.2.1圖的數(shù)組(鄰接矩陣)存7.2圖的存儲結(jié)構(gòu)7.2.1圖的數(shù)組(鄰接矩陣)存儲表示

網(wǎng)的鄰接矩陣的定義設G=(V,E)是具有n(n＞0)個頂點的帶權(quán)圖,頂點的順序依次為(v0,v1,…,vn-1),wij則是頂點i和j的弧(邊)上的權(quán)值,則G的鄰接矩陣A是n階方陣A[0][0]A[0][1]…A[0][n-1]A[1][0]A[1][1]…A[1][n-1]………A[n-1][0]A[n-1][1]…A[n-1][n-1]A=A[i][j]=wij若vi和vj之間有弧或邊存在∞反之7.2圖的存儲結(jié)構(gòu)7.2.1圖的數(shù)組(鄰接矩陣)存G1v0v1v2v3v4v1v2v3v4v0(1)有向圖的鄰接矩陣úúúúúú?ùêêêêêê?é0100100000110000110001010a.有向圖的鄰接矩陣一般是個稀疏矩陣．12304b.第i行非零元素的個數(shù)是頂點vi的的出度。c.第j列非零元素的個數(shù)是頂點vj的的入度。有向圖鄰接矩陣的幾個特點G1v0v1v2v3v4v1v2v3v4v0(1)有向圖的鄰v0v1v2v3v4v1v2v3v4v0(2)無向圖的鄰接矩陣úúúúúú?ùêêêêêê?é0110110111110100110111010a.無向圖的鄰接矩陣是個對稱矩陣;b.第i行非零元素的個數(shù)是頂點vi的度。12304G2無向圖鄰接矩陣的幾個特點v0v1v2v3v4v1v2v3v4v0(2)無向圖的鄰接矩v0v1v2v3v4v1v2v3v4v0(3)有向網(wǎng)的鄰接矩陣úúúúúú?ùêêêêêê?é∞∞∞∞∞∞∞9∞∞6∞∞∞∞∞∞3∞∞∞5∞8∞1023438659有向網(wǎng)v0v1v2v3v4v1v2v3v4v0(3)有向網(wǎng)的鄰接一個圖的鄰接矩陣是唯一的一個圖的鄰接矩陣是唯一的鄰接矩陣的類型定義constINT_MAX=32767;constMAX_V=20;typedefintVRType;typedefintInforType;typedefintVertexType;typedefenum{DG, DN,AG,AN}GraphKind;typedefstruct{VRTypeadj;InforType*info;}ArcCell,AdjMatrix[MAX_V][MAX_V];typedefstruct{VertexTypevex[MAX_V];AdjMatrixarcs;intvexnum,arcnum;GraphKindkind;}MGraph;//設置“無窮大”值//最大頂點數(shù)目//圖的種類//鄰接矩陣類型//頂點關(guān)系類型//指向邊或弧信息(如權(quán)值)的指針//頂點信息數(shù)組(如頂點編號等)//圖的鄰接矩陣//圖的頂點數(shù)和邊(弧)的數(shù)目//圖的種類標志鄰接矩陣的類型定義//設置“無窮大”值//最大頂點數(shù)目//圖7.2.2圖的鄰接表存儲表示鄰接表是一種鏈式存儲表示方法，它類似于樹的孩子鏈表。在鄰接表中,對圖中每個頂點建立一個單鏈表,第i個頂點的單鏈表的所有結(jié)點,表示依附于頂點vi的邊(或以vi為尾的弧)。每個單鏈表上附設一個表頭結(jié)點。表結(jié)點和表頭結(jié)點的結(jié)構(gòu)如下：

7.2.2圖的鄰接表存儲表示

(1)表結(jié)點的三個域adjvex是個整形變量,指示與頂點vi鄰接的頂點在表頭數(shù)組中的存儲位置(下標);nextarc是指針型變量,指向下一條邊或弧的結(jié)點;Info存儲與邊或弧相關(guān)的信息,如權(quán)值等;

(2)表頭結(jié)點的兩個域data存儲頂點vi的名稱或編號等信息;firstarc指向鏈表中第一個結(jié)點。adjvexnextarcinfodatafirstarc表結(jié)點表頭結(jié)點(1)表結(jié)點的三個域adjvexnextarcadjvexnextarcinfodatafirstarc表結(jié)點表頭結(jié)點typedefstructArcNode{intadjvex;structArcNode*nextarc;InfoType*info;}ArcNode;typedefstruct{VertexTypedata;ArcNode*firstarc;}VNode,AdjList[MAX_V];typedefstruct//圖的鄰接表類型{AdjListvertices;//存儲圖中所有頂點的數(shù)組intvexnum,arcnum;//存儲圖的頂點數(shù)目和邊(弧)的數(shù)目intkind;//圖的種類標志}ALGraph;adjvexnextarcinfodatafirstarc表typedefstructArcNode{intadjvex;structArcNode*nextarc;InfoType*info;}ArcNode;typedefstruct{VertexTypedata;ArcNode*firstarc;}VNode,AdjList[MAX_V];typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;}ALGraph;ALGraphG;01MAX_V-1.........G.verticesG.vexnumG.arcnumG.kinddatafirstarctypedefstructArcNodetypedef24∧13∧有向圖的鄰接表存儲示意圖01234ABCDE56FGMAX_V-1......有向圖G1ABCDFEG0512346∧6∧1∧245∧∧有向圖G1的鄰接表注意：圖的鄰接表不是唯一的，因為與一個頂點相鄰的邊的順序沒有明確規(guī)定。在此規(guī)定：邊的順序號按相關(guān)頂點的順序號由小到大排定。24∧13∧有向圖的鄰接表存儲示意圖012042112∧01234ABCDE56FGMAX_V-1......有向圖G1ABCDFEG0512346∧∧1∧∧3∧5∧有向圖G的逆鄰接表表結(jié)點指針域鏈接的不是出邊而是入邊.042112∧01234ABCDE56FGMAX_V-1..有向網(wǎng)G3有向網(wǎng)的鄰接表BACDE386591835∧23∧46∧29∧01234ABCDE MAX_V-1......12034∧有向網(wǎng)G3的鄰接表有向網(wǎng)G3有向網(wǎng)的鄰接表BACDE386591835∧23∧算法7.1建立無向圖的鄰接表存儲結(jié)構(gòu)voidCreateUDG(ALGraph&G){inti,j,k,IncInfo,v1,v2;ArcNode*pi,*pj;cin>>G.vexnum>>G.arcnum;//>>IncInfo;for(i=0;i<G.vexnum;++i){cin>>G.vertices[i].data;G.vertices[i].firstarc=NULL;}for(k=0;k<G.arcnum;++k){cin>>v1>>v2;i=LocateVex(G,v1);j=LocateVex(G,v2);pi=newArcNode;pi->adjvex=j;pi->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=pi;pj=newArcNode;pj->adjvex=i;pj->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=pj;

//if(IncInfo){cin>>pj->info;pi->info=pj->info;}}}//輸入邊的起、止頂點名稱值//確定v1,v2下標//輸入頂點名稱值//用頭插法插入v1的相鄰結(jié)點//用頭插法插入v2的相鄰結(jié)點算法7.1建立無向圖的鄰接表存儲結(jié)構(gòu)voidCreattypedefstructArcNode{intadjvex;structArcNode*nextarc;InfoType*info;}ArcNode,*ArcNodeP;typedefstruct{VertexTypedata;ArcNode*firstarc;}VNode,AdjList[MAX_V];typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;}ALGraph;typedefstructArcNodetypedef//算法7.1的改進算法(用尾插法建立無向圖的鄰接表)voidCreateUDG(ALGraph&G){inti,j,k;ArcNode*pi,*pj,**qi,**qj;VertexTypevi,vj;

cin>>G.vexnum>>G.arcnum;for(i=0;i<G.vexnum;++i){cin>>G.vertices[i].data;G.vertices[i].firstarc=NULL;}

qi=newArcNodeP[G.vexnum];qj=qi;for(i=0;i<G.vexnum;i++)qi[i]=NULL;for(k=0;k<G.arcnum;++k){cin>>vi>>vj;i=LocateVex(G,vi);j=LocateVex(G,vj);pi=newArcNode;pi->adjvex=j;

if(G.vertices[i].firstarc==NULL){pi->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=pi;}else{pi->nextarc=qi[i]->nextarc;qi[i]->nextarc=pi;}qi[i]=pi;pj=newArcNode;pj->adjvex=i;if(G.vertices[j].firstarc==NULL){pj->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=pj;}else{pj->nextarc=qj[j]->nextarc;qj[j]->nextarc=pj;}qj[j]=pj;}//for}//CreateUDG//算法7.1的改進算法(用尾插法建立無向圖的鄰接表)//算法7.1的改進算法(用尾插法建立無向圖的鄰接表)voidCreateUDG(ALGraph&G){inti,j,k;ArcNode*pi,*pj,**qi,**qj;VertexTypevi,vj;

cin>>G.vexnum>>G.arcnum;for(i=0;i<G.vexnum;++i){cin>>G.vertices[i].data;G.vertices[i].firstarc=NULL;}

qi=newArcNodeP[G.vexnum];qj=qi;for(i=0;i<G.vexnum;i++)qi[i]=NULL;...}//算法7.1的改進算法(用尾插法建立無向圖的鄰接表)//算法7.1的改進算法(用尾插法建立無向圖的鄰接表)voidCreateUDG(ALGraph&G){...for(k=0;k<G.arcnum;++k){cin>>vi>>vj;//輸入一條邊的始點vi和終點vj的名稱值i=LocateVex(G,vi);//確定vi的下標j=LocateVex(G,vj);//確定vj的下標pi=newArcNode;pi->adjvex=j;if(G.vertices[i].firstarc==NULL){pi->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=pi;}else{pi->nextarc=qi[i]->nextarc;qi[i]->nextarc=pi;}qi[i]=pi;...}//算法7.1的改進算法(用尾插法建立無向圖的鄰接表)//算法7.1的改進算法(用尾插法建立無向圖的鄰接表)voidCreateUDG(ALGraph&G){...for(k=0;k<G.arcnum;++k){...

pj=newArcNode;pj->adjvex=i;if(G.vertices[j].firstarc==NULL){pj->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=pj;}else{pj->nextarc=qj[j]->nextarc;qj[j]->nextarc=pj;}qj[j]=pj;}//for}//CreateUDG//算法7.1的改進算法(用尾插法建立無向圖的鄰接表)//補充算法7.1-1確定頂點名稱值為v的存儲下標intLocateVex(ALGraphG,VertexTypev){inti;for(i=0;i<G.vexnum;i++)if(v==G.vertices[i].data) break;if(i>=G.vexnum) ErrorMessage("頂點名稱值有錯！");returni;}//補充算法7.1-1確定頂點名稱值為v的存儲下標//補充算法7.1-2輸出圖的鄰接表voidDisplayGraph(ALGraphG){inti;ArcNode*p;cout<<"當前圖的鄰接表為："<<endl;for(i=0;i<G.vexnum;i++){cout<<i<<“:”<<G.vertices[i].data;//輸出表頭p=G.vertices[i].firstarc;while(p!=NULL)//輸出與頂點i相鄰的結(jié)點單鏈表{cout<<"->"<<p->adjvex;p=p->nextarc;}cout<<endl;}}//補充算法7.1-2輸出圖的鄰接表//主函數(shù)調(diào)用實例...ALGraphG;CreateUDG(G);DisplayGraph(G);無向圖G3923146587以右上圖為例圖中9個頂點名稱值的輸入順序為1,2,3,4,5,6,7,8,9圖中11條邊的輸入順序為1-2,1-3,1-4,2-3,2-4,3-6,4-9,5-6,5-7,5-8,7-9//主函數(shù)調(diào)用實例無向圖G3923146587以右上圖為例//運行結(jié)果(省略了輸入提示信息)當前圖的鄰接表為：0:1->1->2->31:2->0->2->32:3->0->1->53:4->0->1->84:5->5->6->75:6->2->46:7->4->77:8->4->68:9->3Pressanykeytocontinue無向圖G39231465870123456MAX_V-178.........123456789123∧023∧015∧018∧567∧24∧47∧67∧3∧//運行結(jié)果(省略了輸入提示信息)無向圖G3923146587.3圖的遍歷(GraphTraversal)從給定圖中某個指定的頂點(稱為初始點)出發(fā),沿著圖的某條路徑對圖中其余頂點進行訪問,且使每個頂點僅被訪問一次,這一過程稱為圖的遍歷(graphtraversal)。圖的遍歷方法有兩種：(1)深度優(yōu)先搜索(DepthFirstSearch-DFS)(2)廣度優(yōu)先搜索(BreadthFirstSearch-BFS)。7.3圖的遍歷(GraphTraversal)7.3.2深度優(yōu)先搜索遍歷圖圖的深度優(yōu)先搜索(depthfirstsearch)類似于樹的先根遍歷的推廣，搜索過程是：(1)從圖中某個初始頂點v出發(fā),首先訪問該頂點v;(2)依次從它的各個未被訪問的鄰接頂點出發(fā)深度優(yōu)先遍歷圖,直至圖中所有和v有路徑相通的頂點都被訪問到;(3)若尚有其它頂點未被訪問,則另選一個未被訪問的鄰接點作起始頂點;(4)重復上述過程,直到圖中所有頂點都被訪問到為止。顯然,遍歷過程是個遞歸過程。BFS7.3.2深度優(yōu)先搜索遍歷圖圖的//算法7.4從鄰接表頭下標為v的頂點從發(fā),遞歸地深度//優(yōu)先遍歷圖G。voidDFS(ALGraphG,intv){intw;ArcNode*p;

visited[v]=true;cout<<G.vertices[v].data<<",";for(p=G.vertices[v].firstarc;p;p=p->nextarc){w=p->adjvex;if(!visited[w])DFS(G,w);//對v的未訪問的鄰接頂點w進行DFS}}//DFS//算法7.4從鄰接表頭下標為v的頂點從發(fā),遞歸地深//主函數(shù)調(diào)用實例inti;ALGraphG;CreateUDG(G);visited=newbool[G.vexnum];for(i=0;i<G.vexnum;i++)visited[i]=false;DisplayGraph(G);cout<<"深度優(yōu)先搜索的頂點序列為"<<endl;DFS(G,LocateVex(G,'3'));//建立圖的鄰接表//建立搜索訪問標志數(shù)組//false表示該頂點尚未被訪問//顯示圖的鄰接矩陣//對課本P209的圖7.6(a)//以v3頂點為起點,進行深度優(yōu)先搜索運行結(jié)果如下//初始化訪問標志數(shù)組//主函數(shù)調(diào)用實例//建立圖的鄰接表//建立搜索訪問標志數(shù)組輸入頂點數(shù)目和邊的數(shù)目:911輸入第1個頂點的值:1...輸入第9個頂點的值:9請輸入第1條邊的起止頂點值:12...請輸入第11條邊的起止頂點值:78當前圖的鄰接表為：0:1->1->2->31:2->0->2->32:3->0->1->53:4->0->1->84:5->5->6->75:6->2->46:7->4->77:8->4->68:9->3深度優(yōu)先搜索的頂點序列為3,1,2,4,9,6,5,7,8,Pressanykeytocontinue注意課本P209正數(shù)第四行給出的DFS結(jié)果有誤！輸入頂點數(shù)目和邊的數(shù)目:911注意無向圖G3無向圖的深度優(yōu)先搜索手工操作過程舉例1923146587v3v1v2v4v9v6v5v7v8注：課本P209正數(shù)第4行給出的DFS遍歷序列不正確。無向圖G3無向圖的深度優(yōu)先搜索手工操作過程舉例1無向圖的深度優(yōu)先搜索手工操作過程舉例2A無向圖G2ACBEDFBCDEF程序驗證6個頂點的輸入次序為:A,B,C,D,E,F9條邊的輸入次序為:A-B,A-C,B-C,B-E,B-F,C-D,C-E,C-F,E-F算法運行結(jié)果如下無向圖的深度優(yōu)先搜索手工操作過程舉例2A無向圖輸入頂點數(shù)目和邊的數(shù)目:69輸入第1個頂點的值:A...輸入第6個頂點的值:F請輸入第1條邊的起止頂點值:AB...請輸入第9條邊的起止頂點值:EF當前圖的鄰接表為：0:A->1->21:B->0->2->4->52:C->0->1->3->4->53:D->24:E->1->2->55:F->1->2->4深度優(yōu)先搜索的頂點序列為A,B,C,D,E,F,Pressanykeytocontinue無向圖G2ACBEDF輸入頂點數(shù)目和邊的數(shù)目:69無向圖G2ACBEDF有向圖的深度優(yōu)先搜索過程v0v1v2v4v3得到的遍歷序列:結(jié)束以v0為初始頂點有向圖10234有向圖的深度優(yōu)先搜索過程v0v1v2v4v3得7.3.2廣度優(yōu)先搜索(BFS)遍歷圖廣度優(yōu)先搜索(breadthfirstsearch)的基本思想是：從圖中某頂點v出發(fā),在訪問了v之后依次訪問v的各個未曾訪問過的鄰接點,然后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點,并使得“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問,直至圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中尚有頂點未被訪問,則需另選一個未曾被訪問的頂點作為新的起始點,重復上述過程,直至圖中所有頂點都被訪問到為止。為存儲已被訪問過的頂點,需附設一個隊列。BFS過程類似于樹的按層次遍歷,7.3.2廣度優(yōu)先搜索(BFS)遍歷圖廣度fv1fif(!visited[v]){visited[v]=TRUE;VisitFunc(G.vexs[v]);EnQueue_Sq(Q,v);while(!QueueEmpty_Sq(Q)){DeQueue_Sq(Q,u);for(w=0;w<G.vexnum;w++;) if(G.arcs[u,w].adj&&!visited[w]) {visited[w]=TRUE;VisitFunc(w);EnQueue_Sq(Q,w); }//if}//while}//if923146587rv3v3ru=v3w=0frv11v2rv22345v6rv6v1v4rv4ffv5rv5fv9rv9fv7rv7v8rv8fff隊列為空，遍歷結(jié)束fv1fif(!visited[v])923146587fv1f923146587rv3v3rfrv1v2rv2v6rv6v4rv4ffv5rv5fv9rv9fv7rv7v8rv8fff隊列為空，遍歷結(jié)束fv1f923146587rv3v3rfrv1v2rv2v612304無向圖無向圖的廣度優(yōu)先搜索遍歷過程

21304得到的遍歷序列:以為v2初始頂點134rf0隊列隊列為空，遍歷結(jié)束12304無向圖無向圖的廣度優(yōu)先搜索遍歷過程2有向圖的廣度優(yōu)先搜索遍歷過程

01342得到的遍歷序列:以v0為初始頂點132rf4隊列有向圖10234rrfrfrff隊列為空，遍歷結(jié)束有向圖的廣度優(yōu)先搜索遍歷過程01342得到的遍7.4連通網(wǎng)的最小生成樹1.生成樹(SpanningTree)在一個含有n個頂點的連通圖中,必能選出n-1條邊構(gòu)成一個極小連通子圖,它含有圖中全部n個頂點,但只有足以構(gòu)成一棵樹的n-1條邊,稱這顆樹為連通圖的生成樹。

極小連通子圖:若刪除極小連通子圖的任意一條邊,該圖就成為非連通圖,若在極小連通子圖中增加一條邊,必定構(gòu)成一個環(huán)。對一個連通圖進行一次深度優(yōu)先搜索或廣度優(yōu)先搜索得到的頂點集合及相關(guān)邊的集合就構(gòu)成圖G的一個生成樹(DFS生成樹或BFS生成樹)一個連通圖的生成樹不是唯一的。7.4連通網(wǎng)的最小生成樹1.生成樹(Sbacdefg1012167653428914(a)連通網(wǎng)bacdefg1676329(b)權(quán)值總和為43的生成樹bacdefg1273428(c)權(quán)值總和為36的生成樹bacdefg10121642814(d)權(quán)值總和為64的生成樹一個連通網(wǎng)的所有生成樹中,具有權(quán)值總和最小的生成樹稱為連通網(wǎng)的最小生成樹bacdefg1012167653428914(a)連通網(wǎng)b如何構(gòu)造一個帶權(quán)無向連通圖的最小生成樹？1.克魯斯卡爾(Kruskal)算法2.普里姆(Prim)算法。問題如何構(gòu)造一個帶權(quán)無向連通圖的最小生成樹？問題1.克魯斯卡爾(Kruskal)算法克魯斯卡爾算法的基本思想為：為使生成樹上的總權(quán)值之和達最小,應使每一條邊的上的僅值盡可能小,自然應從權(quán)值最小的邊選起,直至選出n-1條權(quán)值最小的邊為止。然而這n-1條邊必須不構(gòu)成回路。因此并非每一條居當前權(quán)值最小的邊都可選。1.克魯斯卡爾(Kruskal)算法首先構(gòu)造只含n個頂點的森林,然后依權(quán)值從小到大從連通網(wǎng)中選擇邊加入到森林中去,并使森林中不產(chǎn)生回路,直至森林變成一顆樹為止。12874210121676534289141.克魯斯卡爾(Kruskal)算法克魯斯卡爾算法的具體做法如下：bacdefgbacdefg3克魯斯卡爾算法構(gòu)造的最小生成樹

54321首先構(gòu)造只含n個頂點的森林,然后依權(quán)值從小到大從連通網(wǎng)中選擇邊加入到森林中去,并使森林中不產(chǎn)生回路,直至森林變成一顆樹為止。1.克魯斯卡爾(Kruskal)算法克魯斯卡爾算法的具體做法如下：061563613542552401354254321首先選取圖中任意一個頂點v作為生成樹的根,之后繼續(xù)往生成樹中添加頂點w,則在頂點w和v之間必須有邊,且該邊上的權(quán)值應在所有和v相鄰接的邊中屬最小.2.普里姆(Prim)算法普里姆算法的基本思想為：

2.普里姆(Prim)算法普里姆算法的具體做法如下：從具有n個頂點的連通網(wǎng)G=(V,E)中找出最小生成樹T=(U,TE)的步驟如下：1.選G中任一頂點v為起點,初始化U={v},將v與V-U中所有相鄰頂點構(gòu)成的邊加入候選邊集E',重復以下步驟,直到全部n個頂點都加入到U中為止。

①將E'中最小權(quán)值的邊加入TE,并將該邊在V-U中的頂點vk加入U中,同時將vk從V-U中刪除。②考查vk與V-U中所有相鄰頂點構(gòu)成的邊,若邊(vk,vj)的權(quán)小于E'中邊(vu,vj)的權(quán),則用(vk,vj)取而代之;若E'不存在與vj關(guān)聯(lián)的邊,則將(vk,vj)加入E'中。2.普里姆(Prim)算法從2,g}1012167653428914bacdefgU={V={V-U={E'(候選邊直接在原圖中標出)a,b,c,d,e,f,g}a}b,c,d,e,f,g}(a,b):12,b}V-U={(b,f):7,f}g}(f,e):2,e}g},d}g},c}(e,d):4(d,c):3g(e,g):8}TE127348bacdefgn個結(jié)點已全部加入生成樹中,結(jié)束！普里姆算法構(gòu)造最小生成樹的過程2,g}1012167653428914bacdefgU={152430321545651524636以v5為起點，采用Prim算法，寫出構(gòu)造連通網(wǎng)G的最小生成樹的過程。032154圖G2352432512403251524032155152430321545651524636以v7.5單源最短路徑單源最短路徑的背景是,從某個城市出發(fā),能否到達其他各城市？走哪條路線花費最少？單源路徑的抽象提法為：從有向網(wǎng)中的源點到其余各終點有否路徑？其最短路徑及其長度是什么？從源點到終點的路徑可能存在三種情況：一種是沒有路徑;另一種是只有一條路徑;第三種情況是存在多條路徑。úúúúúú?ùêêêêêê?é8∞∞∞∞12∞6∞∞∞∞5∞∞30100∞∞∞∞201015∞∞∞∞∞∞18∞∞∞∞∞∞∞0900000∞∞∞圖7.15有向網(wǎng)及其鄰接矩陣9101810515b2030128agfedc7.5單源最短路徑單源最短路徑的背景是,從7.5單源最短路徑單源最短路徑的背景是,從某個城市出發(fā),能否到達其他各城市？走哪條路線花費最少？單源路徑的抽象提法為：從有向網(wǎng)中的源點到其余各終點有否路徑？其最短路徑及其長度是什么？從源點到終點的路徑可能存在三種情況：一種是沒有路徑;另一種是只有一條路徑;第三種情況是存在多條路徑。9101810515b2030128agfedcb到f無路徑b到a只有一條路徑b到d有三條路徑(b,a,g,c,e,d):64(b,c,e,d):27(b,d):307.5單源最短路徑單源最短路徑的背景是,從7.5單源最短路徑單源最短路徑的背景是,從某個城市出發(fā),能否到達其他各城市？走哪條路線花費最少？單源路徑的抽象提法為：從有向網(wǎng)中的源點到其余各終點有否路徑？其最短路徑及其長度是什么？從源點到終點的路徑可能存在三種情況：一種是沒有路徑;另一種是只有一條路徑;第三種情況是存在多條路徑。9101810515b2030128agfedc0123456úúúúúú?ùêêêêêê?é8∞∞∞∞12∞6∞∞∞∞5∞∞30100∞∞∞∞201015∞∞∞∞∞∞18∞∞∞∞∞∞∞0900000∞∞∞01234560123456AS[7][7]圖7.15有向網(wǎng)及其鄰接矩陣問題如何求出有向網(wǎng)G={V,E}中某一頂點(稱為源點)到G中其余任一頂點的帶權(quán)最短路徑?單源最短路徑問題迪杰斯特拉(Dijkstra)算法7.5單源最短路徑單源最短路徑的背景是,從則u為目前找到的從源點出發(fā)的最短路徑的終點,將u加入S。(3)搜索u與網(wǎng)中所有頂點w構(gòu)成的弧,若迪杰斯特拉(Dijkstra)算法(1)設AS[n][n]為有向網(wǎng)G={V,E}的鄰接矩陣,vi為源點,S為最短路徑終點集,初態(tài)S={vi},一維組Dist[n]的每個分量記錄當前找到的從vi出發(fā),途經(jīng)S中頂點到各終點的候選路徑長度,其初始值為

Dist[n]=AS[i,n](7-4)(2)選擇滿足下式的頂點u

Dist[u]=min{Dist[w]|(7-5)Dist[u]+AS[u,w]<Dist[w]則令Dist[w]=Dist[u]+AS[u,w](7-6)(4)重復步驟(2)和(3),直到與vi有路徑的頂點都加入S為止,即可求得G中源點vi到其余頂點的最短距離,另設Path[n][n]記錄最短路徑則u為目前找到的從源點出發(fā)的最短路徑的終點path[7][7]209101810515b30128agfedc0123456dist[7]0123456S=abcdefgbabcbd2001030∞∞∞,c}15bce,e}3027cedbceg,a},d}29,g}bcefadgúúúúúú?ùêêêêêê?é8∞∞∞∞12∞6∞∞∞∞5∞∞30100∞∞∞∞201015∞∞∞∞∞∞18∞∞∞∞∞∞∞0900000∞∞∞01234560123456ag(a)Dist和Path的初始狀態(tài),從中求得從b到c的最短路徑(b)修改Dist和Path的值,從中求得從b到e的最短路徑(c)修改Dist和Path的值,從中求得從b到a的最短路徑(d)修改Dist和Path的值,從中求得從b到d的最短路徑(e)修改Dist和Path的值,從中求得從b到g的最短路徑(f)修改Dist和Path的值,可見b到f沒有路徑網(wǎng)中所有與源點b有路徑的頂點已加入S集合中,結(jié)束path[7][7]209101810515b30128ag}a0123456dist[]4766641b658agfedc12bcefadgabcdefgúúúúúú?ùêêêêêê?é∞∞∞812∞52∞∞4∞∞660∞∞∞∞41∞6∞6∞∞∞∞∞∞∞1∞070000∞∞∞∞∞∞∞∞0123456path[][]abcdefgbabcbbdbgS=,a},c},d},e},f}4066∞∞∞5ca119,gcea1710cegbceaf16fg}a0123456dist[]4766641b658agfe7.6拓樸排序1.AOV網(wǎng)課程號課程名稱先修課C1C語言程序設計無C2計算機導論無C3數(shù)據(jù)結(jié)構(gòu)C1,C13C4計算機系統(tǒng)結(jié)構(gòu)C2C5編譯原理C3C6操作系統(tǒng)C3,C4C7計算機網(wǎng)絡C5C8數(shù)據(jù)庫C5,C6C9高等數(shù)學無C10數(shù)值分析C1,C9C11C++語言C1,C3C12軟件工程C7,C8C13離散數(shù)學C9C2C1C9C10C11C4C3C13C6C8C5C7C12頂點(vertex)表示某種行動(activity),弧表示兩種行動間的制約關(guān)系,這種有向圖簡稱為AOV(activityonvertex活動頂點網(wǎng))AOV網(wǎng)的死鎖現(xiàn)象7.6拓樸排序1.AOV網(wǎng)2.拓樸排序若在有向圖中從u到v有一條弧,則在由圖中頂點組成的頂點排列序列中,u一定排在v的之前,稱有向圖的這個操作為拓樸排序,所得頂點序列為拓樸有序序列.顯然拓樸排序序列不是唯一的,但可以檢驗一個AOV網(wǎng)是存在死鎖現(xiàn)象,若存在死鎖則不可能得到拓樸有充序列。3.拓樸排序方法:首先在網(wǎng)中選取一個沒前驅(qū)的頂點,輸出它并從網(wǎng)中刪除此頂點以及所有以它為尾的弧,重復這一操作,直到所有的頂點都被輸出為止.如果在此過程中找不到?jīng)]有前驅(qū)的結(jié)點,則說明尚未輸出的子圖中必有回路.2.拓樸排序13428657AOV網(wǎng)輸出序列:2571348613428657AOV網(wǎng)輸出序列:2571348613428657AOV網(wǎng)輸出序列:25714子圖中找不到無前驅(qū)的頂點,子圖有回路設計算法時注意:1.入度為0的頂點是無前驅(qū)結(jié)點;2.用弧頭頂點的入度減1來代替“刪除了無前驅(qū)頂點及以它為尾的弧”13428657AOV網(wǎng)輸出序列:25714子圖中找不到無前本章小結(jié)

本章基本學習要點如下：(1)掌握圖的相關(guān)概念,包括圖、有向圖、無向圖、完全圖、子圖、連通圖、強連通圖；頂點的度、入度、出度、簡單回路和環(huán)等定義。(2)掌握圖的兩種存儲結(jié)構(gòu)：鄰接矩陣和鄰接表。(3)掌握圖的深度優(yōu)先搜索遍歷、廣度優(yōu)先搜索遍歷方法.(4)掌握最小生成樹構(gòu)成算法：克魯斯卡爾算法、普里姆算法。(5)掌握單源最短路徑算法：迪杰斯特拉算法(6)掌握拓樸排序的概念及拓樸排序方法本章小結(jié)本章作業(yè)7.1增加第(6)問：以V2為起始源點,分別寫出對該圖進行DFS和BFS遍歷得到的頂點序列。7.4（仿例題求解方法寫出構(gòu)造最小生成樹的過程）7.5（仿例題的求解方法求解）本章作業(yè)7.1圖的定義和術(shù)語第7章圖和廣義表7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4連通圖的最小生成樹7.5單源最短路徑7.6拓樸排序7.7關(guān)鍵路徑*7.8廣義表7.1圖的定義和術(shù)語第7章圖和廣義表7.2圖的存

圖(graph)是由一個頂點(vertex)的有窮非空集V(G)和一個弧或邊(arc)的集合E(G)組成。記作G={V,E}.圖又分為有向圖和無向圖,圖中的頂點即為數(shù)據(jù)元素。對有向圖沒有箭頭的出發(fā)端稱為弧尾(tail)或始點(initial)。帶箭頭的終止端稱為弧頭(head)或終點(terminalnode)用有序?qū)?lt;v,w>表示從v到w的一條弧。(如圖中<A,B>）對無向圖7.1圖的定義和術(shù)語1圖的定義ABCDFEG(a)有向圖G1圖(graph)是由一個頂點(vertex)7.1圖的定義和術(shù)語1圖的定義ACBEDF(b)無向圖G2

圖(graph)是由一個頂點(vertex)的有窮非空集V(G)和一個弧或邊(arc)的集合E(G)組成。記作G={V,E}.圖又分為有向圖和無向圖,圖中的頂點即為數(shù)據(jù)元素。對有向圖沒有箭頭的出發(fā)端稱為弧尾(tail)或始點(initial)。帶箭頭的終止端稱為弧頭(head)或終點(terminalnode)用有序?qū)?lt;v,w>表示從v到w的一條弧。(如圖中<A,B>）對無向圖,用(v,w)表示一條邊。如(A,B)表示無向圖G2中的一條邊。7.1圖的定義和術(shù)語1圖的定義ACBEDF(b)無ACBEDF(b)無向圖G2圖的表示G1=(V1,E1)V1={A,C,B,F,D,E,G}E1={<A,B>,<B,C>,<B,F>,<B,E>,<C,E>,<E,D>,<D,C>,<E,B>,<F,G>}(a)有向圖G1ABCDFEGG2=(V2,E2)V2={A,B,C,D,E,F}E2={(A,B),(A,C),(B,C),(B,E),(B,F),(C,F),(C,D),(E,F),(C,F)}ACBEDF(b)無向圖G2圖的表示(a)有向圖G1AB假設有兩個圖G=(V,E)和G'=(V',E'),如果V'V且E'E,則稱G'是G的子圖。可以證明,對于具有n個頂點的無向圖的邊和具有n個頂點的有向圖的弧的最大數(shù)目分別為n(n-1)/2和n(n-1)。稱具有n(n-1)/2條邊的無向圖為完全圖(completedgrahp)。稱具有n(n-1)條弧的有向圖為完全有向圖稱邊或弧的數(shù)目e<nlogn的圖為稀疏圖(sparsegraph),反之則稱為稠密圖(densegraph)。

子圖2幾個常用術(shù)語ABCDFEGABFCDE假設有兩個圖G=(V,E)可以證明,對于具有n個頂點的無向圖的邊和具有n個頂點的有向圖的弧的最大數(shù)目分別為n(n-1)/2和n(n-1)。稱具有n(n-1)/2條邊的無向圖為完全圖(completedgrahp)。稱具有n(n-1)條弧的有向圖為完全有向圖稱邊或弧的數(shù)目e<nlogn的圖為稀疏圖(sparsegraph),反之則稱為稠密圖(densegraph)。

子圖2幾個常用術(shù)語ACBEDFACDBEF假設有兩個圖G=(V,E)和G'=(V',E'),如果V'V且E'E,則稱G'是G的子圖?？梢宰C明,對于具有n個頂點的無向圖的邊和具有度、入度和出度

若u→v是有向圖中的一條弧,則稱u鄰接到v,或稱v被鄰接到u。圖中所鄰接到頂點v的弧(即以它為弧頭的弧)的數(shù)目,稱為頂點v的入度(indegree),記作ID(v);反之,從某頂點u出發(fā)的弧(即鄰接自該頂點的弧),稱為該頂點的出度(outdegree),記作OD(u)。有向圖中頂點v的入度和出度之和稱為該頂點的總度,簡稱為度(degree),記作TD(v)ABCDFEG如右所示的有向圖頂點C鄰接到頂點E,vc→vE

ID(vc)=2OD(vc)=1TD(vc)=3度、入度和出度ABCDFEG如右所無向圖中頂點的度定義為與該頂點相連的邊的數(shù)目。如果頂點vi的度記為TD(vi),則一個含n個頂點,e條邊或弧的圖,滿足如下關(guān)系ACBEDFTD(vB)=4度、入度和出度

若u→v是有向圖中的一條弧,則稱u鄰接到v,或稱v被鄰接到u。圖中所鄰接到頂點v的弧(即以它為弧頭的弧)的數(shù)目,稱為頂點v的入度(indegree),記作ID(v);反之,從某頂點u出發(fā)的弧(即鄰接自該頂點的弧),稱為該頂點的出度(outdegree),記作OD(u)。有向圖中頂點v的入度和出度之和稱為該頂點的總度,簡稱為度(degree),記作TD(v)無向圖中頂點的度定義為與該頂點ACBEDFT路徑和回路若有向圖G中k+1個頂點之間都有弧存在(即<v0,v1>,<v1,v2>,…,<vk-1,vk>是圖G中的弧),則這個頂點的序列(v0,v1,...,vk)為從頂點v0到頂點vk的一條有向路徑,路徑中弧的數(shù)目定義為路徑長度。若序列中的頂點都不相同,則稱為簡單路徑。(v0,v1,v2,v4,v1,v5,v6)是v0到v6的一條有向路徑(v0,v1,v5,v6)也是v0到v6的一條有向路徑0123546簡單路徑路徑和回路若路徑和回路若有向圖G中k+1個頂點之間都有弧存在(即<v0,v1>,<v1,v2>,…,<vk-1,vk>是圖G中的弧),則這個頂點的序列(v0,v1,...,vk)為從頂點v0到頂點vk的一條有向路徑,路徑中弧的數(shù)目定義為路徑長度。若序列中的頂點都不相同,則稱為簡單路徑。對于無向圖,相鄰頂點之間存在邊的k+1個頂點序列構(gòu)成一條長度為k的無向路徑。(v0,v1,v2,v4,v5,v2,v3)是v0到v3的一條無向路徑(v0,v1,v2,v3)也是v0到v3的一條有向路徑如果v0和vk是同一個頂點,則是一條由某個頂點出發(fā)又回到該頂點的路徑,稱這種路徑為回路或