第8章圖-圖的基本概念

18.1圖的基本概念第8章圖8.2圖的存儲(chǔ)結(jié)構(gòu)8.3圖的遍歷8.4生成樹和最小生成樹8.5最短路徑8.6拓?fù)渑判?.7AOE網(wǎng)與關(guān)鍵路徑2圖的示例V1V4V2V3V5V4V3V2V1結(jié)點(diǎn)之間的關(guān)系：多對(duì)多，任意兩個(gè)結(jié)點(diǎn)之間都可能有關(guān)系存在邊弧頂點(diǎn)3圖的抽象數(shù)據(jù)類型ADTGraph{

數(shù)據(jù)對(duì)象：D={ai|1≤i≤n，n≥0，ai屬ElemType類型}

數(shù)據(jù)關(guān)系：R={<ai,aj>|ai,aj∈D,1≤i≤n,1≤j≤n,其中每個(gè)元素可以有零個(gè)或多個(gè)直接前驅(qū)，可以有零個(gè)或多個(gè)直接后繼}

基本操作P：

InitGraph(&g)//初始化圖：構(gòu)造一個(gè)空?qǐng)Dg

ClearGraph(&g)//銷毀圖：釋放圖g占用的存儲(chǔ)空間

DFS(g)//深度優(yōu)先遍歷圖g

BFS(g)//廣度優(yōu)先遍歷圖g

…}ADTGraph48.1.1圖的定義

圖(Graph)G由兩個(gè)集合V(Vertex)和E(Edge)組成,記為G=(V,E)，其中V是頂點(diǎn)的有限集合，E是連接V中兩個(gè)不同頂點(diǎn)(頂點(diǎn)對(duì))的邊的有限集合。在圖G中，如果代表邊的頂點(diǎn)對(duì)是無序的，則稱G為無向圖，無向圖中代表邊的無序頂點(diǎn)對(duì)通常用圓括號(hào)括起來，用以表示一條無向邊。如果表示邊的頂點(diǎn)對(duì)是有序的，則稱G為有向圖，在有向圖中代表邊的頂點(diǎn)對(duì)通常用尖括號(hào)括起來。8.1圖的基本概念51.端點(diǎn)和鄰接點(diǎn)在一個(gè)無向圖中,若存在一條邊(vi,vj),則稱vi和vj為此邊的兩個(gè)端點(diǎn),并稱它們互為鄰接點(diǎn)。在一個(gè)有向圖中,若存在一條邊<vi,vj>,則稱此邊是頂點(diǎn)vi的一條出邊,同時(shí)也是頂點(diǎn)vj的一條入邊；稱vi和vj分別為此邊的起始端點(diǎn)(簡(jiǎn)稱為起點(diǎn))和終止端點(diǎn)(簡(jiǎn)稱終點(diǎn))；稱vi和vj互為鄰接點(diǎn)。8.1.2圖的基本術(shù)語62.頂點(diǎn)的度、入度和出度在無向圖中，頂點(diǎn)所具有的邊的數(shù)目稱為該頂點(diǎn)的度。在有向圖中，以頂點(diǎn)vi為終點(diǎn)的入邊的數(shù)目,稱為該頂點(diǎn)的入度。以頂點(diǎn)vi為始點(diǎn)的出邊的數(shù)目，稱為該頂點(diǎn)的出度。一個(gè)頂點(diǎn)的入度與出度的和為該頂點(diǎn)的度。若一個(gè)圖中有n個(gè)頂點(diǎn)和e條邊，每個(gè)頂點(diǎn)的度為di(1≤i≤n)，則有：73.完全圖若無向圖中的每?jī)蓚€(gè)頂點(diǎn)之間都存在著一條邊，有向圖中的每?jī)蓚€(gè)頂點(diǎn)之間都存在著方向相反的兩條邊，則稱此圖為完全圖。完全無向圖包含有n(n-1)/2條邊完全有向圖包含有n(n-1)條邊。84.稠密圖、稀疏圖當(dāng)一個(gè)圖接近完全圖時(shí)，則稱為稠密圖。相反，當(dāng)一個(gè)圖含有較少的邊數(shù)(即當(dāng)e<<n(n-1))時(shí)，則稱為稀疏圖。

5.子圖設(shè)有兩個(gè)圖G=(V,E)和G’=(V’,E’)，若V’是V的子集,即V’V，且E’是E的子集，即E’E，則稱G’是G的子圖。例如圖(b)是圖(a)的子圖，而圖(c)不是圖(a)的子圖。96.路徑和路徑長(zhǎng)度(略)

在一個(gè)圖G=(V,E)中,從頂點(diǎn)vi到頂點(diǎn)vj的一條路徑是一個(gè)頂點(diǎn)序列(vi,vi1,vi2,…,vim,vj)；若此圖G是無向圖,則邊(vi,vi1),(vi1,vi2),…,(vim-1,vim),(vim,vj)屬于E(G)；若此圖是有向圖,則<vi,vi1>,<vi1,vi2>,…,<vim-1,vim>,<vim,vj>屬于E(G)。路徑長(zhǎng)度是指一條路徑上經(jīng)過的邊的數(shù)目。若一條路徑上除開始點(diǎn)和結(jié)束點(diǎn)可以相同外，其余頂點(diǎn)均不相同，則稱此路徑為簡(jiǎn)單路徑。例如，(v0,v2,v1)就是一條簡(jiǎn)單路徑，其長(zhǎng)度為2。107.回路或環(huán)(略)若一條路徑上的開始點(diǎn)與結(jié)束點(diǎn)為同一個(gè)頂點(diǎn)，則此路徑被稱為回路或環(huán)。開始點(diǎn)與結(jié)束點(diǎn)相同的簡(jiǎn)單路徑被稱為簡(jiǎn)單回路或簡(jiǎn)單環(huán)。例如，(v0,v2,v1,v0)就是一條簡(jiǎn)單回路，其長(zhǎng)度為3。118.連通、連通圖和連通分量在無向圖G中，若從頂點(diǎn)vi到頂點(diǎn)vj有路徑，則稱vi和vj是連通的。若圖G中任意兩個(gè)頂點(diǎn)都連通，則稱G為連通圖，否則稱為非連通圖。

