第七章 圖 數(shù)據(jù)結構

第七章圖數(shù)據(jù)結構第一頁，共九十三頁，2022年，8月28日￡7.1圖的定義和術語（1）形式化定義

Graph=(V,R) V={x|x∈dataobject} //頂點的有窮非空集合 R={VR} VR={<v,w>|P(v,w)∩(v,w∈V)}//兩個頂點之間的關系集合（2）圖形表示圖7.1圖的示例(b)無向圖G2

G1

V1V2V3V4(a)有向圖G1

圖由結點及邊(弧)組成,與樹的主要區(qū)別在于圖可以有回路V3V4V5

V1V2G2第二頁，共九十三頁，2022年，8月28日(a)有向圖G1

G1＝(V1,{A1}) 其中：V1={v1,v2,v3,v4} A1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}(b)無向圖G2 G2＝(V2,{E2}) 其中：V2={v1,v2,v3,v4,v5} E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}（3）相關術語頂點（Vertex）：圖中的數(shù)據(jù)元素?；。ˋrc）：若<v,w>∈VR，則<v,w>表示從v到w的一條弧?；∥玻═ail）或初始點（Initialnode）：弧<v,w>的一個頂點v?；☆^（Head）或終端點（Terminalnode）：弧<v,w>的一個頂點w。有向圖（Digraph）：由弧和頂點組成。

邊（Edge）：若<v,w>∈VR必有<w,v>∈VR，即VR是對稱的，則以無序對(v,w)代替這兩個有序對，表示v和w之間的一條邊。無向圖（Undigraph）：由邊和頂點組成。第三頁，共九十三頁，2022年，8月28日若，用n表示圖中頂點數(shù)目，用e表示邊或弧的數(shù)目。且不考慮頂點到其自身的邊或弧，即若<vi,vj>∈VR，則vi≠vj。那么，；對于有向圖，e的對于無向圖，e的取值范圍是0到取值范圍是0到n(n－1)。無向完全圖（Completedgraph）：有條邊的無向圖。有向完全圖：有n(n－1)條弧的有向圖。

稀疏圖（Sparsegraph）：有很少條邊或?。ㄈ鏴<nlogn）的圖。反之稱為稠密圖（Densegraph）。子圖（Subgraph）：有兩個圖G=(V,{E})和G’=(V’,{E’})，如果V’V且E’則稱G’為G的子圖。E,

(a)圖7.1中G1的子圖V1V4V1V1V1V2V4V3V3V3第四頁，共九十三頁，2022年，8月28日(b)圖7.1中G2的子圖圖7.2子圖示例V1V4V1V2V4V5V3V3V1V2V1V2V4V5對于無向圖G=(V,{E})，如果邊(v,v’)∈E，則稱頂點v和v’互為鄰接點（Adjacent）。邊(v,v’)依附（Incident）于頂點v和v’，或者說(v,v’)和頂點v和v’相關聯(lián)。度：指和頂點v相關聯(lián)的邊的數(shù)目，記為TD(v)。

對于有向圖G=(V,{A})，如果弧<v,v’>∈A，則稱頂點v鄰接到頂點v’，頂點v’鄰接自頂點v?；?lt;v,v’>和頂點v、v’相關聯(lián)。入度（InDegree）：以頂點v為頭的弧的數(shù)目，記為ID(v)。 出度（OutDegree）：以頂點v為尾的弧的數(shù)目，記為OD(v)。有向圖中，頂點v的度為TD(v)＝ID(v)＋OD(v)。第五頁，共九十三頁，2022年，8月28日一般地，如果頂點vi的度記為TD(vi)，那么一個有n個頂點，e條邊或弧的圖，滿足如下關系：

路徑（Path）：在無向圖G=(V,{E})中從頂點v到頂點v’的一個頂點序列(v=vi,0,vi,1,…,vi,m=v’)，其中(vi,j-1,vi,j)∈E，1≤j≤m。若G是有向圖，則路徑也是有向的，頂點序列滿足<vi,j-1,vi,j>∈E，1≤j≤m。路徑的長度：路徑上的邊或弧的數(shù)目。

簡單回路或簡單環(huán)：除了第一個頂點和最后一個頂點之外，其余頂點不重復出現(xiàn)的回路?；芈坊颦h(huán)（Cycle）：第一個頂點和最后一個頂點相同的路徑。簡單路徑：序列中頂點不重復出現(xiàn)的路徑。連通：在無向圖G中，如果從頂點v到頂點v’有路徑，則稱v和v’是連通的。連通圖（ConnectedGraph）：對于圖中任意兩個頂點vi,vj∈V，vi和vj都是連通的圖。連通分量（ConnectedComponent）：指無向圖中的極大連通子圖。第六頁，共九十三頁，2022年，8月28日(a)無向圖G3(b)G3的3個連通分量圖7.3無向圖及其連通分量DE

G3ABCDEFGHIKLMJGHIKABCFJLM第七頁，共九十三頁，2022年，8月28日

強連通圖：在有向圖G中，如果對于每一對vi,vj∈V，vi≠vj，從vi到vj和從vj到vi都存在路徑，則稱G是強連通圖。

強連通分量：有向圖中的極大強連通子圖。

