《數(shù)據(jù)結(jié)構(gòu)（C++版）（第二版）》課件第07章

2023年11月28日1第7章圖本章學(xué)習(xí)內(nèi)容

7.1圖的基本概念7.2圖的存儲(chǔ)結(jié)構(gòu)7.3圖的遍歷7.4生成樹(shù)和最小生成樹(shù)7.5最短路徑7.6有向無(wú)環(huán)圖及其應(yīng)用2023年11月28日27.1.1圖的定義7.1圖的基本概念圖是由頂點(diǎn)集V和頂點(diǎn)間的關(guān)系集合E（邊的集合）組成的一種數(shù)據(jù)結(jié)構(gòu)，可以用二元組定義為：G=(V,E)。例如，對(duì)于圖7-1所示的無(wú)向圖G1和有向圖G2，它們的數(shù)據(jù)結(jié)構(gòu)可以描述為：G1=(V1,E1)，其中V1={a,b,c,d}，E1={(a,b)(a,c),(a,d),(b,d),(c,d)}，而G2=(V2,E2)，其中V2={1,2,3}，E2={<1,2>,<1,3>,<2,3>,<3,1>}。

（a）無(wú)向圖G1（b）有向圖G2

圖7-1無(wú)向圖和有向圖2023年11月28日37.1.2圖的基本術(shù)語(yǔ)1．有向圖和無(wú)向圖在圖中，若用箭頭標(biāo)明了邊是有方向性的，則稱這樣的圖為有向圖，否則稱為無(wú)向圖。圖7-1中，G1為無(wú)向圖，G2為有向圖。在無(wú)向圖中，一條邊（x,y）與（y,x）表示的結(jié)果相同，用圓括號(hào)表示，在有向圖中，一條邊<x,y>與<y,x>表示的結(jié)果不相同，故用尖括號(hào)表示。<x,y>表示從頂點(diǎn)x發(fā)向頂點(diǎn)y的邊，x為始點(diǎn)，y為終點(diǎn)。有向邊也稱為弧，x為弧尾，y為弧頭，則<x,y>表示為一條??；而<y,x>表示y為弧尾，x為弧頭的另一條弧。2023年11月28日42．完全圖、稠密圖、稀疏圖具有n個(gè)頂點(diǎn)，n(n-1)/2條邊的圖，稱為完全無(wú)向圖；具有n個(gè)頂點(diǎn)，n(n-1)條弧的有向圖，稱為完全有向圖。完全無(wú)向圖和完全有向圖都稱為完全圖。對(duì)于一般無(wú)向圖，頂點(diǎn)數(shù)為n，邊數(shù)為e，則0≤e≤n(n-1)/2。對(duì)于一般有向圖，頂點(diǎn)數(shù)為n，弧數(shù)為e，則0≤e≤n(n-1)。當(dāng)一個(gè)圖接近完全圖時(shí)，稱它為稠密圖，相反地，當(dāng)一個(gè)圖中含有較少的邊或弧時(shí)，稱它為稀疏圖。3．度、入度、出度在圖中，一個(gè)頂點(diǎn)依附的邊或弧的數(shù)目，稱為該頂點(diǎn)的度。在有向圖中，一個(gè)頂點(diǎn)依附的弧頭數(shù)目，稱為該頂點(diǎn)的入度；一個(gè)頂點(diǎn)依附的弧尾數(shù)目，稱為該頂點(diǎn)的出度；某個(gè)頂點(diǎn)的入度和出度之和稱為該頂點(diǎn)的度。2023年11月28日5另外，若圖中有n個(gè)頂點(diǎn)，e條邊或弧，第i個(gè)頂點(diǎn)的度為di，則有e=。例如，對(duì)圖7-1，G1中頂點(diǎn)a，b，c，d的度分別為3，2，2，3，G2中頂點(diǎn)1，2，3的出度分別為2，1，1，而它們的入度分別為1，1，2，故頂點(diǎn)1，2，3的度分別為3，2，3。4．子圖若有兩個(gè)圖G1和G2，G1=(V1,E1)，G2=(V2,E2)，滿足如下條件：V2

V1，E2

E1，即V2為V1的子集，E2為E1的子集，稱圖G2為圖G1的子圖。圖和子圖的示例具體見(jiàn)圖7-2。

（a）圖G（b）圖G的兩個(gè)子圖圖7-2圖與子圖示例2023年11月28日65．權(quán)在圖的邊或弧中給出相關(guān)的數(shù)，稱為權(quán)。權(quán)可以代表一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離、耗費(fèi)等，帶權(quán)圖一般稱為網(wǎng)。帶權(quán)圖的示例具體見(jiàn)圖7-3。

（a）無(wú)向網(wǎng)（b）有向網(wǎng)圖7-3無(wú)向帶權(quán)圖和有向帶權(quán)圖2023年11月28日76．連通圖和強(qiáng)連通圖在無(wú)向圖中，若從頂點(diǎn)i到頂點(diǎn)j有路徑，則稱頂點(diǎn)i到頂點(diǎn)j是連通的。若任意兩個(gè)頂點(diǎn)都是連通的，則稱此無(wú)向圖為連通圖，否則稱為非連通圖。連通圖和非連通圖示例見(jiàn)圖7-4。

（a）連通圖（b）非連通圖

圖7-4連通圖和非連通圖2023年11月28日8在有向圖中，若從頂點(diǎn)i到頂點(diǎn)j有路徑，則稱從頂點(diǎn)i到頂點(diǎn)j是連通的，若圖中任意兩個(gè)頂點(diǎn)都是連通的，則稱此有向圖為強(qiáng)連通圖，否則稱為非強(qiáng)連通圖。強(qiáng)連通圖和非強(qiáng)連通圖示例見(jiàn)圖7-5。

（a）強(qiáng)連通圖（b）非強(qiáng)連通圖

圖7-5強(qiáng)連通圖和非強(qiáng)連通圖2023年11月28日97．連通分量和強(qiáng)連通分量無(wú)向圖中，極大的連通子圖為該圖的連通分量。顯然，任何連通圖的連通分量只有一個(gè)，即它本身，而非連通圖有多個(gè)連通分量。對(duì)于圖7-4中的非連通圖，它的連通分量見(jiàn)圖7-6。

圖7-6圖7-4（b）的連通分量2023年11月28日10有向圖中，極大的強(qiáng)連通子圖為該圖的強(qiáng)連通分量。顯然，任何強(qiáng)連通圖的強(qiáng)連通分量只有一個(gè)，即它本身，而非強(qiáng)連通圖有多個(gè)強(qiáng)連通分量。對(duì)于圖7-5中的非強(qiáng)連通圖，它的強(qiáng)連通分量見(jiàn)圖7-7。

圖7-7圖7-5（b）的強(qiáng)連通分量2023年11月28日118．路徑、回路在無(wú)向圖G中，若存在一個(gè)頂點(diǎn)序列Vp，Vi1，Vi2，…，Vin，Vq,使得(Vp,Vi1)，(Vi1,Vi2)，…，(Vin,Vq)均屬于E(G)，則稱頂點(diǎn)Vp到Vq存在一條路徑。若一條路徑上除起點(diǎn)和終點(diǎn)可以相同外，其余頂點(diǎn)均不相同，則稱此路徑為簡(jiǎn)單路徑。起點(diǎn)和終點(diǎn)相同的路徑稱為回路，簡(jiǎn)單路徑組成的回路稱為簡(jiǎn)單回路。路徑上經(jīng)過(guò)的邊的數(shù)目稱為該路徑的路徑長(zhǎng)度。9．有根圖在一個(gè)有向圖中，若從頂點(diǎn)V有路徑可以到達(dá)圖中的其他所有頂點(diǎn)，則稱此有向圖為有根圖，頂點(diǎn)V稱做圖的根。10．生成樹(shù)、生成森林連通圖的生成樹(shù)是一個(gè)極小連通子圖，它包含圖中全部n個(gè)頂點(diǎn)和n-1條不構(gòu)成回路的邊。非連通圖的生成樹(shù)則組成一個(gè)生成森林。若圖中有n個(gè)頂點(diǎn)，m個(gè)連通分量，則生成森林中有n-m條邊。2023年11月28日127.2圖的存儲(chǔ)結(jié)構(gòu)