無向圖G中的極大連通子圖稱為G的連通分量。任何連通圖的連通分量只有一個(gè)，即本身，而非連通圖有多個(gè)連通分量。CABDEFBDEFCA129.強(qiáng)連通圖和強(qiáng)連通分量(略)在有向圖G中，若從頂點(diǎn)vi到頂點(diǎn)vj有路徑，則稱從vi到vj是連通的。若圖G中的任意兩個(gè)頂點(diǎn)vi和vj都連通，即從vi到vj和從vj到vi都存在路徑，則稱圖G是強(qiáng)連通圖。

有向圖G中的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量。1310.權(quán)和網(wǎng)圖中每一條邊都可以附有一個(gè)對(duì)應(yīng)的數(shù)值，這種與邊相關(guān)的數(shù)值稱為權(quán)。權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或花費(fèi)的代價(jià)。邊上帶有權(quán)的圖稱為帶權(quán)圖，也稱作網(wǎng)。v2v4v1v5v3v616211114336191865201531050v2v1v5v3v4v0202010301545無向網(wǎng)有向網(wǎng)14思考要連通具有n個(gè)頂點(diǎn)的無向圖，至少需要（）條邊？要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要（）條??？n-1n158.2圖的存儲(chǔ)結(jié)構(gòu)幾種常用的存儲(chǔ)結(jié)構(gòu)鄰接矩陣鄰接表十字鏈表鄰接多重表168.2.1鄰接矩陣存儲(chǔ)方法鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是具有n(n＞0)個(gè)頂點(diǎn)的圖，頂點(diǎn)的順序依次為(v0,v1,…,vn-1)，則G的鄰接矩陣A是n階方陣。其定義如下：

(1)如果G是無向圖,則：

A[i][j]=1:若(vi,vj)∈E(G)0:其他

(2)如果G是有向圖,則：

A[i][j]=1:若<vi,vj>∈E(G)0:其他

(3)如果G是帶權(quán)無向圖,則：

A[i][j]=wij:若vi≠vj且(vi,vj)∈E(G)∞:其他

(4)如果G是帶權(quán)有向圖,則：

A[i][j]=wij:若vi≠vj且<vi,vj>∈E(G)∞:其他171320413204A1＝0123401234A2＝0123401234對(duì)稱不對(duì)稱18（1）對(duì)于有n個(gè)頂點(diǎn)e條邊的無向圖，鄰接矩陣表示時(shí)有多少個(gè)元素，多少個(gè)非0元素？（2）對(duì)于有n個(gè)頂點(diǎn)e條邊的有向圖，鄰接矩陣表示時(shí)有多少個(gè)元素，多少個(gè)非0元素？（3）鄰接矩陣中如何求頂點(diǎn)的度？思考19(1)圖的鄰接矩陣表示是唯一的。

(2)對(duì)于含有n個(gè)頂點(diǎn)的圖，采用鄰接矩陣存儲(chǔ)時(shí)，無論是有向圖還是無向圖，也無論邊的數(shù)目是多少，其存儲(chǔ)空間均為O(n2)，所以鄰接矩陣適合于存儲(chǔ)邊數(shù)較多的稠密圖。

(3)無向圖的鄰接矩陣一定是一個(gè)對(duì)稱矩陣。按照壓縮存儲(chǔ)的思想，只需存放上(或下)三角形陣的元素即可。

(4)對(duì)于無向圖，鄰接矩陣的第i行(或第i列)非零元素(或非∞元素)的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的度。

(5)對(duì)于有向圖，鄰接矩陣的第i行(或第i列)非零元素(或非∞元素)的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的出度(或入度)。

(6)用鄰接矩陣方法存儲(chǔ)圖，很容易確定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連。但是，要確定圖中有多少條邊，則必須按行、按列對(duì)每個(gè)元素進(jìn)行檢測(cè)，所花費(fèi)的時(shí)間代價(jià)很大。鄰接矩陣的特點(diǎn)20#defineMAXV<最大頂點(diǎn)個(gè)數(shù)> typedefstruct{intno; /*頂點(diǎn)編號(hào)*/

InfoTypeinfo; /*頂點(diǎn)其他信息*/}VertexType; /*頂點(diǎn)類型*/typedefstruct /*圖的定義*/{intedges[MAXV][MAXV]; /*鄰接矩陣*/

intvexnum,arcnum; /*頂點(diǎn)數(shù)，邊數(shù)*/

VertexTypevexs[MAXV]; /*存放頂點(diǎn)信息*/}MGraph;鄰接矩陣的數(shù)據(jù)類型定義21順序分配與鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲(chǔ)方法。在鄰接表中，對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)vi的邊(對(duì)有向圖是以頂點(diǎn)vi為尾的弧)。每個(gè)單鏈表上附設(shè)一個(gè)表頭結(jié)點(diǎn)。表結(jié)點(diǎn)和表頭結(jié)點(diǎn)的結(jié)構(gòu)如下：