生成樹：一個連通圖的生成樹是一個極小連通子圖。它含有圖中全部頂點，但只有足以構成一棵樹的n－1條邊。圖7.4 G3的最大連通分量的一棵生成樹ABCFJLM由生成樹的定義易知： ①一棵有n個頂點的生成樹有且僅有n－1條邊。 ②如果一個圖有n個頂點和小于n－1條邊，則是非連通圖。 ③如果一個圖有n個頂點和大于n－1條邊，則一定有環(huán)。 ④有n－1條邊的圖不一定是生成樹。第八頁，共九十三頁，2022年，8月28日生成森林：一個有向圖的生成森林由若干棵有向樹組成，含有圖中全部的結點，但只有足以構成若干棵不相交的有向樹的弧。

圖7.5 一個有向圖及其生成森林ADFBCE

ABCFED第九頁，共九十三頁，2022年，8月28日邊的權、網圖有時圖的邊或弧附帶有數(shù)值信息，這種數(shù)值稱為權（Weight）在實際應用中，權值可以有某種含義。比如，在一個反映城市交通線路的圖中，邊上的權值可以表示該條線路的長度或者等級；對于一個電子線路圖，邊上的權值可以表示兩個端點之間的電阻、電流或電壓值；對于反映工程進度的圖而言，邊上的權值可以表示從前一個工程到后一個工程所需要的時間等等。每條邊或弧都帶權的圖稱為帶權圖或網絡（Network）如果邊是無方向的帶權圖，則是一個無向網圖。否則就是一個有向網圖。如下圖所示是一個有向網圖。第十頁，共九十三頁，2022年，8月28日（4）圖的抽象數(shù)據(jù)類型定義ADTGraph{數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。數(shù)據(jù)關系R： R={VR} VR={<v,w>|v,w∈V且P(v,w),<v,w>表示從v到w的弧， 謂詞P(v,w)定義了弧<v,w>的意義或信息}基本操作：CreateGraph(&G,V,VR); 初始條件：V是圖的頂點集，VR是圖中弧的集合。 操作結果：按V和VR的定義構造圖G。DestroyGraph(&G); 初始條件：圖G存在。 操作結果：銷毀圖G。第十一頁，共九十三頁，2022年，8月28日 LocateVex(G,u); 初始條件：圖G存在，u和G中頂點有相同特征。 操作結果：若G中存在頂點u，則返回該頂點在圖中位置； 否則返回其他信息。GetVex(G,v); 初始條件：圖G存在，v是G中某個頂點。 操作結果：返回v的值。PutVex(&G,v,value); 初始條件：圖G存在，v是G中某個頂點。 操作結果：對v賦值value。FirstAdjVex(G,v); 初始條件：圖G存在，v是G中某個頂點。 操作結果：返回v的第一個鄰接頂點。若頂點在G中沒有鄰 接頂點，則返回“空”。第十二頁，共九十三頁，2022年，8月28日NextAdjVex(G,v,w); 初始條件：圖G存在，v是G中某個頂點，w是v的鄰接點。 操作結果：返回v的（相對于w的）下一個鄰接頂點。若w 是v的最后一個鄰接點，則返回“空”。InsertVex(&G,v); 初始條件：圖G存在，v和圖中頂點有相同特征。 操作結果：在圖G中增添新頂點v。DeleteVex(&G,v); 初始條件：圖G存在，v是G中某個頂點。 操作結果：刪除G中頂點v及其相關的弧。InsertArc(&G,v,w); 初始條件：圖G存在，v和w是G中兩個頂點。 操作結果：在圖G中增添新弧<v,w>，若G是無向的，則還 增添對稱弧<w,v>。DeleteArc(&G,v,w); 初始條件：圖G存在，v和w是G中兩個頂點。 操作結果：在圖G中刪除弧<v,w>，若G是無向的，則還刪 除對稱弧<w,v>。第十三頁，共九十三頁，2022年，8月28日BFSTraverse(G,visit()); 初始條件：圖G存在，visit是頂點的應用函數(shù)。 操作結果：對圖進行廣度優(yōu)先遍歷。在遍歷過程中對每個頂 點調用函數(shù)Visit一次且僅一次。一旦visit()失敗， 則操作失敗。}ADTGraphDFSTraverse(G,visit()); 初始條件：圖G存在，visit是頂點的應用函數(shù)。 操作結果：對圖進行深度優(yōu)先遍歷。在遍歷過程中對每個頂 點調用函數(shù)Visit一次且僅一次。一旦visit()失敗， 則操作失敗。第十四頁，共九十三頁，2022年，8月28日￡7.2圖的存儲結構￡7.2.1數(shù)組表示法（鄰接矩陣）

（1）定義

數(shù)組表示法：用兩個數(shù)組分別存儲數(shù)據(jù)元素（頂點）的信息和數(shù)據(jù)元素之間的關系（邊或弧）的信息。（2）C語言描述 #define INFINITY INT_MAX //最大值∞ #define MAX_VERTEX_NUM 20 //最大頂點個數(shù) typedefenum{DG,DN,UDG,UDN}GraphKind; //{有向圖，有向網，無向圖，無向網} typedefstructArcCell{ VRType adj; //VRType是頂點關系類型。對無權圖，用1 //或0表示相鄰否；對帶權圖，則為權值類型。 InfoType *info; //該弧相關信息的指針 }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedefstruct{ VertexType vexs[MAX_VERTEX_NUM]; //頂點向量 AdjMatrix arcs; //鄰接矩陣 int vexnum,arcnum; //圖的當前頂點數(shù)和弧數(shù) GraphKind kind; //圖的種類標志 }MGraph;第十五頁，共九十三頁，2022年，8月28日思考…設計一個算法判斷一個圖是否是連通圖第十六頁，共九十三頁，2022年，8月28日（3）鄰接矩陣中頂點度的求法對于無向圖，頂點vi的度是鄰接矩陣中第i行（或第i列）的元素之和，即：