由于圖是一種多對(duì)多的非線性關(guān)系，因此，無(wú)法用數(shù)據(jù)元素在存儲(chǔ)區(qū)中的物理位置來(lái)表示元素之間的關(guān)系，故不能用順序存儲(chǔ)結(jié)構(gòu)。下面將介紹常用的三種存儲(chǔ)結(jié)構(gòu)：鄰接矩陣、鄰接表和鄰接多重表。7.2.1鄰接矩陣1．圖的鄰接矩陣表示在鄰接矩陣表示中，除了存放頂點(diǎn)本身的信息外，還用一個(gè)矩陣表示各個(gè)頂點(diǎn)之間的關(guān)系。若(i,j)∈E(G)或〈i,j〉∈E(G)，則矩陣中第i行第j列元素值為1，否則為0。圖的鄰接矩陣定義為：1 若(i,j)∈E(G)或〈i,j〉∈E(G)A[i][j]=0 其他情形2023年11月28日13例如，對(duì)圖7-8所示的無(wú)向圖和有向圖，它們的鄰接矩陣見(jiàn)圖7-9。（a）無(wú)向圖G3（b）有向圖G4

圖7-8無(wú)向圖G3及有向圖G4（a）G3的鄰接矩陣（b）G4的鄰接矩陣圖7-9鄰接矩陣表示2023年11月28日142．從無(wú)向圖的鄰接矩陣可以得出如下結(jié)論（1）矩陣是對(duì)稱的；（2）第i行或第i列1的個(gè)數(shù)為頂點(diǎn)i的度；（3）矩陣中1的個(gè)數(shù)的一半為圖中邊的數(shù)目；（4）很容易判斷頂點(diǎn)i和頂點(diǎn)j之間是否有邊相連（看矩陣中i行j列值是否為1）。3．從有向圖的鄰接矩陣可以得出如下結(jié)論（1）矩陣不一定是對(duì)稱的；（2）第i行中1的個(gè)數(shù)為頂點(diǎn)i的出度；（3）第j列中1的個(gè)數(shù)為頂點(diǎn)j的入度；（4）矩陣中1的個(gè)數(shù)為圖中弧的數(shù)目；（5）很容易判斷頂點(diǎn)i和頂點(diǎn)j是否有弧相連。2023年11月28日154．網(wǎng)的鄰接矩陣表示類似地可以定義網(wǎng)的鄰接矩陣為：wij

若(i,j)∈E(G)或〈i,j〉∈E(G)A[i][j]=0 若i=j∞ 其他情形網(wǎng)及網(wǎng)的鄰接矩陣見(jiàn)圖7-10。

（a）網(wǎng)G5（b）網(wǎng)G5的鄰接矩陣示意圖圖7-10網(wǎng)及鄰接矩陣示意圖2023年11月28日165．圖的鄰接矩陣數(shù)據(jù)類型描述圖的鄰接矩陣數(shù)據(jù)類型描述如下:constintn=maxn； //圖中頂點(diǎn)數(shù)constinte=maxe； //圖中邊數(shù)classgraph{public:elemtypev[n+1]; //存放頂點(diǎn)信息v1,v2,…,vn，不使用v[0]存儲(chǔ)空間intarcs[n+1][n+1] //鄰接矩陣

…… //成員函數(shù)說(shuō)明及定義};2023年11月28日176．建立無(wú)向圖的鄰接矩陣voidgraph::creatadj(graph&g){inti,j,k;for(k=1;k<=n;k++)cin>>g.v[k]; //輸入頂點(diǎn)信息for(i=1;i<=n;i++)for(j=1;j<=n;j++)g.arcs[i][j]=0; //矩陣的初值為0for(k=1;k<=e;k++){cin>>i>>j; //輸入一條邊(i,j)g.arcs[i][j]=1;g.arcs[j][i]=1;}}該算法的時(shí)間復(fù)雜度為O(n2)。2023年11月28日187．建立有向圖的鄰接矩陣voidgraph::creatadj(graph&g){inti,j,k;for(k=1;k<=n;k++)cin>>g.v[k]; //輸入頂點(diǎn)信息for(i=1;i<=n;i++)for(j=1;j<=n;j++)g.arcs[i][j]=0;for(k=1;k<=e;k++){cin>>i>>j; //輸入一條弧<i,j>g.arcs[i][j]=1;}}該算法的時(shí)間復(fù)雜度為O(n2)。2023年11月28日198．建立無(wú)向網(wǎng)的鄰接矩陣voidgraph::creatadj(graph&g){inti,j,k;floatw;for(k=1;k<=n;k++)cin>>g.v[k]; //輸入頂點(diǎn)信息for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i==j)g.arcs[i][j]=0;elseg.arcs[i][j]=∞; //∞代表頂點(diǎn)i和頂點(diǎn)j無(wú)邊，上機(jī)時(shí)可以用一個(gè)很大的數(shù)代替for(k=1;k<=e;k++){cin>>i>>j>>w; //輸入一條邊(i,j)及權(quán)值wg.arcs[i][j]=w;g.arcs[j][i]=w;}}該算法的時(shí)間復(fù)雜度為O(n2)。2023年11月28日209．建立有向網(wǎng)的鄰接矩陣voidgraph::creatadj(graph&g){inti,j,k;floatw;for(k=1;k<=n;k++)cin>>g.v[k]; //輸入頂點(diǎn)信息for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i==j)g.arcs[i][j]=0;elseg.arcs[i][j]=∞;for(k=1;k<=e;k++) //輸入e條邊及權(quán)值{cin>>i>>j>>w; //輸入一條弧<i,j>及權(quán)值wg.arcs[i][j]=w;}}該算法的時(shí)間復(fù)雜度為O(n2)。2023年11月28日21若要將得到的鄰接矩陣輸出，可以使用如下的語(yǔ)句段：for(inti=1;i<=n;i++){for(intj=1;j<=n;j++)cout<<g.arcs[i][j]<<"";cout<<endl;}7.2.2鄰接表1．圖的鄰接表表示將每個(gè)結(jié)點(diǎn)的邊用一個(gè)單鏈表鏈接起來(lái)，若干個(gè)結(jié)點(diǎn)可以得到若干個(gè)單鏈表，每個(gè)單鏈表都有一個(gè)頭結(jié)點(diǎn)，為將所有頭結(jié)點(diǎn)聯(lián)系起來(lái)組成一個(gè)整體，所有頭結(jié)點(diǎn)可看成一個(gè)一維數(shù)組，稱這樣的鏈表為鄰接表。2023年11月28日22例如，圖7-8所示的無(wú)向圖G3和有向圖G4的鄰接表如圖7-11所示。（a）無(wú)向圖G3的鄰接表（b）有向圖G4的鄰接表（c）有向圖G4的逆鄰接表