表結(jié)點(diǎn)

表頭結(jié)點(diǎn)adjvexnextarcinfodatafirstarc8.2.2鄰接表存儲(chǔ)方法221320413204datafirstarcadjvexnextarc表頭結(jié)點(diǎn)表結(jié)點(diǎn)23（1）對(duì)于有n個(gè)頂點(diǎn)e條邊的無向圖，鄰接表表示時(shí)有多少個(gè)表頭結(jié)點(diǎn)，多少個(gè)表結(jié)點(diǎn)？（2）對(duì)于有n個(gè)頂點(diǎn)e條邊的有向圖，鄰接表表示時(shí)有多少個(gè)表頭結(jié)點(diǎn)，多少個(gè)表結(jié)點(diǎn)？（3）鄰接表中如何求頂點(diǎn)的度？思考24(1)鄰接表表示不唯一。這是因?yàn)樵诿總€(gè)頂點(diǎn)對(duì)應(yīng)的單鏈表中，各邊結(jié)點(diǎn)的鏈接次序可以是任意的，取決于建立鄰接表的算法以及邊的輸入次序。

(2)對(duì)于有n個(gè)頂點(diǎn)和e條邊的無向圖，其鄰接表有n個(gè)表頭結(jié)點(diǎn)和2e個(gè)邊結(jié)點(diǎn)。對(duì)于有n個(gè)頂點(diǎn)和e條邊的有向圖，其鄰接表有n個(gè)表頭結(jié)點(diǎn)和e個(gè)邊結(jié)點(diǎn)。對(duì)于稀疏圖，鄰接表比鄰接矩陣節(jié)省空間。

(3)對(duì)于無向圖，鄰接表的頂點(diǎn)vi對(duì)應(yīng)的第i個(gè)鏈表的邊結(jié)點(diǎn)數(shù)目正好是頂點(diǎn)vi的度。