對于有向圖，頂點vi的出度OD(vi)為第i行的元素之和，頂點vi的入度ID(vi)為第i列的元素之和。（4）網的鄰接矩陣網的鄰接矩陣可定義為：

wi,j 若<vi,vj>或(vi,vj)∈VRA[i][j]=

∞ 反之例如，下圖列出了一個有向網和它的鄰接矩陣。

(b)鄰接矩陣(a)網N453879

1655

V1V2

V6V3V5V4第十七頁，共九十三頁，2022年，8月28日練習1:畫出下列圖的鄰接矩陣,并求出各頂點的度.V1V2V3V4（a）G1V1V2V3V4（b）G2第十八頁，共九十三頁，2022年，8月28日練習2:繪出如下有向網絡的鄰接矩陣V2V4V1V3V63527948V5617úúúúúúú?ùêêêêêêê?é￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥9￥￥=6187274￥53A第十九頁，共九十三頁，2022年，8月28日（5）圖的構造算法7.1如下：StatusCreateGraph(MGraph&G){ //采用數(shù)組（鄰接矩陣）表示法，構造圖G。 scanf(&G.kind); switch(G.kind){ caseDG: returnCreateDG; //構造有向圖G caseDN: returnCreateDN; //構造有向網G caseUDG: returnCreateUDG; //構造無向圖G caseUDN: returnCreateUDN; //構造無向網G default: returnERROR; }}//CreateGraph算法7.1是在鄰接矩陣存儲結構MGraph上對圖的構造操作的實現(xiàn)框架，它根據(jù)圖G的種類調用具體構造算法。第二十頁，共九十三頁，2022年，8月28日StatusCreateUDN(MGraph&G){ //采用數(shù)組（鄰接矩陣）表示法，構造無向網G。 scanf(&G.vexnum,&G.arcnum,&IncInfo); //IncInfo為0則各弧不含其他信息 for(i=0;i<G.vexnum;++i) scanf(&G.vexs[i]); //構造頂點向量 for(i=0;i<G.vexnum;++i) //初始化鄰接矩陣 for(j=0;j<G.vexnum;++j) G.arcs[i][j]={INFINITY,NULL}; //{adj,info} for(k=0;k<G.arcnum;++k){ //構造鄰接矩陣 scanf(&v1,&v2,&w); //輸入一條邊依附的頂點及權值 i=LocateVex(G,v1); //確定v1和v2在G中位置 j=LocateVex(G,v2); G.arcs[i][j].adj=w; //弧<v1,v2>的權值 if(IncInfo) Input(*G.arcs[i][j].info); //若弧含有相關信息，則輸入 G.arcs[j][i]=G.arcs[i][j]; //置<v1,v2>的對稱弧<v2,v1> }//for returnOK;}//CreateUDN算法7.2如下：算法7.2構造一個具有n個頂點和e條邊的無向網G。其時間復雜度為O(n2+e*n)，其中對鄰接矩陣G.arcs的初始化耗費了O(n2)的時間。第二十一頁，共九十三頁，2022年，8月28日￡7.2.2鄰接表（1）定義鄰接表（AdjacencyList）：是圖的一種鏈式存儲結構。在鄰接表中，對圖中每個頂點建立一個單鏈表，第i個單鏈表中的結點表示依附于頂點vi的邊（對有向圖是以頂點vi為尾的弧）。

逆鄰接表：即對每個頂點vi建立一個鏈接以vi為頭的弧的表。在逆鄰接表中可以方便的確定頂點的入度或以頂點vi為頭的弧。（2）結點結構頭結點datafirstarc表結點adjvexnextarcinfo表結點由3個域組成：adjvex：鄰接點域，指示與頂點vi鄰接的點在圖中的位置。nextarc：鏈域，指示下一條邊或弧的結點。info：數(shù)據(jù)域，存儲和邊或弧相關的信息，如權值等。頭結點由2個域組成：data：數(shù)據(jù)域，存儲頂點vi的名或其他有關信息。firstarc：鏈域，指向鏈表中第一個結點。表頭結點通常以順序結構的形式存儲，以便隨機訪問任一頂點的鏈表。第二十二頁，共九十三頁，2022年，8月28日 #define MAX_VERTEX_NUM 20 typedefstructArcNode{ int adjvex; //該弧所指向的頂點的位置 structArcNode*nextarc; //指向下一條弧的指針 InfoType *info; //該弧相關信息的指針 }ArcNode; typedefstructVNode{ VertexType data; //頂點信息 structArcNode*firstarc; //指向第一條依附該頂點的弧的指針 }VNode,AdjList[MAX_VERTEX_NUM]; typedefstruct{ AdjList vertices; int vexnum,arcnum; //圖的當前頂點數(shù)和弧數(shù) kind kind; //圖的種類標志 }ALGraph;

（3）C語言描述第二十三頁，共九十三頁，2022年，8月28日（4）圖形表示(a)有向圖和無向圖G1G2G1V1V2V3V4G2V1V2V4V5V3

(b)G1的鄰接表V1V2V3V401232 130V1V2V3V401232003(c)G1的逆鄰接表第二十四頁，共九十三頁，2022年，8月28日

(d)G2的鄰接表圖7.6鄰接表和逆鄰接表

對于無向圖，頂點vi的度恰為第i個鏈表中的結點數(shù)。 對于有向圖，頂點vi的出度OD(vi)為第i個鏈表中的結點個數(shù)；求頂點vi的入度ID(vi)必須遍歷整個鄰接表，查找所有鏈表中其鄰接點域的值為i的結點，它們的總和即為頂點vi的入度。（5）鄰接表中頂點度的求法V1V2V3V40123V54312120424310G2V1V2V4V5V3第二十五頁，共九十三頁，2022年，8月28日練習3:畫出下列圖的鄰接表與逆鄰接表,并求出各頂點的度.V1V2V3V4（a）G1V1V2V3V4（b）G2v3v2v13201v42310^^（a）G1的鄰接表data2^0^firstarcv3v2v13201v412333^^^^（b）G2的鄰接表datafirstarc第二十六頁，共九十三頁，2022年，8月28日練習3:畫出下列圖的鄰接表與逆鄰接表,并求出各頂點的度.V1V2V3V4（a）G1V1V2V3V4（b）G2v3v2v13201v401200^^^^（c）G2的逆鄰接表datafirstarc第二十七頁，共九十三頁，2022年，8月28日￡7.2.3十字鏈表（有向圖）（1）定義

十字鏈表（OrthogonalList）：是有向圖的另一種鏈式存儲結構?？梢钥闯墒菍⒂邢驁D的鄰接表和逆鄰接表結合起來得到的一種鏈表。也即弧頭相同的弧在同一鏈表上，弧尾相同的弧也在同一鏈表上（2）結點結構弧結點頭結點（頂點結點）datafirstinfirstouttailvexheadvexhlinktlinkinfo弧結點由5個域組成： tailvex：尾域，指示弧尾頂點在圖中的位置。 headvex：頭域，指示弧頭頂點在圖中的位置。 hlink：鏈域，指向弧頭相同的下一條弧。 tlink：鏈域，指向弧尾相同的下一條弧。 info：數(shù)據(jù)域，指向該弧的相關信息。頭結點由3個域組成： data：數(shù)據(jù)域，存儲和頂點相關的信息，如頂點名稱等。 firstin：鏈域，指向以該頂點為弧頭的第一個弧結點。 firstout：鏈域，指向以該頂點為弧尾的第一個弧結點。第二十八頁，共九十三頁，2022年，8月28日 #define MAX_VERTEX_NUM 20 typedefstructArcBox{ int tailvex,headvex; //該弧的尾和頭頂點的位置 structArcBox*hlink,*tlink; //分別為弧頭相同和弧尾相同的弧的鏈域 InfoType *info; //該弧相關信息的指針 }ArcBox; typedefstructVexNode{ VertexType data; ArcBox *firstin,*firstout; //分別指向該頂點第一條入弧和出弧 }VexNode; typedefstruct{ VexNode xlist[MAX_VERTEX_NUM]; //表頭向量 int vexnum,arcnum; //有向圖的當前頂點數(shù)和弧數(shù) }OLGraph;

（3）C語言描述第二十九頁，共九十三頁，2022年，8月28日（4）圖形表示圖7.7 有向圖的十字鏈表V1V2

(a)V3V4

V1(b)

01V2

1V3

2V4

3

02

20

30

23

31

32

0第三十頁，共九十三頁，2022年，8月28日（5）圖的構造StatusCreateDG(OLGraph&G){ //采用十字鏈表存儲表示，構造有向圖G(G.kind=DG)。 scanf(&G.vexnum,&G.arcnum,&IncInfo); //IncInfo為0則各弧不含其他信息 for(i=0;i<G.vexnum;++i){ //構造表頭向量 scanf(&G.xlist[i].data); //輸入頂點值 G.xlist[i].firstin=NULL; //初始化指針 G.xlist[i].firstout=NULL; } for(k=0;k<G.arcnum;++k){ //輸入各弧并構造十字鏈表 scanf(&v1,&v2); //輸入一條弧的始點和終點 i=LocateVex(G,v1); //確定v1和v2在G中位置 j=LocateVex(G,v2); p=(ArcBox*)malloc(sizeof(ArcBox)); //假定有足夠空間 *p={i,j,G.xlist[j].firstin,G.xlist[i].firstout,NULL}; //對弧結點賦值{tailvex,headvex,hlink,tlink,info} G.xlist[j].firstin=G.xlist[i].firstout=p; //完成在入弧和出弧鏈頭的插入 if(IncInfo) Input(*p－>info); //若弧含有相關信息，則輸入 }//for}//CreateDG算法7.3如下：第三十一頁，共九十三頁，2022年，8月28日￡7.2.4鄰接多重表（無向圖）（1）定義

鄰接多重表（AdjacencyMultilist）：是無向圖的另一種鏈式存儲結構。鄰接多重表的結構和十字鏈表類似。在鄰接多重表中，所有依附于同一頂點的邊串聯(lián)在同一鏈表中，由于每條邊依附兩個頂點，則每個邊結點同時鏈接在兩個鏈表中。（2）結點結構頂點結點datafirstedgemarkivexilinkjvexjlinkinfo邊結點邊結點由6個域組成： mark：標志域，用以標記該條邊是否被搜索過。 ivex和jvex：為該邊依附的兩個頂點在圖中的位置。 ilink：鏈域，指向下一條依附于頂點ivex的邊。 jlink：鏈域，指向下一條依附于頂點jvex的邊。 info：數(shù)據(jù)域，指向和邊相關的各種信息的指針域。頂點結點有2個域組成： data：數(shù)據(jù)域，存儲和該頂點相關的信息。 firstedge：鏈域，指示第一條依附于該頂點的邊。在鄰接多重表中,每一條邊用一個結點表示,每一個頂點也用一個結點表示。第三十二頁，共九十三頁，2022年，8月28日（3）C語言描述 #define MAX_VERTEX_NUM 20 typedefemnu{unvisited,visited}VisitIf; typedefstructEBox{ VisitIf mark; //訪問標記 int ivex,jvex; //該邊依附的兩個頂點的位置 structEBox*ilink,*jlink; //分別指向依附這兩個頂點的下一條邊 InfoType *info; //該邊信息指針 }EBox; typedefstructVexBox{ VertexType data; EBox *firstedge; //指向第一條依附該頂點的邊 }VexBox; typedefstruct{ VexBox adjmulist[MAX_VERTEX_NUM]; int vexnum,edgenum; //無向圖的當前頂點數(shù)和邊數(shù) }AMLGraph;第三十三頁，共九十三頁，2022年，8月28日（4）圖形表示G2V1V2V4V5V3圖7.8 無向圖G2的鄰接多重表4V1

01V2

1V3

2V4

3

0V5

03

21

23

41

24第三十四頁，共九十三頁，2022年，8月28日￡7.3圖的遍歷￡7.3.1深度優(yōu)先遍歷

圖的遍歷（TraversingGraph）：從圖中某一頂點出發(fā)，訪遍圖中其余頂點，且使每一個頂點僅被訪問一次的過程。（1）定義深度優(yōu)先遍歷（Depth_FirstSearch）類似于樹的先根遍歷，是樹的先根遍歷的推廣。主要思想：假設初始狀態(tài)是圖中所有頂點未曾被訪問，則深度優(yōu)先搜索可從圖中某個頂點v出發(fā)，訪問此頂點，然后依次從v的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。第三十五頁，共九十三頁，2022年，8月28日（2）深度優(yōu)先搜索遍歷圖的過程演示以圖7.9(a)中無向圖G4為例，深度優(yōu)先搜索遍歷圖。(b)深度優(yōu)先搜索的過程

(a)無向圖圖7.9遍歷圖的過程

G4V1V2V3V4V5V6V7V8V1V2V3V4V5V6V7V8112573482說明：假設從v1出發(fā)進行搜索，在訪問了頂點v1之后，選擇鄰接點v2。因為v2未曾訪問，則從v2成分進行搜索。依次類推，接著從v4，v8，v5出發(fā)進行搜索。在訪問了v5之后，由于v5的鄰接點都已被訪問，則搜索回到v8。同理，搜索繼續(xù)回到v4，v2直至v1，此時由于v1的另一個鄰接點未被訪問，則搜索又從v1到v3，再繼續(xù)進行下去。得到的頂點訪問序列為：第三十六頁，共九十三頁，2022年，8月28日（3）遍歷算法//-----------------------算法7.4和7.5使用的全局變量---------------------------- Booleanvisited[MAX]; //訪問標志數(shù)組 Status(*VisitFunc)(intv); //函數(shù)變量 算法7.5如下：voidDFS(GraphG,intv){ //從第v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖G。 visited[v]=TRUE; VisitFunc(v); //訪問第v個頂點 for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)) if(!visited[w]) DFS(G,w); //對v尚未訪問的鄰接頂點w遞歸調用DFS}算法7.4如下： voidDFSTraverse(GraphG,Status(*Visit)(intv)){ //對圖G作深度優(yōu)先遍歷 VisitFunc=Visit; //使用全局變量VisitFunc,使DFS不必設函數(shù)指針參數(shù) for(v=0;v<G.vexnum;++v) visited[v]=FALSE; //訪問標志數(shù)組初始化 for(v=0;v<G.vexnum;++v) if(!visited[v]) DFS(G,v); //對尚未訪問的頂點調用DFS }

G3ABCDEFGHIKLMJ第三十七頁，共九十三頁，2022年，8月28日￡7.3.2廣度優(yōu)先遍歷（1）定義廣度優(yōu)先遍歷（Breadth_FirstSearch）類似于樹的按層次遍歷的過程。

主要思想：假設從圖中某頂點v出發(fā)，在訪問了v之后依次訪問v的各個未曾訪問過的鄰接點，然后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。（2）廣度優(yōu)先搜索遍歷圖的過程演示以圖7.9(a)中無向圖為例，廣度優(yōu)先搜索遍歷圖。第三十八頁，共九十三頁，2022年，8月28日V1V2V3V4V5V6V7V8圖7.10 廣度優(yōu)先搜索的過程

說明：假設從v1出發(fā)進行搜索。首先訪問v1和v1的鄰接點v2和v3，然后依次訪問v2的鄰接點v4和v5及v3的鄰接點v6和v7，最后訪問v4的鄰接點v8。由于這些頂點的鄰接點均已被訪問，并且圖中所有頂點都被訪問，由此完成了圖的遍歷。得到的頂點訪問序列為：

G4V1V2V3V4V5V6V7V8第三十九頁，共九十三頁，2022年，8月28日voidBFSTraverse(GraphG,Status(*Visit)(intv)){ //按廣度優(yōu)先非遞歸遍歷圖G。使用輔助隊列Q和訪問標志數(shù)組visited。 for(v=0;v<G.vexnum;++v) visited[v]=FALSE; InitQueue(Q); //置空的輔助隊列Q for(v=0;v<G.vexnum;++v) if(!visited[v]){ //v尚未訪問 visited[v]=TRUE; Visit(v); EnQueue(Q,v); //v入隊列 while(!QueueEmpty(Q)){ DeQueue(Q,u); //隊頭元素出隊并置為u for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w)) if(!Visited[w]){ //w為u的尚未訪問的鄰接頂點 visited[w]=TRUE; Visit(w); EnQueue(Q,w); }//if }//while }//if}//BFSTraverse（3）遍歷算法算法7.6如下：第四十頁，共九十三頁，2022年，8月28日練習4:分別寫出下圖的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列深度優(yōu)先搜索序列:1—6—7—5—4—3—2(不唯一)廣度優(yōu)先搜索序列:1—2—3—4—6—5—7(不唯一)依照圖的存儲結構和FirstAdjVex(G,v)和NextAdjVex(G,v,w)操作定義的不同,可以有不同的優(yōu)先搜索序列.第四十一頁，共九十三頁，2022年，8月28日￡7.4圖的連通性問題￡7.4.1無向圖的連通分量和生成樹廣度優(yōu)先生成樹：在連通圖中，由廣度優(yōu)先搜索得到的生成樹。（1）連通圖在對無向圖進行遍歷時，對于連通圖，僅需從圖中任一頂點出發(fā)，進行深度優(yōu)先搜索或廣度優(yōu)先搜索，便可訪問到圖中所有結點。深度優(yōu)先生成樹：在連通圖中，由深度優(yōu)先搜索得到的生成樹。（2）非連通圖在對無向圖進行遍歷時，對于非連通圖，需從多個頂點出發(fā)進行搜索，而每一次從一個新的起始點出發(fā)進行搜索過程中得到的頂點訪問序列恰為其各個連通分量中的頂點集。

生成森林：在非連通圖中，每個連通分量中的頂點集和遍歷時走過的邊一起構成若干棵生成樹，這些連通分量的生成樹組成非連通圖的生成森林。

深度優(yōu)先生成森林：在非連通圖中，由深度優(yōu)先搜索得到的生成森林。

廣度優(yōu)先生成森林：在非連通圖中，由廣度優(yōu)先搜索得到的生成森林。第四十二頁，共九十三頁，2022年，8月28日（3）圖形表示

(a) G4的深度優(yōu)先生成樹V2V3V4V5V6V7V8V1V1V2V3V4V5V6V7V8圖7.10生成樹和生成森林

(b) G4的廣度優(yōu)先生成樹A1L2F6C7M3J4B5D8E9G10K11I13H12

(c) G5的深度優(yōu)先生成森林

G4V1V2V3V4V5V6V7V8

G5ABCDEFGHIKLMJ第四十三頁，共九十三頁，2022年，8月28日（4）非連通圖的深度優(yōu)先森林的生成算法voidDFSForest(GraphG,CSTree&T){ //建立無向圖G的深度優(yōu)先生成森林的（最左）孩子（右）兄弟鏈表T。 T=NULL; for(v=0;v<G.vexnum;++v) visited[v]=FALSE; for(v=0;v<G.vexnum;++v) if(!visited[v]){ //第v頂點為新的生成樹的根結點 p=(CSTree)malloc(sizeof(CSNode)); //分配根結點 *p={GetVex(G,v),NULL,NULL}; //給該結點賦值 if(!T) T=p; //是第一棵生成樹的根（T的根） else q－>nextsibling=p; //是其他生成樹的根(前一棵的根的“兄弟”) q=p; //q指示當前生成樹的根 DFSTree(G,v,p); //建立以p為根的生成樹 }}//DFSForest算法7.7如下：第四十四頁，共九十三頁，2022年，8月28日voidDFSTree(GraphG,intv,CSTree&T){ //從第v個頂點出發(fā)深度優(yōu)先遍歷圖G，建立以T為根的生成樹 visited[v]=TRUE; first=TRUE; for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)) if(!visited[w]){ p=(CSTree)malloc(sizeof(CSNode)); //分配孩子結點 *p={GetVex(G,w),NULL,NULL}; if(first){ //w是v的第一個未被訪問的鄰接頂點 T－>lchild=p; first=FALSE; //是根的左孩子結點 }//if else{ //w是v的其他未被訪問的鄰接頂點 q－>nextsibling=p; //是上以鄰接頂點的右兄弟結點 }//else q=p; DFSTree(G,w,q); //從第w個頂點出發(fā)深度優(yōu)先遍歷圖G，建立子生成樹q }//if}//DFSTree算法7.8如下：

G5ABCDEFGHIKLMJ第四十五頁，共九十三頁，2022年，8月28日￡7.4.2最小生成樹最小生成樹的MST性質：假設N=(V,{E})是一個連通網，U是頂點集V的一個非空子集。若(u,v)是一條具有最小權值（代價）的邊，其中u∈U,v∈V－U，則必存在一棵包含邊(u,v)的最小生成樹。（1）普里姆（Prim）算法①算法思想假設N=(V,{E})是連通網，TE是N上最小生成樹中邊的集合。算法從U={u0}(u0∈V)，TE={}開始，重復執(zhí)行下述操作：在所有u∈U，v∈V-U的邊(u,v)∈E中找一條代價最小的邊(u0,v0)并入集合TE，同時v0并入U，直至U=V為止。此時TE中必有n－1條邊，則T=(V,{TE})為N的最小生成樹。②算法實現(xiàn)為實現(xiàn)算法需附設一個輔助數(shù)組closedge，以記錄從U到V-U具有最小代價的邊。對每個頂點vi∈V-U，在輔助數(shù)組中存在一個相應分量closedge[i－1]，它包括兩個域，其中l(wèi)owcost存儲該邊上的權。顯然， closedge[i－1].lowcost=Min{cost(u,vi)|u∈U}vex域存儲該邊依附的在U中的頂點。第四十六頁，共九十三頁，2022年，8月28日假設以二維數(shù)組表示網的鄰接矩陣，且令兩個頂點之間不存在的邊的權值為機內允許的最大值（INT_MAX），則Prim算法如下所示。算法7.9如下：voidMiniSpanTree_PRIM(MGraphG,VertexTypeu){ //用Prim算法從第u個頂點出發(fā)構造網G的最小生成樹T，輸出T的各條邊。 //記錄從頂點集U到V－U的代價最小的邊的輔助數(shù)組定義： // struct{ // VertexType adjvex; // VRType lowcost; // }closedge[MAX_VERTEX_NUM]; k=LocateVex(G,u); for(j=0;j<G.vexnum;++j) //輔助數(shù)組初始化 if(j!=k) closedge[j]={u,G.arcs[k][j].adj}; //{adjvex,lowcost} closedge[k].lowcost=0; //初始，U={u}第四十七頁，共九十三頁，2022年，8月28日for(i=0;i<G.vexnum;++i){ //選擇其余G.vexnum－1個頂點 k=minimum(closedge); //求出T的下一個結點：第k頂點 //此時closedge[k].lowcost= // MIN{closedge[vi].lowcost|closedge[vi].lowcost>0,vi∈V-U} printf(closedge[k].adjvex,G.vexs[k]); //輸出生成樹的邊 closedge[k].lowcost=0; //第k頂點并入U集 for(j=0;j<G.vexnum;++j) if(G.arcs[k][j].adj<closedge[j].lowcost) //新頂點并入U后重新選擇最小邊 closedge[j]={G.vexs[k],G.arcs[k][j].adj};}//for}//MiniSpanTree_PRIM時間復雜度：O(n2)。其中n為網中的頂點數(shù)?？梢姡鋾r間復雜度與網中的邊數(shù)無關，因此適用于求邊稠密的網的最小生成樹。第四十八頁，共九十三頁，2022年，8月28日③例子例如，圖7.12所示為按Prim算法構造網的一棵最小生成樹的過程，在構造過程中各分量的變化如圖7.13所示。圖7.12Prim算法構造最小生成樹的過程1V1V2V4V3V6V5542V1V2V4V3V6V514V1V2V4V3V6V5142V1V2V4V3V6V56556631425V1V2V4V3V6V531425(a)(d)(e)(f)(c)(b)V1V2V4V3V6V51第四十九頁，共九十三頁，2022年，8月28日

說明：初始狀態(tài)時，由于U={v1}，則到V－U中各頂點的最小邊，即為從依附于頂點1的各條邊中，找到一條代價最小的邊(u0,v0)=(1,3)為生成樹上的第一條邊，同時將v0(=v3)并入集合U。然后修改輔助數(shù)組中的值。首先將closedge[2].lowcost改為’0’以示頂點v3已并入U。然后，由于邊(v3,v2)上的權值小于closedge[1].lowcost，則需修改closedge[1]為邊(v3,v2)及其權值。同理修改closedge[4]和closedge[5]。依次類推，直到U=V。closedge12 345 U V－U k

iadjvex v1v1v1{v1}{v2,v3,v4,2lowcost 615v5,v6} adjvex v3 v1v3v3{v1,v3}{v2,v4,5lowcost 505 64v5,v6} adjvex v3 v3{v1,v3,{v2,v5}1lowcost 50060v6,v4} adjvex v3 v6v3{v1,v3,{v2,v4,3lowcost 50260v6}v5} adjvex v2 {v1,v3,{v5}4lowcost 00030v6,v4,v2} adjvex {v1,v3,v6,{}lowcost 00000v4,v2,v5}圖7.13圖7.12構造最小生成樹過程中輔助數(shù)組中各分量的值V1V2V4V3V6V56556631425第五十頁，共九十三頁，2022年，8月28日（2）克魯斯卡爾（Kruskal）算法①算法思想假設連通網N=(V,{E})，則令最小生成樹的初始狀態(tài)為只有n個頂點而無邊的非連通圖T=(V,{})，圖中每個頂點自成一個連通分量。在E中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價最小的邊。依次類推，直至T中所有頂點都在同一連通分量上為止。

②時間復雜度Kruskal算法的時間復雜度為：O(eloge)(e為網中邊的數(shù)目)，因此其相對于Prim算法而言，適合于求邊稀疏的網的最小生成樹。③例子例如，圖7.14所示為依照Kruskal算法構造一棵最小生成樹的過程。(a)(b)(c)V1V2V4V3V6V51V1V2V4V3V6V512V1V2V4V3V6V56556631425第五十一頁，共九十三頁，2022年，8月28日V1V2V4V3V6V531425V1V2V4V3V6V51234(d)(e)圖7.14Kruskal算法構造最小生成樹的過程V1V2V4V3V6V5123(f)

說明：代價分別為1，2，3，4的4條邊由于滿足上述條件，則先后被加入到T中，代價為5的兩條邊(v1,v4)和(v3,v4)被舍去。因為它們依附的兩頂點在同一連通分量上，它們若加入T中，則會使T中產生回路，而下一條代價(=5)最小的邊(v2,v3)聯(lián)結兩個連通分量，則可加入T。由此構造一棵最小生成樹。V1V2V4V3V6V56556631425第五十二頁，共九十三頁，2022年，8月28日￡7.5有向無環(huán)圖及其應用￡7.5.1有向無環(huán)圖

有向無環(huán)圖（directedacyclinegraph）：無環(huán)的有向圖，簡稱DAG圖。DAG圖是一類較有向樹更一般的特殊有向圖。圖7.15有向樹、DAG圖和有向圖一例例如，圖7.15示例了有向樹、DAG圖和有向圖的例子。第五十三頁，共九十三頁，2022年，8月28日（2）表達式子式共享例如，下述表達式((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)，用二叉樹表示如圖7.16所示，用有向無環(huán)圖表示如圖7.17所示。圖7.16 用二叉樹描述表達式*+***+e+++*abbccddecd第五十四頁，共九十三頁，2022年，8月28日圖7.17 描述表達式的有向無環(huán)圖*+eabcd*+*+**+***+e+++*abbccddecd第五十五頁，共九十三頁，2022年，8月28日￡7.5.2拓撲排序

全序關系：R是集合X上的偏序，若對每個x,y∈X必有xRy或yRx，則稱R是集合X上的全序關系。(教材P180)（1）定義

拓撲排序（TopologicalSort）：簡單地說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。

偏序關系：若集合X上的關系R是自反的、反對稱的和傳遞的，則稱R是集合X上的偏序關系。 （2）AOV-網

AOV-網：用頂點表示活動，用弧表示活動間的優(yōu)先關系的有向圖稱為頂點表示活動的網（ActivityOnVertexNetwork），簡稱AOV-網。在網中，若從頂點i到頂點j有一條有向路徑，則i是j的前驅；j是i的后繼。若<i,j>是網中的一條弧，則i是j的直接前驅；j是i的直接后繼。第五十六頁，共九十三頁，2022年，8月28日例如，一個軟件專業(yè)的學生必須學習一系列基本課程(如圖7.18所示)，其中有些課程是基礎課，它獨力于其他課程，如《高等數(shù)學》；而另一些課程必須在學完作為它的基礎的先修課程才能開始。如，在《程序設計基礎》和《離散數(shù)學》學完之前就不能開始學習《數(shù)據(jù)結構》。這些先決條件定義了課程之間的領先（優(yōu)先）關系。這個關系可以用有向圖7.19清楚的表示。圖7.18 軟件專業(yè)的學生必須學習的課程課程編號 課程名稱 先決條件C1 程序設計基礎 無C2 離散數(shù)學 C1C3 數(shù)據(jù)結構 C1，C2

C4 匯編語言 C1C5 語言的設計和分析 C3，C4C6 計算機原理 C11

C7 編譯原理 C3，C5C8 操作系統(tǒng) C3，C6

C9 高等數(shù)學 無

C10 線性代數(shù) C9C12 數(shù)值分析 C9，C10，C1

C11 普通物理 C9第五十七頁，共九十三頁，2022年，8月28日圖7.19表示課程之間優(yōu)先關系的有向圖C4C5C1C2C3C7C12C8C6C9C10C11圖7.19中，頂點表示課程，有向邊（?。┍硎鞠葲Q條件。若課程i是課程j的先決條件，則圖中有弧<i,j>。如下，為圖7.19中的有向圖的拓撲有序序列的其中兩個序列： 1．(C1,C2,C3,C4,C5,C7,C9,C10,C11,C6,C12,C8) 2．(C9,C10,C11,C6,C1,C12,C4,C2,C3,C5,C7,C8)第五十八頁，共九十三頁，2022年，8月28日（3）拓撲排序①算法思想： 1．在有向圖中選一個沒有前驅的頂點且輸出之。 2．從圖中刪除該頂點和所有以它為尾的弧。 3．重復上述兩步，直至全部頂點均已輸出，或者當前圖中不存在無前驅的頂點為止。②算法實現(xiàn)：針對上述操作，采用鄰接表作有向圖的存儲結構，且在頭結點中增加一個存放頂點入度的數(shù)組（indegree）。入度為0的頂點即為沒有前驅的頂點，刪除頂點及以它為弧的操作，則可以弧頭頂點的入度減1來實現(xiàn)。StatusTopologicalSort(ALGraphG){ //有向圖G采用鄰接表存儲結構。 //若G無回路，則輸出G的頂點的一個拓撲序列，并返回OK，否則ERROR。 FindInDegree(G,indegree); //對各頂點求入度indegree[0..vernum－1] InitStack(S); for(i=0;i<G.vexnum;++i) //建0入度頂點棧S if(!indegree[i]) Push(S,i); //入度為0者進棧算法7.10如下：第五十九頁，共九十三頁，2022年，8月28日 count=0; while(!StackEmpty(S)){ Pop(S,i); printf(i,G.vertices[i].data); //輸出i號頂點并計數(shù) ++count; for(p=G.vertices[i].firstarc;p;p=p－>nextarc){ k=p－>adjvex; //對i號頂點的每個鄰接點的入度減1 if(!(――indegree[k])) Push(S,k); //若入度減為0，則入棧 }//for }//while if(count<G.vexnum) returnERROR; //該有向圖有回路}//TopologicalSort時間復雜度：O(n+e)。第六十頁，共九十三頁，2022年，8月28日③例子以圖7.20(a)中的有向圖為例。

圖7.20AOV-網及其拓撲有序序列產生的過程(a)AOV-網； (b)輸出v6之后； (c)輸出v1之后；(d)輸出v4之后；(e)輸出v3之后； (f)輸出v2之后；V1V2V4V3V6V5V1V2V4V3V5V2V4V3V5V2V3V5V2V5V5說明：圖中v1和v6沒有前驅，則可任選一個。假設先輸出v6，在輸出v6及弧<v6,v4>,<v6,v5>之后，只有頂點v1