圖7-11鄰接表示例2023年11月28日232．從無(wú)向圖的鄰接表可以得到如下結(jié)論（1）第i個(gè)鏈表中結(jié)點(diǎn)數(shù)目為頂點(diǎn)i的度；（2）所有鏈表中結(jié)點(diǎn)數(shù)目的一半為圖中邊數(shù)；（3）占用的存儲(chǔ)單元數(shù)目為n+2e。3．從有向圖的鄰接表可以得到如下結(jié)論（1）第i個(gè)鏈表中結(jié)點(diǎn)數(shù)目為頂點(diǎn)i的出度；（2）所有鏈表中結(jié)點(diǎn)數(shù)目為圖中弧數(shù)；（3）占用的存儲(chǔ)單元數(shù)目為n+e。從有向圖的鄰接表可知，不能求出頂點(diǎn)的入度。為此，我們必須另外建立有向圖的逆鄰接表，以便求出每一個(gè)頂點(diǎn)的入度。逆鄰接表在圖7-11（c）中已經(jīng)給出，從該圖中可知。有向圖的逆鄰接表與鄰接表類似，只是它是從入度考慮結(jié)點(diǎn)，而不是從出度考慮結(jié)點(diǎn)。2023年11月28日244．圖的鄰接表數(shù)據(jù)類型描述圖的鄰接表數(shù)據(jù)類型描述如下：constintn=maxn； //maxn表示圖中最大頂點(diǎn)數(shù)constinte=maxe； //maxe表示圖中最大邊數(shù)classlink //定義鏈表類型{public:elemtypedata;link*next;};classnode //定義鄰接表的表頭類型{public:linka[n+1];voidcreatlink(node&g);…… //其他成員函數(shù)的說(shuō)明及定義};在本章中，為描述問(wèn)題方便直觀，我們將elemtype類型設(shè)定為int類型，以此代表圖中頂點(diǎn)的序號(hào)。2023年11月28日255．無(wú)向圖的鄰接表建立voidnode::creatlink(node&g){inti,j,k;link*s;for(i=1;i<=n;i++) //建立鄰接表頭結(jié)點(diǎn){g.a[i].data=i;g.a[i].next=NULL;}for(k=1;k<=e;k++){cin>>i>>j; //輸入一條邊(i,j)s=newlink; //申請(qǐng)一個(gè)動(dòng)態(tài)存儲(chǔ)單元s->data=j;s->next=g.a[i].next; //頭插法建立鏈表g.a[i].next=s;s=newlink;s->data=i;s->next=g.a[j].next;g.a[j].next=s;}}該算法的時(shí)間復(fù)雜度為O(n+e)。2023年11月28日266．有向圖的鄰接表建立voidnode::creatlink(node&g){inti,j,k;link*s;for(i=1;i<=n;i++) //建立鄰接表頭結(jié)點(diǎn){g.a[i].data=i;g.a[i].next=NULL;}for(k=1;k<=e;k++){cin>>i>>j; //輸入一條邊(i,j)s=newlink; //申請(qǐng)一個(gè)動(dòng)態(tài)存儲(chǔ)單元s->data=j;s->next=g.a[i].next;g.a[i].next=s;}}該算法的時(shí)間復(fù)雜度為O(n+e)。2023年11月28日277．網(wǎng)的鄰接表的數(shù)據(jù)類型描述網(wǎng)的鄰接表的數(shù)據(jù)類型可描述如下：constintn=maxn； //maxn表示網(wǎng)中最大頂點(diǎn)數(shù)constinte=maxe； //maxe表示網(wǎng)中最大邊數(shù)classlink //定義鏈表類型{public:elemtypedata;floatw; //定義網(wǎng)上的權(quán)值類型為浮點(diǎn)型

link*next;};classnode //定義鄰接表的表頭類型{public:linka[n+1];voidcreatlink(node&g);};2023年11月28日288．無(wú)向網(wǎng)的鄰接表建立voidnode::creatlink(node&g){floatw;inti,j,k;link*s;for(i=1;i<=n;i++) //建立鄰接表頭結(jié)點(diǎn){g.a[i].data=i;g.a[i].w=0;g.a[i].next=NULL;}for(k=1;k<=e;k++){cin>>i>>j>>w; //輸入一條邊(i,j)及該邊上的權(quán)值s=newlink; //申請(qǐng)一個(gè)動(dòng)態(tài)存儲(chǔ)單元s–>data=j;s->w=w;s->next=g.a[i].next;g.a[i].next=s;s=newlink;s->data=i;s->w=w;s->next=g.a[j].next;g.a[j].next=s;}}該算法的時(shí)間復(fù)雜度為O(n+e)。2023年11月28日299．有向網(wǎng)的鄰接表建立voidnode::creatlink(node&g){floatw;inti,j,k;link*s;for(i=1;i<=n;i++) //建立鄰接表頭結(jié)點(diǎn){g.a[i].data=i;g.a[i].next=NULL;}for(k=1;k<=e;k++){cin>>i>>j>>w; //輸入一條邊(i,j)及該邊上的權(quán)值s=newlink; //申請(qǐng)一個(gè)動(dòng)態(tài)存儲(chǔ)單元s–>data=j;s->w=w;s->next=g.a[i].next;g.a[i].next=s;}}該算法的時(shí)間復(fù)雜度為O(n+e)。2023年11月28日30另外，請(qǐng)注意上面的算法中，建立的鄰接表不是惟一的，與你從鍵盤輸入邊的順序有關(guān)，輸入邊的順序不同，得到的鏈表也不同。若要將得到的鄰接表輸出，可以使用如下的語(yǔ)句：for(inti=1;i<=n;i++){link*p=g.a[i].next;cout<<i<<"->";while(p->next!=NULL) {cout<<p->data<<"->"; p=p->next; } cout<<p->data<<endl; }2023年11月28日317.2.3鄰接多重表在無(wú)向圖的鄰接表中，每條邊(Vi,Vj)由兩個(gè)結(jié)點(diǎn)表示，一個(gè)結(jié)點(diǎn)在第i個(gè)鏈表中，另一個(gè)結(jié)點(diǎn)在第j個(gè)鏈表中，當(dāng)需要對(duì)邊進(jìn)行操作時(shí)，就需要找到表示同一條邊的兩個(gè)結(jié)點(diǎn)，這給操作帶來(lái)不便，在這種情況下采用鄰接多重表比較方便。在鄰接多重表中，每條邊用一個(gè)結(jié)點(diǎn)表示，每個(gè)結(jié)點(diǎn)由五個(gè)域組成，其結(jié)點(diǎn)結(jié)構(gòu)為：其中Mark為標(biāo)志域，用來(lái)標(biāo)記這條邊是否被訪問(wèn)過(guò)，i和j域?yàn)橐粭l邊的兩個(gè)頂點(diǎn)，next1和next2為兩個(gè)指針域，分別指向依附于i頂點(diǎn)的下一條邊和j頂點(diǎn)的下一條邊。而表頭與鄰接表的表頭類似。2023年11月28日32鄰接多重表的形式見(jiàn)圖7-12。（a）無(wú)向圖G6（b）G6的鄰接多重表圖7-12鄰接多重表示例2023年11月28日337.3圖的遍歷和樹(shù)的遍歷類似，圖的遍歷也是從某個(gè)頂點(diǎn)出發(fā)，沿著某條搜索路徑對(duì)圖中所有頂點(diǎn)各作一次訪問(wèn)。若給定的圖是連通圖，則從圖中任一頂點(diǎn)出發(fā)順著邊可以訪問(wèn)到該圖中所有的頂點(diǎn)，但是，在圖中有回路，從圖中某一頂點(diǎn)出發(fā)訪問(wèn)圖中其他頂點(diǎn)時(shí)，可能又會(huì)回到出發(fā)點(diǎn)，而圖中可能還剩余有頂點(diǎn)沒(méi)有訪問(wèn)到，因此，圖的遍歷較樹(shù)的遍歷更復(fù)雜。我們可以設(shè)置一個(gè)全局型標(biāo)志數(shù)組visited來(lái)標(biāo)志某個(gè)頂點(diǎn)是否被訪過(guò)，未訪問(wèn)的值為false，訪問(wèn)過(guò)的值為true。根據(jù)搜索路徑的方向不同，圖的遍歷有兩種方法：深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。2023年11月28日347.3.1深度優(yōu)先搜索遍歷1．深度優(yōu)先搜索思想深度優(yōu)先搜索遍歷類似于樹(shù)的先序遍歷。假定給定圖G的初態(tài)是所有頂點(diǎn)均未被訪問(wèn)過(guò)，在G中任選一個(gè)頂點(diǎn)i作為遍歷的初始點(diǎn)，則深度優(yōu)先搜索遍歷可定義如下：（1）首先訪問(wèn)頂點(diǎn)i，并將其訪問(wèn)標(biāo)記置為訪問(wèn)過(guò)，即visited[i]=true；（2）然后搜索與頂點(diǎn)i有邊相連的下一個(gè)頂點(diǎn)j，若j未被訪問(wèn)過(guò)，則訪問(wèn)它，并將j的訪問(wèn)標(biāo)記置為訪問(wèn)過(guò)，visited[j]=true，然后從j開(kāi)始重復(fù)此過(guò)程，若j已訪問(wèn)，再看與i有邊相連的其他頂點(diǎn)；（3）若與i有邊相連的頂點(diǎn)都被訪問(wèn)過(guò)，則退回到前一個(gè)訪問(wèn)頂點(diǎn)并重復(fù)剛才的過(guò)程，直到圖中所有頂點(diǎn)都被訪問(wèn)完為止。2023年11月28日35例如，對(duì)圖7-13所示的無(wú)向圖G7，從頂點(diǎn)1出發(fā)的深度優(yōu)先搜索遍歷序列可有多種，下面僅給出其中三種，其他可作類似分析寫出來(lái)。圖7-13無(wú)向圖G7在無(wú)向圖G7中，從頂點(diǎn)1出發(fā)的深度優(yōu)先搜索遍歷序列（列舉三種）為：1,2,4,8,5,6,3,71,2,5,8,4,7,3,61,3,6,8,7,4,2,52023年11月28日362．連通圖的深度優(yōu)先搜索若圖是連通的或強(qiáng)連通的，則從圖中某一個(gè)頂點(diǎn)出發(fā)可以訪問(wèn)到圖中所有頂點(diǎn)，否則只能訪問(wèn)到一部分頂點(diǎn)。另外，從剛才寫出的遍歷結(jié)果可以看出，從某一個(gè)頂點(diǎn)出發(fā)的遍歷結(jié)果是不惟一的。但是若我們給定圖的存儲(chǔ)結(jié)構(gòu)，則從某一頂點(diǎn)出發(fā)的遍歷結(jié)果應(yīng)是惟一的。（1）用鄰接矩陣實(shí)現(xiàn)圖的深度優(yōu)先搜索以圖7-13中無(wú)向圖G7為例，來(lái)說(shuō)明算法的實(shí)現(xiàn)，G7的鄰接矩陣見(jiàn)圖7-14。圖7-14無(wú)向圖G7的鄰接矩陣2023年11月28日37算法描述如下：#include<iostream.h>#defineelemtypeintconstintn=8; //圖中頂點(diǎn)數(shù)constinte=10; //圖中邊數(shù)boolvisited[n+1];classgraph{public:elemtypev[n+1]; //存放頂點(diǎn)信息v1,v2,…,vn，不使用v[0]存儲(chǔ)空間intarcs[n+1][n+1]; //鄰接矩陣voidcreatadj(graph&g); //建立鄰接矩陣voiddfs(graphg,inti); //實(shí)現(xiàn)深度優(yōu)先搜索遍歷};2023年11月28日38voidgraph::creatadj(graph&g) //建立鄰接矩陣{inti,j,k;for(k=1;k<=n;k++)cin>>g.v[k]; //輸入頂點(diǎn)信息for(i=1;i<=n;i++)for(j=1;j<=n;j++)g.arcs[i][j]=0;for(k=1;k<=e;k++){cin>>i>>j; //輸入一條邊(i,j)g.arcs[i][j]=1;g.arcs[j][i]=1;}}2023年11月28日39voidgraph::dfs(graphg,inti) //從頂點(diǎn)i出發(fā)實(shí)現(xiàn)深度優(yōu)先搜索遍歷