(4)對(duì)于有向圖，鄰接表的頂點(diǎn)vi對(duì)應(yīng)的第i個(gè)鏈表的邊結(jié)點(diǎn)數(shù)目?jī)H僅是vi的出度。其入度為鄰接表中所有adjvex域值為i的邊結(jié)點(diǎn)數(shù)目。鄰接表的特點(diǎn)25typedefstructANode /*弧的結(jié)點(diǎn)結(jié)構(gòu)類型*/{ intadjvex;/*該弧的終點(diǎn)位置*/

structANode*nextarc;/*指向下一條弧的指針*/

InfoTypeinfo; /*該弧的相關(guān)信息*/}ArcNode;typedefstructVnode/*鄰接表頭結(jié)點(diǎn)的類型*/{ Vertexdata; /*頂點(diǎn)信息*/

ArcNode*firstarc;/*指向第一條弧*/}VNode;typedefVNodeAdjList[MAXV]; /*AdjList是鄰接表類型*/typedefstruct{AdjListadjlist; /*鄰接表*/

intn,e; /*圖中頂點(diǎn)數(shù)n和邊數(shù)e*/}ALGraph; /*圖的類型*/鄰接表存儲(chǔ)結(jié)構(gòu)的定義26已知無向圖采用鄰接表存儲(chǔ)，寫出刪除邊(i，j)的算法。voidDeletEdge(ALGraphg,inti,j){ p=g.adjlist[i].firstarc;pre=null;∥pre是前驅(qū)指針

while(p) if(p->adjvex==j) {if(pre==null)g.adjlist[i].firstarc=p->next; elsepre->next=p->next; free(p); }∥釋放空間

else{pre=p;p=p->next;}∥沿鏈表繼續(xù)查找

p=g.adjlist[j].firstarc;pre=null;∥刪頂點(diǎn)j的邊結(jié)點(diǎn)(j,i)

while(p)

if(p->adjvex==i)

{ if(pre==null)g.adjlist[j].firstarc=p->next;

elsepre->next=p->next;

free(p);

}∥釋放空間

else{pre=p;p=p->next; }∥沿鏈表繼續(xù)查找}∥DeletEdge27圖的存儲(chǔ)結(jié)構(gòu)：逆鄰接表若問題對(duì)入度更關(guān)心，則可以把線性鏈表改為：所有以頭結(jié)點(diǎn)為弧頭的弧組成的線性鏈表。此時(shí)該鄰接表稱為逆鄰接表。v3v2v10v11v22v3∧011∧∧對(duì)于有向圖，逆鄰接表表示了頂點(diǎn)的入度28有向圖的存儲(chǔ)結(jié)構(gòu)：十字鏈表有向圖的十字鏈表可以同時(shí)表示一個(gè)頂點(diǎn)和其他頂點(diǎn)的所有關(guān)系：出度和入度十字鏈表(orthogonallist)把鄰接表和逆鄰接表結(jié)合起來29無向圖的存儲(chǔ)結(jié)構(gòu)：鄰接多重表問題：在無向圖中，邊是一種“對(duì)稱”關(guān)系，因此在鄰接表中，表示任一條邊的結(jié)點(diǎn)都有兩個(gè)，而且分別在兩個(gè)不同的鏈表中。即：存儲(chǔ)表示中信息有冗余，維護(hù)不容易。改進(jìn)方法：用一個(gè)結(jié)點(diǎn)完整地表示一條邊，在整個(gè)存儲(chǔ)結(jié)構(gòu)中，有且僅有一個(gè)存儲(chǔ)單元來表示該邊。v3v2v4v10v11v22v33v410002211333∧2∧∧∧30各種存儲(chǔ)結(jié)構(gòu)的適用類型鄰接矩陣：有向圖和無向圖鄰接表（逆鄰接表）：有向圖和無向圖十字鏈表：有向圖鄰接多重表：無向圖318.3.1圖的遍歷的概念圖的遍歷：從給定圖中任意指定的頂點(diǎn)(稱為初始點(diǎn))出發(fā)，按照某種搜索方法沿著圖的邊訪問圖中的所有頂點(diǎn)，使每個(gè)頂點(diǎn)僅被訪問一次。如果給定圖是連通的無向圖或者是強(qiáng)連通的有向圖，則遍歷過程一次就能完成，并可按訪問的先后順序得到由該圖所有頂點(diǎn)組成的一個(gè)序列。根據(jù)搜索方法的不同，圖的遍歷方法有兩種：深度優(yōu)先搜索法(DFS)廣度優(yōu)先搜索法(BFS)8.3圖的遍歷需要用一個(gè)數(shù)組visited[n]記錄每個(gè)頂點(diǎn)的訪問情況，以免同一個(gè)頂點(diǎn)被訪問多次321、從圖中某個(gè)初始頂點(diǎn)v出發(fā)，訪問該頂點(diǎn)2、選擇一個(gè)與頂點(diǎn)v相鄰且沒被訪問過的頂點(diǎn)w為初始頂點(diǎn)，再?gòu)膚出發(fā)進(jìn)行深度優(yōu)先搜索，直到圖中與當(dāng)前頂點(diǎn)v連通的所有頂點(diǎn)都被訪問過為止。顯然，這個(gè)遍歷過程是個(gè)遞歸過程。3、此時(shí)若圖中尚有頂點(diǎn)未被訪問，則另選圖中下一個(gè)未被訪問的頂點(diǎn)作起始點(diǎn)，訪問該頂點(diǎn)，繼續(xù)過程2。8.3.2深度優(yōu)先遍歷33abchdekfg812345670FFFFFFFFF012345678TTTTTTTTTachdkfebgachkfedbg訪問標(biāo)志:訪問次序:achdkfe34圖的深度優(yōu)先遍歷已知圖G的鄰接表如圖所示，其從頂點(diǎn)V1出發(fā)的深度優(yōu)先搜索序列為__________。V6∧V1143V2V3V4V5245352∧∧∧∧∧012345V6∧v1v2v3v6v5v435typedefstructANode /*弧的結(jié)點(diǎn)結(jié)構(gòu)類型*/{ intadjvex;/*該弧的終點(diǎn)位置*/

structANode*nextarc;/*指向下一條弧的指針*/

InfoTypeinfo; /*該弧的相關(guān)信息*/}ArcNode;typedefstructVnode/*鄰接表頭結(jié)點(diǎn)的類型*/{ Vertexdata; /*頂點(diǎn)信息*/

ArcNode*firstarc;/*指向第一條弧*/}VNode;typedefVNodeAdjList[MAXV]; /*AdjList是鄰接表類型*/typedefstruct{AdjListadjlist; /*鄰接表*/

intn,e; /*圖中頂點(diǎn)數(shù)n和邊數(shù)e*/}ALGraph; /*圖的類型*/鄰接表存儲(chǔ)結(jié)構(gòu)的定義36voidDFS(ALGraph*G,intv){ArcNode*p;visited[v]=1; /*置已訪問標(biāo)記*/

printf("%d",v); /*輸出被訪問頂點(diǎn)的編號(hào)*/

p=G->adjlist[v].firstarc;

/*p指向頂點(diǎn)v的第一條弧的弧頭結(jié)點(diǎn)*/

while(p!=NULL)

{if(visited[p->adjvex]==0)DFS(G,p->adjvex);

/*若p->adjvex頂點(diǎn)未訪問,遞歸訪問它*/

p=p->nextarc;

/*p指向頂點(diǎn)v的下一條弧的弧頭結(jié)點(diǎn)*/

}}v是初始頂點(diǎn)編號(hào)，visited[]是一個(gè)全局?jǐn)?shù)組，初始時(shí)所有元素均為0表示所有頂點(diǎn)尚未訪問過37圖的深度優(yōu)先遍歷intvisited[MAXNODE]//訪問標(biāo)志數(shù)組voidDFSTraverse(ALGraphG){for(i=0；i<G->n；i++)visited[i]=0；

for(i=0；i<G->n；i++)