{intj;cout<<g.v[i]; //輸出訪問(wèn)頂點(diǎn)

visited[i]=true; //全局?jǐn)?shù)組訪問(wèn)標(biāo)記置1表示已經(jīng)訪問(wèn)

for(j=1;j<=n;j++)if((g.arcs[i][j]==1)&&(!visited[j]))dfs(g,j);}voidmain(){graphg;g.creatadj(g);for(i=1;i<=n;i++)visited[i]=false;g.dfs(g,1); //從頂點(diǎn)1出發(fā)訪問(wèn)}2023年11月28日40用上述算法和無(wú)向圖G7，可以描述從頂點(diǎn)1出發(fā)的深度優(yōu)先搜索遍歷過(guò)程，示意圖見(jiàn)圖7-15，其中實(shí)線表示下一層遞歸調(diào)用，虛線表示遞歸調(diào)用的返回。圖7-15鄰接矩陣深度優(yōu)先搜索示意圖從圖7-15中，可以得到從頂點(diǎn)1的遍歷結(jié)果為1,2,4,8,5,6,3,7。同樣可以分析出從其他頂點(diǎn)出發(fā)的遍歷結(jié)果。2023年11月28日41（2）用鄰接表實(shí)現(xiàn)圖的深度優(yōu)先搜索仍以圖7-13中無(wú)向圖G7為例，來(lái)說(shuō)明算法的實(shí)現(xiàn)，G7的鄰接表見(jiàn)圖7-16圖7-16G7的鄰接表2023年11月28日42算法描述如下：#include<iostream.h>#defineelemtypeintconstintn=8; //n表示圖中最大頂點(diǎn)數(shù)constinte=10; //e為圖中最大邊數(shù)boolvisited[n+1];classlink //定義鏈表類型{public:elemtypedata;link*next;};2023年11月28日43classnode //定義鄰接表的表頭類型{public:linka[n+1];voidcreatlink(node&g); //建立鄰接表voiddfs1(nodeg,inti); //實(shí)現(xiàn)深度優(yōu)先搜索遍歷};voidnode::creatlink(node&g){inti,j,k;link*s;for(i=1;i<=n;i++) //建立鄰接表頭結(jié)點(diǎn){g.a[i].data=i;g.a[i].next=NULL;}2023年11月28日44for(k=1;k<=e;k++){cin>>i>>j; //輸入一條邊(i,j)s=newlink; //申請(qǐng)一個(gè)動(dòng)態(tài)存儲(chǔ)單元s->data=j;s->next=g.a[i].next;g.a[i].next=s;s=newlink;s->data=i;s->next=g.a[j].next;g.a[j].next=s;}}2023年11月28日45voidnode::dfs1(nodeg,inti){link*p;cout<<g.a[i].data; //輸出訪問(wèn)頂點(diǎn)

visited[i]=true; //全局?jǐn)?shù)組訪問(wèn)標(biāo)記置為1表示已訪問(wèn)

p=g.a[i].next;while(p!=NULL){if(!visited[p->data])dfs1(g,p->data);p=p->next;}}voidmain(){nodeg;g.creatlink(g);for(i=1;i<=n;i++)visited[i]=false;g.dfs1(g,1);//從頂點(diǎn)1訪問(wèn)}2023年11月28日46用剛才的算法及圖7-16，可以描述從頂點(diǎn)7出發(fā)的深度優(yōu)先搜索遍歷示意圖，見(jiàn)圖7-17，其中實(shí)線表示下一層遞歸，虛線表示遞歸返回，箭頭旁邊的數(shù)字表示調(diào)用的步驟。圖7-17鄰接表深度優(yōu)先搜索示意圖于是，從頂點(diǎn)7出發(fā)的深度優(yōu)先搜索遍歷序列，從圖7-17中可得出為7，3，1，2，4，8，5，6。從其他頂點(diǎn)出發(fā)的深度優(yōu)先搜索序列，請(qǐng)讀者自已寫出。2023年11月28日473．非連通圖的深度優(yōu)先搜索若圖是非連通圖或非強(qiáng)連通圖，則從圖中某一個(gè)頂點(diǎn)出發(fā)，不能用深度優(yōu)先搜索訪問(wèn)到圖中所有頂點(diǎn)，而只能訪問(wèn)到一個(gè)連通子圖（即連通分量）或只能訪問(wèn)到一個(gè)強(qiáng)連通子圖（即強(qiáng)連通分量）。這時(shí)，可以在每個(gè)連通分量或每個(gè)強(qiáng)連通分量中都選一個(gè)頂點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，最后將每個(gè)連通分量或每個(gè)強(qiáng)連通分量的遍歷結(jié)果合起來(lái)，則得到整個(gè)非連通圖的遍歷結(jié)果。遍歷算法實(shí)現(xiàn)與連通圖的只有一點(diǎn)不同，即對(duì)所有頂點(diǎn)進(jìn)行循環(huán)，反復(fù)調(diào)用連通圖的深度優(yōu)先搜索遍歷算法即可。具體實(shí)現(xiàn)如下：for(inti=1;i<=n;i++)if(!visited[i])dfs(i);或者為：

for(inti=1;i<=n;i++)if(!visited[i])dfs1(i);2023年11月28日487.3.2廣度優(yōu)先搜索遍歷1．廣度優(yōu)先搜索的思想廣度優(yōu)先搜索遍歷類似于樹(shù)的按層次遍歷。設(shè)圖G的初態(tài)是所有頂點(diǎn)均未訪問(wèn)，在G中任選一頂點(diǎn)i作為初始點(diǎn)，則廣度優(yōu)先搜索的基本思想是：（1）首先訪問(wèn)頂點(diǎn)i，并將其訪問(wèn)標(biāo)志置為已被訪問(wèn)，即visited[i]=true；（2）接著依次訪問(wèn)與頂點(diǎn)i有邊相連的所有頂點(diǎn)W1，W2，…，Wt；（3）然后再按順序訪問(wèn)與W1，W2，…，Wt有邊相連又未曾訪問(wèn)過(guò)的頂點(diǎn)；（4）依此類推，直到圖中所有頂點(diǎn)都被訪問(wèn)完為止。2023年11月28日49例如，對(duì)圖7-13所示的無(wú)向圖G7，從頂點(diǎn)1出發(fā)的廣度優(yōu)先搜索遍歷序列可有多種，下面僅給出其中三種，其他可作類似分析。在無(wú)向圖G7中，從頂點(diǎn)1出發(fā)的廣度優(yōu)先搜索遍歷序列（列舉三種）為：1,2,3,4,5,6,7,81,3,2,7,6,5,4,81,2,3,5,4,7,6,8這對(duì)于連通圖是可以辦到的，但若是非連通圖，則只須對(duì)每個(gè)連通分量都選一頂點(diǎn)作開(kāi)始點(diǎn)，都進(jìn)行廣度優(yōu)先搜索，則可以得到非連通圖的遍歷。2023年11月28日502．連通圖的廣度優(yōu)先搜索（1）用鄰接矩陣實(shí)現(xiàn)圖的廣度優(yōu)先搜索遍歷仍以圖7-13中無(wú)向圖G7及圖7-14所示的鄰接矩陣來(lái)說(shuō)明對(duì)無(wú)向圖G7的遍歷過(guò)程，算法描述如下：#include<iostream.h>#defineelemtypeintconstintn=8; //圖中頂點(diǎn)數(shù)constinte=10; //圖中邊數(shù)boolvisited[n+1];classgraph{public:elemtypev[n+1]; //存放頂點(diǎn)信息v1,v2,…,vn，不使用v[0]存儲(chǔ)空間intarcs[n+1][n+1]; //鄰接矩陣voidcreatadj(graph&g); //建立鄰接矩陣voidbfs(graphg,inti); //實(shí)現(xiàn)圖的廣度優(yōu)先搜索遍歷};2023年11月28日51voidgraph::creatadj(graph&g){inti,j,k;for(k=1;k<=n;k++)cin>>g.v[k]; //輸入頂點(diǎn)信息for(i=1;i<=n;i++)for(j=1;j<=n;j++)g.arcs[i][j]=0;for(k=1;k<=e;k++){cin>>i>>j; //輸入一條邊(i,j)g.arcs[i][j]=1;g.arcs[j][i]=1;}}2023年11月28日52voidgraph::bfs(graphg,inti) //從頂點(diǎn)i出發(fā)實(shí)現(xiàn)圖的廣度優(yōu)先搜索遍歷{intq[n+1]; //q為隊(duì)列

intf,r,j; //f、r分別為隊(duì)列頭、尾指針

f=r=0; //設(shè)置空隊(duì)列

cout<<g.v[i]; //輸出訪問(wèn)頂點(diǎn)

visited[i]=true; //全局?jǐn)?shù)組標(biāo)記置true表示已經(jīng)訪問(wèn)

r++;q[r]=i; //入隊(duì)列

while(f<r){f++;i=q[f]; //出隊(duì)列for(j=1;j<=n;j++)if((g.arcs[i][j]==1)&&(!visited[j])){cout<<g.v[j]<<"";visited[j]=true;r++;q[r]=j;}}}voidmain(){graphg;g.creatadj(g);for(i=1;i<=n;i++)visited[i]=false;g.bfs(g,1); /從頂點(diǎn)1出發(fā)實(shí)現(xiàn)圖的廣度優(yōu)先搜索遍歷}2023年11月28日53（2）用鄰接表實(shí)現(xiàn)圖的廣度優(yōu)先搜索遍歷仍以無(wú)向圖G7及圖7-16所示的鄰接表來(lái)說(shuō)明鄰接表上實(shí)現(xiàn)廣度優(yōu)先搜索遍歷的過(guò)程。具體算法描述如下：#include<iostream.h>#defineelemtypeintconstintn=8; //maxn表示圖中最大頂點(diǎn)數(shù)constinte=10; //maxe表示圖中最大邊數(shù)boolvisited[n+1];classlink //定義鏈表類型{public:elemtypedata;link*next;};classnode //定義鄰接表的表頭類型{public:linka[n+1];voidcreatlink(node&g); //建立鄰接表voidbfs1(nodeg,inti); //實(shí)現(xiàn)圖的廣度優(yōu)先搜索遍歷};2023年11月28日54voidnode::creatlink(node&g){inti,j,k;link*s;for(i=1;i<=n;i++) //建立鄰接表頭結(jié)點(diǎn){g.a[i].data=i;g.a[i].next=NULL;}for(k=1;k<=e;k++){cin>>i>>j; //輸入一條邊(i,j)s=newlink; //申請(qǐng)一個(gè)動(dòng)態(tài)存儲(chǔ)單元s->data=j;s->next=g.a[i].next;g.a[i].next=s;s=newlink;s->data=i;s->next=g.a[j].next;g.a[j].next=s;}}2023年11月28日55voidnode::bfs1(nodeg,inti){intq[n+1]; //定義隊(duì)列

intf,r;link*p; //p為搜索指針

f=r=0;cout<<g.a[i].data;visited[i]=true;r++;q[r]=i; //進(jìn)隊(duì)while(f<r){f++;i=q[f]; //出隊(duì)

p=g.a[i].next;while(p!=NULL){if(!visited[p->data]){cout<<g.a[p->data].data<<“”;visited[p->data]=true;r++;q[r]=p->data;}p=p->next;}}}2023年11月28日56voidmain(){nodeg;g.creatlink(g);for(i=1;i<=n;i++)visited[i]=false;g.bfs1(g,1); //從頂點(diǎn)1出發(fā)實(shí)現(xiàn)圖的廣度優(yōu)先搜索遍歷}根據(jù)該算法及圖7-16，可以得到圖G7的廣度優(yōu)先搜索遍歷序列，若從頂點(diǎn)1出發(fā)，廣度優(yōu)先搜索遍歷序列為：1，2，3，4，5，6，7，8；若從頂點(diǎn)7出發(fā)，廣度優(yōu)先搜索遍歷序列為：7，3，8，1，6，4，5，2；從其他頂點(diǎn)出發(fā)的廣度優(yōu)先搜索遍歷序列，可根據(jù)同樣類似方法分析得到。2023年11月28日573．非連通圖的廣度優(yōu)先搜索若圖是非連通圖或非強(qiáng)連通圖，則從圖中某一個(gè)頂點(diǎn)出發(fā)，不能用廣度優(yōu)先搜索遍歷訪問(wèn)到圖中所有頂點(diǎn)，而只能訪問(wèn)到一個(gè)連通子圖（即連通分量）或只能訪問(wèn)到一個(gè)強(qiáng)連通子圖（即強(qiáng)連通分量）。這時(shí)，可以在每個(gè)連通分量或每個(gè)強(qiáng)連通分量中都選一個(gè)頂點(diǎn)，進(jìn)行廣度優(yōu)先搜索遍歷，最后將每個(gè)連通分量或每個(gè)強(qiáng)連通分量的遍歷結(jié)果合起來(lái)，則得到整個(gè)非連通圖或非強(qiáng)連通圖的廣度優(yōu)先搜索遍歷序列。遍歷算法實(shí)現(xiàn)與連通圖的只有一點(diǎn)不同，即對(duì)所有頂點(diǎn)進(jìn)行循環(huán)，反復(fù)調(diào)用連通圖的廣度優(yōu)先搜索遍歷算法即可。具體可以表示如下：for(inti=1;i<=n;i++)for(inti=1;i<=n;i++)if(!visited[i])或if(!visited[i])g.bfs(g,i);g.bfs1(g,i);2023年11月28日587.4生成樹(shù)和最小生成樹(shù)7.4.1基本概念1．生成樹(shù)在圖論中，常常將樹(shù)定義為一個(gè)無(wú)回路連通圖。例如，圖7-18中的兩個(gè)圖就是無(wú)回路的連通圖。乍一看它似乎不是樹(shù)，但只要選定某個(gè)頂點(diǎn)做根并以樹(shù)根為起點(diǎn)對(duì)每條邊定向，就可以將它們變?yōu)橥ǔ５臉?shù)。圖7-18兩個(gè)無(wú)回路的連通圖2023年11月28日59在一個(gè)連通圖中，有n個(gè)頂點(diǎn)，若存在這樣一個(gè)子圖，含有n個(gè)頂點(diǎn)，n-1條不構(gòu)成回路的邊，則這個(gè)子圖稱為生成樹(shù)，或者定義為：一個(gè)連通圖G的子圖如果是一棵包含G的所有頂點(diǎn)的樹(shù)，則該子圖為圖G的生成樹(shù)。由于n個(gè)頂點(diǎn)的連通圖至少有n-1條邊，而所有包含n-1條邊及n個(gè)頂點(diǎn)的連通圖都是無(wú)回路的樹(shù)，所以生成樹(shù)是連通圖中的極小連通子圖。所謂極小是指邊數(shù)最少。若在生成樹(shù)中去掉任何一條邊，都會(huì)使之變?yōu)榉沁B通圖；若在生成樹(shù)上任意增加一條邊，就會(huì)構(gòu)成回路。那么，對(duì)給定的連通圖，如何求得它的生成樹(shù)呢？回到我們前面提到的圖的遍歷，訪問(wèn)過(guò)圖中一個(gè)頂點(diǎn)后，要訪問(wèn)下一個(gè)頂點(diǎn)，一般要求兩個(gè)頂點(diǎn)有邊相連，即必須經(jīng)過(guò)圖中的一條邊，要遍歷圖中n個(gè)頂點(diǎn)且每個(gè)頂點(diǎn)都只遍歷一次，則必須經(jīng)過(guò)圖中的n-1條邊，這n-1條邊構(gòu)成連通圖的一個(gè)極小連通子圖，所以它是連通圖的生成樹(shù)。由于遍歷結(jié)果可能不惟一，所以得到的生成樹(shù)也是不惟一的。2023年11月28日60要求得生成樹(shù)，可考慮用剛才講過(guò)的深度優(yōu)先搜索遍歷算法及廣度優(yōu)先搜索遍歷算法。對(duì)于深度優(yōu)先搜索算法DFS或DFS1，由DFS(i)遞歸到DFS(j)，中間必經(jīng)過(guò)一條邊(i,j)，因此，只需在DFS(j)調(diào)用前輸出這條邊或保存這條邊，即可求得生成樹(shù)的一條邊，整個(gè)遞歸完成后，則可求得生成樹(shù)的所有邊。對(duì)于廣度優(yōu)先搜索算法BFS或BFS1，若i出隊(duì)，j入隊(duì)，則(i,j)為一條樹(shù)邊。因此，可以在算法的if語(yǔ)句中輸出這條邊，算法完成后，將會(huì)輸出n-1條邊，也可求得生成樹(shù)。由深度優(yōu)先搜索遍歷得到的生成樹(shù)，稱為深度優(yōu)先生成樹(shù)，由廣度優(yōu)先搜索遍歷得到的生成樹(shù)，稱為廣度優(yōu)先生成樹(shù)。2023年11月28日61圖7-13中無(wú)向圖G7的兩種生成樹(shù)如圖7-19所示。

（a）深度優(yōu)先生成樹(shù)（b）廣度優(yōu)先生成樹(shù)圖7-19兩種生成樹(shù)示意圖若一個(gè)圖是強(qiáng)連通的有向圖，同樣可以得到它的生成樹(shù)。生成樹(shù)可以利用連通圖的深度優(yōu)先搜索遍歷或連通圖的廣度優(yōu)先搜索遍歷算法得到。2023年11月28日622．生成森林若一個(gè)圖是非連通圖或非強(qiáng)連通圖，但有若干個(gè)連通分量或若干個(gè)強(qiáng)連通分量，則通過(guò)深度優(yōu)先搜索遍歷或廣度優(yōu)先搜索遍歷，得到的不是生成樹(shù)，而是生成森林。且若非連通圖有n個(gè)頂點(diǎn)、m個(gè)連通分量或強(qiáng)連通分量，則可以遍歷得到m棵生成樹(shù)，合起來(lái)為生成森林，森林中包含n-m條樹(shù)邊。生成森林可以利用非連通圖的深度優(yōu)先搜索遍歷或非連通圖的廣度優(yōu)先搜索遍歷算法得到。3．最小生成樹(shù)在一般情況下，圖中的每條邊若給定了權(quán)值，這時(shí)，我們所關(guān)心的不是生成樹(shù)，而是生成樹(shù)中邊上權(quán)值之和。若生成樹(shù)中每條邊上權(quán)值之和達(dá)到最小，稱為最小生成樹(shù)。下面將介紹求最小生成樹(shù)的兩種方法：普里姆算法和克魯斯卡爾算法。2023年11月28日637.4.2普里姆（prim）算法1．普里姆算法思想下面僅討論無(wú)向網(wǎng)的最小生成樹(shù)問(wèn)題。普里姆算法的思想是：在圖中任取一個(gè)頂點(diǎn)k作為開(kāi)始點(diǎn)，令集合U={k}，集合W=V-U，其中V為圖中所有頂點(diǎn)集合，然后找出：一個(gè)頂點(diǎn)在集合U中，另一個(gè)頂點(diǎn)在集合W中的所有的邊中，權(quán)值最短的一條邊，找到后，將該邊作為最小生成樹(shù)的樹(shù)邊保存起來(lái)，并將該邊頂點(diǎn)全部加入U(xiǎn)集合中，并從W中刪去這些頂點(diǎn)，然后重新調(diào)整U中頂點(diǎn)到W中頂點(diǎn)的距離，使之保持最小，再重復(fù)此過(guò)程，直到W為空集為止。求解過(guò)程參見(jiàn)下面的圖7-20各步驟。2023年11月28日64

（a）無(wú)向網(wǎng)（b）u={1}w={2,3,4,5,6}

（c）u={1,3}w={2,4,5,6}（d）u={1,3,6}w={2,4,5}2023年11月28日65（e）u={1,3,6,4}w={2,5}（f）u={1,3,6,4,2}w={5}（g）u={1,3,6,4,2,5}w={}圖7-20prim算法構(gòu)造最小生成樹(shù)的過(guò)程2023年11月28日662．普里姆算法實(shí)現(xiàn)普里姆算法的算法實(shí)現(xiàn)，可描述如下（假設(shè)網(wǎng)用鄰接矩陣作存儲(chǔ)結(jié)構(gòu)，與圖的鄰接矩陣類似，只是將0變?yōu)椤蓿?變?yōu)閷?duì)應(yīng)邊上權(quán)值，而矩陣中對(duì)角線上的元素值為0，本算法參照的示例為圖7-20（a）中的無(wú)向網(wǎng)）：#include<iostream.h>constintn=6; //定義網(wǎng)中頂點(diǎn)數(shù)constinte=10; //定義網(wǎng)中邊數(shù)