if(visited[i]==0)DFS(G,i)；}//DFSTraverseDFS的調(diào)用次數(shù)即為連通分量的個(gè)數(shù)381、訪問初始點(diǎn)vi2、接著訪問vi的所有未被訪問過的鄰接點(diǎn)v1,v2,…,vt3、然后再按照v1,v2,…,vt的次序，訪問每一個(gè)頂點(diǎn)的所有未被訪問過的鄰接點(diǎn)依次類推，直到圖中所有和初始點(diǎn)vi有路徑相通的頂點(diǎn)都被訪問過為止。8.3.3廣度優(yōu)先遍歷39圖的廣度優(yōu)先遍歷v2v4v1v5v3v6v7v8廣度優(yōu)先搜索v1->v2->v3->v4->v5->v6->v7->v8v2v4v1v5v3v6v7v8回邊40圖的廣度優(yōu)先遍歷已知圖G的鄰接表如圖所示，其從頂點(diǎn)V1出發(fā)的廣度優(yōu)先搜索序列為____________。V6∧V1143V2V3V4V5245352∧∧∧∧∧012345V6∧v1v2v5v4v3v641voidBFS(ALGraph*G,intv){ArcNode*p;intw,i;intqueue[MAXV],front=0,rear=0; /*定義循環(huán)隊(duì)列*/

intvisited[MAXV];/*定義存放結(jié)點(diǎn)的訪問標(biāo)志的數(shù)組*/

for(i=0;i<G->n;i++)visited[i]=0;/*訪問標(biāo)志數(shù)組初始化*/

printf("%2d",v);/*輸出被訪問頂點(diǎn)的編號(hào)*/

visited[v]=1;/*置已訪問標(biāo)記*/

rear=(rear+1)%MAXV;

queue[rear]=v; /*v進(jìn)隊(duì)*/

while(front!=rear) /*若隊(duì)列不空時(shí)循環(huán)*/

{front=(front+1)%MAXV;

w=queue[front];/*出隊(duì)并賦給w*/

p=G->adjlist[w].firstarc;/*找w的第一個(gè)鄰接點(diǎn)*/

while(p!=NULL)

{ if(visited[p->adjvex]==0)

{ printf(“%2d”,p->adjvex); /*訪問之*/

visited[p->adjvex]=1;

rear=(rear+1)%MAXV;/*該頂點(diǎn)進(jìn)隊(duì)*/

queue[rear]=p->adjvex;

}

p=p->nextarc;/*找下一個(gè)鄰接頂點(diǎn)*/

}

}

printf("\n");}42思考題1對(duì)一個(gè)圖進(jìn)行遍歷為什么可以得到不同的遍歷序列？主要因素有：開始遍歷的頂點(diǎn)不同；鄰接點(diǎn)的順序不同；43思考題2遍歷圖的過程實(shí)質(zhì)上是______，breath-firstsearch和depth-firstsearch的不同之處在于______，反映在數(shù)據(jù)結(jié)構(gòu)上的差別是______。（1）：查找頂點(diǎn)的鄰接點(diǎn)的過程；（2）：訪問頂點(diǎn)的順序不同；（3）：隊(duì)列和棧448.3.4非連通圖的遍歷（略）在對(duì)無向圖進(jìn)行遍歷時(shí)：對(duì)于連通圖，僅需調(diào)用遍歷過程(DFS或BFS)一次，從圖中任一頂點(diǎn)出發(fā)，便可以遍歷圖中的各個(gè)頂點(diǎn)。對(duì)于非連通圖，則需多次調(diào)用遍歷過程，每次調(diào)用得到的頂點(diǎn)集連同相關(guān)的邊就構(gòu)成圖的一個(gè)連通分量。調(diào)用兩次DFS（分別從A、D出發(fā)），得到的頂點(diǎn)訪問序列分別為：

A,B,CD,E,F

ACBDEFDEFBCA45確定連通分量的個(gè)數(shù)number=0;for(i=0；i<G->n;i++)

if(visited[i]==0)

{

++number;

DFS(G,i)；

}468.4.1生成樹的概念

一個(gè)連通圖的生成樹是一個(gè)極小連通子圖，它含有圖中全部頂點(diǎn)，但只有構(gòu)成一棵樹的n-1條邊。如果一個(gè)圖有n個(gè)頂點(diǎn)和小于(n-1)條邊，則是非連通圖。如果它多于n-1條邊，則一定有回路。生成樹的構(gòu)成：設(shè)G=(V,E)為連通圖，則從圖中任一頂點(diǎn)出發(fā)遍歷圖時(shí)，必定將E(G)分成兩個(gè)集合T和B，其中T是遍歷圖過程中走過的邊的集合，B是剩余的邊的集合。G‘=(V,T)是G的極小連通子圖，即G'是G的一棵生成樹。

8.4生成樹和最小生成樹47深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹；由廣度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹。8.4.2無向圖的連通分量和生成樹生成樹不唯一v3v2v1v4v3v2v1v4v3v2v4v1例8.1148最小生成樹圖的最小生成樹：圖的所有生成樹中，邊上的權(quán)值之和最小的樹。實(shí)際問題：假設(shè)要在n個(gè)城市之間建立通信網(wǎng)絡(luò)。則連通這n個(gè)城市只需要n-1條通信線路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通訊網(wǎng)？該問題等價(jià)于：在含有n個(gè)頂點(diǎn)的連通圖的所有生成樹中，選擇一棵，使得各邊權(quán)值之和最小。49假設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無向圖，T=(U,TE)是G的最小生成樹。由G構(gòu)造最小生成樹T的步驟如下：(1)初始化U={v}，以v到其他頂點(diǎn)的所有邊為候選邊；(2)重復(fù)以下步驟n-1次,使得其他n-1個(gè)頂點(diǎn)被加入到U中：①?gòu)暮蜻x邊中挑選權(quán)值最小的邊加入TE，設(shè)該邊在V-U中的頂點(diǎn)是vk，將vk加入U(xiǎn)中；②考察當(dāng)前V-U中的所有頂點(diǎn)vj，修改候選邊：若(vk,vj)的權(quán)值小于原來和vj關(guān)聯(lián)的候選邊，則用(vk,vj)取代后者作為候選邊。8.4.3普里姆算法50Prim算法的實(shí)現(xiàn)設(shè)立輔助數(shù)組closedge，對(duì)每個(gè)頂點(diǎn)，存在一個(gè)相應(yīng)分量，記錄從U到vi的所有邊中代價(jià)最小的邊。數(shù)組closedge包括兩個(gè)域：lowcost域存放該邊上的權(quán)adjvex域存放該邊依附的在U中的頂點(diǎn)顯然：（其中表示賦予邊的權(quán)）51Prim算法舉例5