classedgeset //定義一條生成樹(shù)的邊

{public: intfromvex; //邊的起點(diǎn)

intendvex; //邊的終點(diǎn)

intweight; //邊上的權(quán)值

};2023年11月28日67classtree{public:ints[n+1][n+1]; //網(wǎng)的鄰接矩陣edgesetct[n+1]; //最小生成樹(shù)的邊集voidprim(tree&t); //普里姆算法

};voidtree::prim(tree&t){inti,j,k,min,t1,m,w;for(i=1;i<n;i++) //從頂點(diǎn)1出發(fā)求最小生成的樹(shù)邊

{t.ct[i].fromvex=1;t.ct[i].endvex=i+1;t.ct[i].weight=t.s[1][i+1];}2023年11月28日68for(k=2;k<=n;k++){min=32767;m=k-1;for(j=k-1;j<n;j++) //找權(quán)值最小的樹(shù)邊

if(t.ct[j].weight<min){min=t.ct[j].weight;m=j;}edgesettemp=t.ct[k-1];t.ct[k-1]=t.ct[m];t.ct[m]=temp;j=t.ct[k-1].endvex;for(i=k;i<n;i++) //重新修改樹(shù)邊的距離

{t1=t.ct[i].endvex;w=t.s[j][t1];if(w<t.ct[i].weight) /原來(lái)的邊用權(quán)值較小的邊取代

{t.ct[i].weight=w;2023年11月28日69t.ct[i].fromvex=j;}}}}voidmain(){intj,w;treet;for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)if(i==j)t.s[i][j]=0;elset.s[i][j]=32767; //若(i,j)邊上無(wú)權(quán)值，用32767來(lái)代替∞for(intk=1;k<=e;k++) //建立網(wǎng)的鄰接矩陣{cout<<"請(qǐng)輸入一條邊及邊上的權(quán)值";cin>>i>>j>>w;cout<<endl;t.s[i][j]=w;t.s[j][i]=w;}2023年11月28日70t.prim(t); //用普里姆算法求最小生成樹(shù)