0

2

1

3

4

5

(a)

1

5

6

3

5

6

6

4

2

0

2

1

3

4

5

(b)

1

0

2

1

3

4

5

(c)

1

4

0

2

1

3

4

5

(d)

1

4

2

0

2

1

3

4

5

(e)

1

5

4

2

0

2

1

3

4

5

(f)

1

3

4

2

5

52Prim算法舉例Adjvexlowcost

0

0

0

0

0{0,1,2,3,4,5}{}

closedge

12

3

4

5U

V－UAdjvexlowcost060105∞∞{0}{1,2,3,4,5}Adjvexlowcost250052624{0,2}{1,3,4,5}Adjvexlowcost25

052260{0,2,5}{1,3,4}Adjvexlowcost25

0

0260{0,2,3,5}{1,4}Adjvexlowcost

0

0

013

0{0,1,2,3,5}{4}i

53克魯斯卡爾(Kruskal)算法是一種按權(quán)值的遞增次序選擇合適的邊來構(gòu)造最小生成樹的方法。假設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無向圖，T=(U,TE)是G的最小生成樹，則構(gòu)造最小生成樹的步驟如下：(1)置U的初值等于V(即包含有G中的全部頂點(diǎn))，TE的初值為空集(即圖T中每一個(gè)頂點(diǎn)都構(gòu)成一個(gè)分量)。(2)將圖G中的邊按權(quán)值從小到大的順序依次選?。喝暨x取的邊未使生成樹T形成回路，則加入TE；否則舍棄，直到TE中包含(n-1)條邊為止。8.4.4克魯斯卡爾算法54克魯斯卡爾算法舉例5

0

2

1

3

4

5

1

5

6

3

5

6

6

4

2

(e)

4

1

0

2

1

3

4

5

(a)

1

0

2

1

3

4

5

(b)

1

0

2

1

3

4

5

(c)

1

0

2

1

3

4

5

(d)

1

4

2

(e)

0

2

1

3

4

5

1

3

4

2

5

2

2

3

3

0

0

3

5

4

1

0

0

3

3

1

1

0

0

3

3

1

1

0

0

0

0

1

1

1

1

1

1

558.5.1路徑的概念

在一個(gè)無權(quán)的圖中，若從一頂點(diǎn)到另一頂點(diǎn)存在著一條路徑，則稱該路徑長(zhǎng)度為該路徑上所經(jīng)過的邊的數(shù)目，它等于該路徑上的頂點(diǎn)數(shù)減1。由于從一頂點(diǎn)到另一頂點(diǎn)可能存在著多條路徑,每條路徑上所經(jīng)過的邊數(shù)可能不同，即路徑長(zhǎng)度不同，我們把路徑長(zhǎng)度最短(即經(jīng)過的邊數(shù)最少)的那條路徑叫做最短路徑，其路徑長(zhǎng)度叫做最短路徑長(zhǎng)度或最短距離。8.5最短路徑（略）56

對(duì)于帶權(quán)的圖，考慮路徑上各邊上的權(quán)值，則通常把一條路徑上所經(jīng)邊的權(quán)值之和定義為該路徑的路徑長(zhǎng)度或稱帶權(quán)路徑長(zhǎng)度。從源點(diǎn)到終點(diǎn)可能不止一條路徑，把帶權(quán)路徑長(zhǎng)度最短的那條路徑稱為最短路徑，其路徑長(zhǎng)度(權(quán)值之和)稱為最短路徑長(zhǎng)度或者最短距離。57問題：給定一個(gè)帶權(quán)有向圖G與源點(diǎn)v，求從v到G中其他頂點(diǎn)的最短路徑，并限定各邊上的權(quán)值大于或等于0。8.5.2從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑采用狄克斯特拉(Dijkstra)算法求解基本思想是：按最短路徑長(zhǎng)度遞增的次序產(chǎn)生每條最短路徑源點(diǎn)v1…v258源點(diǎn)v1…v2從源點(diǎn)到頂點(diǎn)v1的最短路徑是所有最短路徑中長(zhǎng)度最短者在這條最短路徑上，必定只包含一條權(quán)值最小的弧，由此，只要在所有從源點(diǎn)出發(fā)的弧中查找權(quán)值最小者即可長(zhǎng)度次短者可能有兩種情況：

1.它可能是從源點(diǎn)直接到該頂點(diǎn)的路徑；