for(i=1;i<n;i++) //輸出n-1條生成樹(shù)的邊

{cout<<t.ct[i].fromvex<<"";cout<<t.ct[i].endvex<<"";cout<<t.ct[i].weight<<endl;}}該算法的時(shí)間復(fù)雜度為O(n2)，與邊數(shù)e無(wú)關(guān)。用普里姆算法求得圖7-20（a）中的無(wú)向網(wǎng)的生成樹(shù)，結(jié)果如圖7-21所示。圖7-21普里姆算法求解的結(jié)果2023年11月28日717.4.3克魯斯卡爾（kruskal）算法1．克魯斯卡爾算法的基本思想克魯斯卡爾算法的基本思想是：將圖中所有邊按權(quán)值遞增順序排列，依次選定權(quán)值較小的邊，但要求后面選取的邊不能與前面所有選取的邊構(gòu)成回路，若構(gòu)成回路，則放棄該條邊，再去選后面權(quán)值較大的邊，n個(gè)頂點(diǎn)的圖中，選夠n-1條邊即可。例如，對(duì)圖7-20（a）中的無(wú)向網(wǎng)，用克魯斯卡爾算法求最小生成樹(shù)的過(guò)程見(jiàn)下面的圖7-22各步驟。

（a）選第1條邊（b）選第2條邊2023年11月28日72（c）選第3條邊（d）選第4條邊（e）選第5條邊（不能選(1,4)邊，因?yàn)闀?huì)構(gòu)成回路，但可選(2,3)或(5,3)中之一）圖7-22克魯斯卡爾算法求最小生成樹(shù)的過(guò)程2023年11月28日732．克魯斯卡爾算法實(shí)現(xiàn)本算法參照的示例為圖7-20（a）中的無(wú)向網(wǎng)#include<iostream.h>constintn=6;constinte=10;classedgeset //定義一條邊

{public: intfromvex;intendvex;intweight;};classtree //定義生成樹(shù)

{public:edgesetc[n]; //存放生成樹(shù)邊edgesetge[e+1]; //存放網(wǎng)中所有邊ints[n+1][n+1]; //s為一個(gè)集合，一行元素s[i][0]~s[i][n]表示一個(gè)集合

//若s[i][t]=1，則表示頂點(diǎn)t屬于該集合，否則不屬于該集合voidkruska(tree&t);};2023年11月28日74voidtree::kruska(tree&t){inti,j;for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i==j)t.s[i][j]=1;elset.s[i][j]=0;intk=1; //統(tǒng)計(jì)生成樹(shù)的邊數(shù)

intd=1; //表示待掃描邊的下標(biāo)位置

intm1,m2; //記錄一條邊的兩個(gè)頂點(diǎn)所在集合的序號(hào)while(k<n){for(i=1;i<=n;i++)for(j=1;j<=n;j++){if((t.ge[d].fromvex==j)&&(t.s[i][j]==1))m1=i;if((t.ge[d].endvex==j)&&(t.s[i][j]==1))m2=i;}2023年11月28日75if(m1!=m2){t.c[k]=t.ge[d];k++;for(j=1;j<=n;j++){t.s[m1][j]=t.s[m1][j]||t.s[m2][j]; //求出一條邊后，合并兩個(gè)集合

t.s[m2][j]=0; //另一個(gè)集合置為空

}}d++;}}voidmain(){treet;for(inti=1;i<=e;i++)//按從小到大的順序輸入網(wǎng)中的邊的起點(diǎn)、終點(diǎn)及權(quán)值

{cin>>t.ge[i].fromvex;cin>>t.ge[i].endvex;cin>>t.ge[i].weight;}t.kruska(t);for(i=1;i<n;i++) //輸出最小生成樹(shù)的邊的起點(diǎn)、終點(diǎn)及權(quán)值

{cout<<t.c[i].fromvex<<"";cout<<t.c[i].endvex<<"";cout<<t.c[i].weight<<endl;}}2023年11月28日76利用上述算法實(shí)現(xiàn)時(shí)，要求輸入的網(wǎng)中的邊上權(quán)值必須為從小到大排列。例如，對(duì)圖7-23（a）的無(wú)向網(wǎng)，輸入的值順序見(jiàn)圖7-23（b），通過(guò)算法調(diào)用得到的最小生成樹(shù)的樹(shù)邊見(jiàn)圖7-24。（a）無(wú)向網(wǎng)（b）用克魯斯卡爾算法求最小生成樹(shù)的輸入邊的順序圖7-23無(wú)向網(wǎng)及用克魯斯卡爾算法求最小生成樹(shù)的輸入邊的順序圖7-24用克魯斯卡爾算法求出的圖7-23（a）的最小生成樹(shù)的樹(shù)邊2023年11月28日777.5最短路徑交通網(wǎng)絡(luò)中常常提出這樣的問(wèn)題：從甲地到乙地之間是否有公路連通?在有多條通路的情況下，哪一條路最短?交通網(wǎng)絡(luò)可用帶權(quán)圖來(lái)表示。頂點(diǎn)表示城市名稱，邊表示兩個(gè)城市有路連通，邊上權(quán)值可表示兩城市之間的距離、交通費(fèi)或途中所花費(fèi)的時(shí)間等。求兩個(gè)頂點(diǎn)之間的最短路徑，不是指路徑上邊數(shù)之和最少，而是指路徑上各邊的權(quán)值之和最小。另外，若兩個(gè)頂點(diǎn)之間沒(méi)有邊，則認(rèn)為兩個(gè)頂點(diǎn)無(wú)通路，但有可能有間接通路（從其他頂點(diǎn)達(dá)到）。路徑上的開(kāi)始頂點(diǎn)（出發(fā)點(diǎn)）稱為源點(diǎn)，路徑上的最后一個(gè)頂點(diǎn)稱為終點(diǎn)，并假定討論的權(quán)值不能為負(fù)數(shù)。2023年11月28日787.5.1單源點(diǎn)最短路徑1．單源點(diǎn)最短路徑單源點(diǎn)最短路徑是指：給定一個(gè)出發(fā)點(diǎn)（單源點(diǎn)）和一個(gè)有向網(wǎng)G=(V,E)，求出源點(diǎn)到其他各頂點(diǎn)之間的最短路徑。例如，對(duì)圖7-25所示的有向網(wǎng)G，設(shè)頂點(diǎn)1為源點(diǎn)，則源點(diǎn)到其余各頂點(diǎn)的最短路徑如圖7-26所示。