2.也可能是：從源點(diǎn)先到v1，再?gòu)膙1到該頂點(diǎn)；其余依次類推設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖，把圖中頂點(diǎn)集合V分成兩組：第一組為已求出最短路徑的頂點(diǎn)集合S；第二組為其余未確定最短路徑的頂點(diǎn)集合U。59源點(diǎn)v到j(luò)的最小距離＝MIN(cvk+wkj,cvj)60S U dist[]123456{0} {1,2,3,4,5,6}{4,6,6,∞,∞,∞}{0,1}{2,3,4,5,6}{,

5,6,11,∞,∞}{0,1,2}{3,4,5,6} {,,6,11,9,∞}{0,1,2,3}{4,5,6} {,,,11,9,∞}{0,1,2,3,5}{4,6} {,,,10,,17}{0,1,2,3,5,4} {6} {,,,,,16}{0,1,2,3,5,4,6}{} {,,,,,}從源點(diǎn)到vj的最短路徑長(zhǎng)度61

問題：對(duì)于一個(gè)各邊權(quán)值均大于零的有向圖，對(duì)每一對(duì)頂點(diǎn)vi≠vj，求出vi與vj之間的最短路徑和最短路徑長(zhǎng)度。

可以通過以每個(gè)頂點(diǎn)作為源點(diǎn)循環(huán)求出每對(duì)頂點(diǎn)之間的最短路徑。弗洛伊德(Floyd)算法也可用于求兩頂點(diǎn)之間最短路徑。

8.5.3每對(duì)頂點(diǎn)之間的最短路徑62

假設(shè)有向圖G=(V,E)采用鄰接矩陣cost存儲(chǔ)，另外設(shè)置一個(gè)二維數(shù)組A用于存放當(dāng)前頂點(diǎn)之間的最短路徑長(zhǎng)度，分量A[i][j]表示當(dāng)前頂點(diǎn)vi到頂點(diǎn)vj的最短路徑長(zhǎng)度。弗洛伊德算法的基本思想：遞推產(chǎn)生一個(gè)矩陣序列A0,A1,…,Ak,…,An

其中Ak[i][j]表示從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過的頂點(diǎn)編號(hào)不大于k的最短路徑長(zhǎng)度。初始時(shí),有A-1[i][j]=cost[i][j]63

當(dāng)求從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過的頂點(diǎn)編號(hào)不大于k+1的最短路徑長(zhǎng)度時(shí),要分兩種情況考慮：一種情況是該路徑不經(jīng)過頂點(diǎn)編號(hào)為k+1的頂點(diǎn),此時(shí)該路徑長(zhǎng)度與從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過的頂點(diǎn)編號(hào)不大于k的最短路徑長(zhǎng)度相同；另一種情況是從頂點(diǎn)vi到頂點(diǎn)vj的最短路徑上經(jīng)過編號(hào)為k+1的頂點(diǎn)。64Ak+1[i,j]=MIN(Ak[i,j],Ak[i,k+1]+Ak[k+1,j]65

該路徑可分為兩段:

(1)從頂點(diǎn)vi到頂點(diǎn)vk+1的最短路徑;

(2)從頂點(diǎn)vk+1到頂點(diǎn)vj的最短路徑。此時(shí)最短路徑長(zhǎng)度等于這兩段路徑長(zhǎng)度之和。這兩種情況中的較小值，就是所要求的從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過的頂點(diǎn)編號(hào)不大于k+1的最短路徑。

弗洛伊德思想可用如下的表達(dá)式來描述：

A-1[i][j]=cost[i][j]Ak+1[i][j]=MIN{Ak[i][j],Ak[i][k+1]+Ak[k+1][j]

}(0≤k≤n-1)66設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的有向圖，V中頂點(diǎn)序列v1,v2,…,vn稱為一個(gè)拓?fù)湫蛄?，?dāng)且僅當(dāng)該頂點(diǎn)序列滿足下列條件：若<vi,vj>是圖中的邊(即從頂點(diǎn)vi到vj有一條路徑)，則在序列中頂點(diǎn)vi必須排在頂點(diǎn)vj之前。在一個(gè)有向圖中找一個(gè)拓?fù)湫蛄械倪^程稱為拓?fù)渑判颉?/p>

對(duì)有向圖進(jìn)行拓?fù)渑判颍蓹z查有向圖中是否存在回路。

8.6拓?fù)渑判?7課程代號(hào)課程名稱先修課程C1高等數(shù)學(xué)無C2程序設(shè)計(jì)無C3離散數(shù)學(xué)C1C4數(shù)據(jù)結(jié)構(gòu)C2,C3C5編譯原理C2,C4C6操作系統(tǒng)C4,C7C7計(jì)算機(jī)組成原理C2

例如，計(jì)算機(jī)專業(yè)的學(xué)生必須完成一系列規(guī)定的基礎(chǔ)課和專業(yè)課才能畢業(yè)。課程之間的先后關(guān)系可用有向圖表示：拓?fù)湫蛄?：C1-C3-C2-C4-C7-C6-C5拓?fù)湫蛄?：C2-C7-C1-C3-C4-C5-C6按照任何一個(gè)拓?fù)湫蛄卸伎梢皂樞虻剡M(jìn)行課程學(xué)習(xí)。68

拓?fù)渑判蚍椒ㄈ缦拢?/p>

(1)從有向圖中選擇一個(gè)沒有前驅(qū)(即入度為0)的頂點(diǎn)并且輸出它。

(2)從網(wǎng)中刪去該頂點(diǎn)，并且刪去從該頂點(diǎn)發(fā)出的全部有向邊。

(3)重復(fù)上述兩步，直到剩余的網(wǎng)中不再存在沒有前驅(qū)的頂點(diǎn)為止。若此時(shí)網(wǎng)不空，表明網(wǎng)中有環(huán)。

69abcghdfeabhcdgfe一個(gè)AOV-網(wǎng)的拓?fù)渑判?0為了實(shí)現(xiàn)拓?fù)渑判虻乃惴?，?duì)于給定的有向圖，采用鄰接表作為存儲(chǔ)結(jié)構(gòu)，為每個(gè)頂點(diǎn)設(shè)立一個(gè)鏈表，每個(gè)鏈表有一個(gè)表頭結(jié)點(diǎn)，表頭結(jié)點(diǎn)中增加一個(gè)存放頂點(diǎn)入度的域count。即將鄰接表定義中的VNode類型修改如下：

typedefstruct /*表頭結(jié)點(diǎn)類型*/

{Vertexdata; /*頂點(diǎn)信息*/

intcount; /*存放頂點(diǎn)入度*/

ArcNode*firstarc;/*指向第一條弧*/

}VNode;71voidTopSort(ALGragh*G){inti,j;intSt[MAXV],top=-1;/*棧St的指針為top*/

ArcNode*p;

for(i=0;i<G->n;i++)

G->adjlist[i].count=0;

for(i=0;i<G->n;i++)

{ p=G->adjlist[i].firstarc;

while(p!=NULL)

{ G->adjlist[p->adjvex].count++;

p=p->nextarc; }

}

for(i=0;i<G->n;i++)

if(G->adjlist[i].count==0) /*入度為0的頂點(diǎn)入棧*/

{top++;St[top]=i;}

while(top>-1)/*棧不為空時(shí)循環(huán)*/

{i=St[top];top--; /*出棧*/

printf("%d",i);p=G->adjlist[i].firstarc;

while(p!=NULL)

{j=p->adjvex;G->adjlist[j].count--;

if(G->adjlist[j].count==0)

{top++;St[top]=j;}

p=p->nextarc; /*找下一個(gè)相鄰頂點(diǎn)*/

}

}}72用帶權(quán)有向圖描述工程的預(yù)計(jì)進(jìn)度，估算工程完成的時(shí)間。AOE網(wǎng)(ActivityOnEdge)：以頂點(diǎn)表示事件，有向邊表示活動(dòng)，邊e的權(quán)c(e)表示完成活動(dòng)e所需的時(shí)間，或者說活動(dòng)e持續(xù)時(shí)間。8.7AOE網(wǎng)與關(guān)鍵路徑（略）v1

表示工程的開始v2

表示a1活動(dòng)的完成v5表示a4

和a5

的完成v8

表示a8

和a9

的完成v9

表示工程的結(jié)束事件解釋每個(gè)事件給出某些活動(dòng)完成的信號(hào)，即表示在它之前的活動(dòng)已經(jīng)完成，在它之后的活動(dòng)可以開始v2v4v1v5v3v6v9v7v8a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4源點(diǎn)匯點(diǎn)73我們對(duì)AOE-網(wǎng)所關(guān)心的問題是:(1)完成整個(gè)工程至少需要多少時(shí)間(2)哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵完成工程的最小時(shí)間：從開始頂點(diǎn)到結(jié)束頂點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度。關(guān)鍵路徑：從開始頂點(diǎn)到結(jié)束頂點(diǎn)的最長(zhǎng)路徑。事件vi能夠發(fā)生的最早時(shí)間是從始點(diǎn)v1到頂點(diǎn)vi的最長(zhǎng)路徑的長(zhǎng)，它決定了表示該事件的這個(gè)頂點(diǎn)發(fā)出去的所有邊（?。┍硎镜幕顒?dòng)的最早開始時(shí)間。我們用e(i)表示活動(dòng)ai的最早開始時(shí)間，用l(i)表示活動(dòng)ai的最遲開始時(shí)間。識(shí)別關(guān)鍵活動(dòng)就是要找e(i)=l(i)的活動(dòng)。

74e(i)和l(i)分別表示活動(dòng)ai的最早和最遲開始時(shí)間，ve(j)和vl(j)分別表示事件vj的最早和最遲發(fā)生時(shí)間如果活動(dòng)ai由弧<j,k>表示，其權(quán)記為c(<j,k>)，則活動(dòng)開始時(shí)間的計(jì)算公式為：

e(i)=ve(j) l(i)=vl(k)-c(<j,k>)

事件發(fā)生時(shí)間的計(jì)算公式為：

(1)最早時(shí)間

ve(源點(diǎn))=0

ve(j)=max{ve(i)+c(<i,j>)}<i,j>∈T，j=1,2,……,n

其中，T是所有以第j個(gè)頂點(diǎn)為頭的弧的集合。

(2)最遲時(shí)間

vl(匯點(diǎn))=ve(匯點(diǎn))

vl(i)=min{vl(j)－c(<i,j>)}<i,j>∈S，i=n-1,……,1其中，S是所有以第i個(gè)頂點(diǎn)為尾的弧的集合。jkaii1ji2...ij2j1...75關(guān)鍵路徑---求ve，向前推ve(1)=0ve(2)=6ve(3)=4ve(4)=5ve(5)=maxv2v4v1v5v3v6v9v7v8a1=6a2=4a3=5a4=1a5=