圖7-25有向網(wǎng)G

圖7-26源點(diǎn)1到其余頂點(diǎn)的最短路徑2023年11月28日79從圖7-25可以看出，從頂點(diǎn)1到頂點(diǎn)5有四條路徑：①1→5，②1→4→5，③1→4→3→5，④1→2→3→5，路徑長(zhǎng)度分別為100，90，60，70，因此，從源點(diǎn)1到頂點(diǎn)5的最短路徑為60。那么怎樣求出單源點(diǎn)的最短路徑呢？我們可以將源點(diǎn)到終點(diǎn)的所有路徑都列出來(lái)，然后在里面選最短的一條即可。但是這樣做，用手工方式可以，當(dāng)路徑特別多時(shí)，就顯得特別麻煩，并且沒(méi)有什么規(guī)律，不能用計(jì)算機(jī)算法實(shí)現(xiàn)。迪杰斯特拉（Dijkstra）在做了大量觀察后，首先提出了按路長(zhǎng)度遞增的順序產(chǎn)生各頂點(diǎn)的最短路徑算法，我們稱之為迪杰斯特拉算法。2023年11月28日802．迪杰斯特拉算法的基本思想算法的基本思想是：設(shè)置并逐步擴(kuò)充一個(gè)集合S，存放已求出其最短路徑的頂點(diǎn)，則尚未確定最短路徑的頂點(diǎn)集合是V-S，其中V為網(wǎng)中所有頂點(diǎn)集合。按最短路徑長(zhǎng)度遞增的順序逐個(gè)以V-S中的頂點(diǎn)加到S中，直到S中包含全部頂點(diǎn)，而V-S為空。具體做法是：設(shè)源點(diǎn)為Vl，則S中只包含頂點(diǎn)Vl，令W=V-S，則W中包含除Vl外圖中所有頂點(diǎn)，Vl對(duì)應(yīng)的距離值為0，W中頂點(diǎn)對(duì)應(yīng)的距離值是這樣規(guī)定的：若圖中有弧<Vl,Vj>，則Vj頂點(diǎn)的距離為此弧權(quán)值，否則為∞（一個(gè)很大的數(shù)），然后每次從W中的頂點(diǎn)中選一個(gè)其距離值為最小的頂點(diǎn)Vm加入到S中，每往S中加入一個(gè)頂點(diǎn)Vm，就要對(duì)W中的各個(gè)頂點(diǎn)的距離值進(jìn)行一次修改。若加進(jìn)Vm做中間頂點(diǎn)，使<Vl,Vm>+<Vm,Vj>的值小于<Vl,Vj>值，則用<Vl,Vm>+<Vm,Vj>代替原來(lái)Vj的距離，修改后再在W中選距離值最小的頂點(diǎn)加入到S中，如此進(jìn)行下去，直到S中包含圖中所有頂點(diǎn)為止。2023年11月28日813．迪杰斯特拉算法實(shí)現(xiàn)(略)利用該算法求得的最短路徑如下面的圖7-27各步驟所示。

（a）一個(gè)有向網(wǎng)點(diǎn)（b）源點(diǎn)1到其他頂點(diǎn)的初始距離2023年11月28日82

（c）第一次求得的結(jié)果（d）第二次求得的結(jié)果（e）第三次求得的結(jié)果（f）第四次求得的結(jié)果圖7-27迪杰斯特拉算法求最短路徑的過(guò)程及結(jié)果2023年11月28日83從圖7-27可知，1到2的最短距離為3，路徑為：1→2；1到3的最短距離為15，路徑為：1→2→4→3；1到4的最短距離為11，路徑為：1→2→4；1到5的最短距離為23，路徑為：1→2→4→5。7.5.2所有頂點(diǎn)對(duì)之間的最短路徑1．頂點(diǎn)對(duì)之間的最短路徑的概念所有頂點(diǎn)對(duì)之間的最短路徑是指：對(duì)于給定的有向網(wǎng)G=(V,E)，要對(duì)G中任意一對(duì)頂點(diǎn)有序?qū)，W(V≠W)，找出V到W的最短距離和W到V的最短距離。解決此問(wèn)題的一個(gè)有效方法是：輪流以每一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行迪杰斯特拉算法n次，即可求得每一對(duì)頂點(diǎn)之間的最短路徑,總的時(shí)間復(fù)雜度為O(n3)。下面將介紹用弗洛伊德（Floyd）算法來(lái)實(shí)現(xiàn)此功能，時(shí)間復(fù)雜度仍為O(n3)，但該方法比調(diào)用n次迪杰斯特拉方法更直觀一些。2023年11月28日842．弗洛伊德算法的基本思想弗洛伊德算法仍然使用前面定義的圖的鄰接矩陣arcs[n+1][n+1]來(lái)存儲(chǔ)帶權(quán)有向圖。算法的基本思想是：設(shè)置一個(gè)n×n的矩陣A(k)，其中除對(duì)角線的元素都等于0外，其他元素A(k)[i][j]表示頂點(diǎn)i到頂點(diǎn)j的路徑長(zhǎng)度，k表示運(yùn)算步驟。開(kāi)始時(shí)，以任意兩個(gè)頂點(diǎn)之間的有向邊的權(quán)值作為路徑長(zhǎng)度，沒(méi)有有向邊時(shí)，路徑長(zhǎng)度為∞，當(dāng)k=0時(shí)，A(0)[i][j]=arcs[i][j],以后逐步嘗試在原路徑中加入其他頂點(diǎn)作為中間頂點(diǎn)，如果增加中間頂點(diǎn)后，得到的路徑比原來(lái)的路徑長(zhǎng)度減少了，則以此新路徑代替原路徑，修改矩陣元素。具體做法為：第一步，讓所有邊上加入中間頂點(diǎn)1，取A[i][j]與A[i][1]+A[1][j