最小生成樹和拓撲排序課件

最小生成樹和7月18日最小生成樹和7月18日1最小生成樹最小生成樹2一、什么是圖的最小生成樹（MST）？

不知道大家還記不記得樹的一個定理：N個點用N-1條邊連接成一個連通塊，形成的圖形只可能是樹，沒有別的可能。

一個有N個點的圖，邊一定是大于等于N-1條的。圖的最小生成樹，就是在這些邊中選擇N-1條出來，連接所有的N個點。這N-1條邊的邊權之和是所有方案中最小的。一、什么是圖的最小生成樹（MST）？一個有N個點的圖，3二、最小生成樹用來解決什么問題？

就是用來解決如何用最小的“代價”用N-1條邊連接N個點的問題。【引例】有一張城市地圖，圖中的頂點為城市，無向邊代表兩個城市間的連通關系，邊上的權為在這兩個城市之間修建高速公路的造價，研究后發(fā)現(xiàn)，這個地圖有一個特點，即任一對城市都是連通的?，F(xiàn)在的問題是，要修建若干高速公路把所有城市聯(lián)系起來，問如何設計可使得工程的總造價最少？123452471162二、最小生成樹用來解決什么問題？就是用來解決如何用最4Prim算法算法分析&思想講解：Prim算法采用“藍白點”思想：白點代表已經(jīng)進入最小生成樹的點，藍點代表未進入最小生成樹的點。Prim算法每次循環(huán)都將一個藍點u變?yōu)榘c，并且此藍點u與白點相連的最小邊權min[u]還是當前所有藍點中最小的。這樣相當于向生成樹中添加了n-1次最小的邊，最后得到的一定是最小生成樹。我們通過對右圖最小生成樹的求解模擬來理解上面的思想。藍點和虛線代表未進入最小生成樹的點、邊；白點和實線代表已進入最小生成樹的點、邊。123452471162Prim算法算法分析&思想講解：1234524711625初始時所有點都是藍點，min[1]=0,min[2、3、4、5]=∞。權值之和MST=0。123452471162第一次循環(huán)自然是找到min[1]=0最小的藍點1。將1變?yōu)榘c，接著枚舉與1相連的所有藍點2、3、4，修改它們與白點相連的最小邊權。123452471162min[2]=w[1][2]=2;min[3]=w[1][3]=4;min[4]=w[1][4]=7;123452471162第一次循環(huán)自然是找到min[1]=06第二次循環(huán)是找到min[2]最小的藍點2。將2變?yōu)榘c，接著枚舉與2相連的所有藍點3、5，修改它們與白點相連的最小邊權。123452471162min[3]=w[2][3]=1;min[5]=w[2][5]=2;

第三次循環(huán)是找到min[3]最小的藍點3。將3變?yōu)榘c，接著枚舉與3相連的所有藍點4、5，修改它們與白點相連的最小邊權。

123452471162min[4]=w[3][4]=1;由于min[5]=2<w[3][5]=6;所以不修改min[5]的值。123452471162min[3]=w[2][3]=1;7最后兩輪循環(huán)將點4、5以及邊w[2][5],w[3][4]添加進最小生成樹。123452471162最后權值之和MST=6。

這n次循環(huán)，每次循環(huán)我們都能讓一個新的點加入生成樹，n次循環(huán)就能把所有點囊括到其中；每次循環(huán)我們都能讓一條新的邊加入生成樹，n-1次循環(huán)就能生成一棵含有n個點的樹；每次循環(huán)我們都取一條最小的邊加入生成樹，n-1次循環(huán)結束后，我們得到的就是一棵最小的生成樹。這就是Prim采取貪心法生成一棵最小生成樹的原理。算法時間復雜度：O(N2)。123452471162最后權值之和MST=6。8算法描述：以1為起點生成最小生成樹，min[v]表示藍點v與白點相連的最小邊權。MST表示最小生成樹的權值之和。a）初始化：min[v]=∞(v≠1);min[1]=0;MST=0;b）for(i=1;i<=n;i++)1.尋找min[u]最小的藍點u。2.將u標記為白點3.MST+=min[u]4.for與白點u相連的所有藍點vif(w[u][v]<min[v])min[v]=w[u][v];c）算法結束：MST即為最小生成樹的權值之和算法描述：9【例1】、最優(yōu)布線問題【問題描述】學校有n臺計算機，為了方便數(shù)據(jù)傳輸，現(xiàn)要將它們用數(shù)據(jù)線連接起來。兩臺計算機被連接是指它們間有數(shù)據(jù)線連接。由于計算機所處的位置不同，因此不同的兩臺計算機的連接費用往往是不同的。當然，如果將任意兩臺計算機都用數(shù)據(jù)線連接，費用將是相當龐大的。為了節(jié)省費用，我們采用數(shù)據(jù)的間接傳輸手段，即一臺計算機可以間接的通過若干臺計算機（作為中轉）來實現(xiàn)與另一臺計算機的連接?，F(xiàn)在由你負責連接這些計算機，任務是使任意兩臺計算機都連通（不管是直接的或間接的）。【輸入格式】輸入文件wire.in，第一行為整數(shù)n（2<=n<=100），表示計算機的數(shù)目。此后的n行，每行n個整數(shù)。第x+1行y列的整數(shù)表示直接連接第x臺計算機和第y臺計算機的費用?！据敵龈袷健枯敵鑫募ire.out，一個整數(shù)，表示最小的連接費用?！据斎霕永?012101210【輸出樣例】2（注：表示連接1和2，2和3，費用為2）【例1】、最優(yōu)布線問題10【參考程序】#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intg[101][101];//鄰接矩陣intminn[101];//minn[i]存放藍點i與白點相連的最小邊權boolu[101];//u[i]=True，表示頂點i還未加入到生成樹中//u[i]=False，表示頂點i已加入到生成樹中intn,i,j;intmain(){cin>>n;for(i=1;i<=n;i++)for(j=1;j<=n;j++)cin>>g[i][j];memset(minn,0x7f,sizeof(minn));//初始化為maxintminn[1]=0;memset(u,1,sizeof(u));//初始化為True，表示所有頂點為藍點【參考程序】11for(i=1;i<=n;i++){intk=0;for(j=1;j<=n;j++)//找一個與白點相連的權值最小的藍點kif(u[j]&&(minn[j]<minn[k]))k=j;u[k]=false;//藍點k加入生成樹，標記為白點for(j=1;j<=n;j++)//修改與k相連的所有藍點if(u[j]&&(g[k][j]<minn[j]))minn[j]=g[k][j];}inttotal=0;for(i=1;i<=n;i++)//累加權值total+=minn[i];cout<<total<<endl;return0;}知識擴展：本算法在移動通信、智能交通、移動物流、生產(chǎn)調度等物聯(lián)網(wǎng)相關領域都有十分現(xiàn)實的意義，采用好的算法，就能節(jié)省成本提高效率。for(i=1;i<=n;i++)12

【引例】有一張城市地圖，圖中的頂點為城市，無向邊代表兩個城市間的連通關系，邊上的權為在這兩個城市之間修建高速公路的造價，研究后發(fā)現(xiàn)，這個地圖有一個特點，即任一對城市都是連通的?，F(xiàn)在的問題是，要修建若干高速公路把所有城市聯(lián)系起來，問如何設計可使得工程的總造價最少？12345212896731012345212896731013Kruskal算法Kruskal（克魯斯卡爾）算法是一種巧妙利用并查集來求最小生成樹的算法。

Kruskal算法將一個連通塊當做一個集合。Kruskal首先將所有的邊按從小到大順序排序（一般使用快排），并認為每一個點都是孤立的，分屬于n個獨立的集合。然后按順序枚舉每一條邊。如果這條邊連接著兩個不同的集合，那么就把這條邊加入最小生成樹，這兩個不同的集合就合并成了一個集合；如果這條邊連接的兩個點屬于同一集合，就跳過。直到選取了n-1條邊為止。123452128967310Kruskal算法Kruskal（克魯斯卡爾）算法是一種14思想講解：Kruskal（克魯斯卡爾）算法開始時，認為每一個點都是孤立的，分屬于n個獨立的集合。1234521289673105個集合{{1}，{2}，{3}，{4}，{5}}生成樹中沒有邊Kruskal每次都選擇一條最小的邊，而且這條邊的兩個頂點分屬于兩個不同的集合。將選取的這條邊加入最小生成樹，并且合并集合。1234521289673105個集合{{1}，{2}，{15第一次選擇的是<1,2>這條邊，將這條邊加入到生成樹中，并且將它的兩個頂點1、2合并成一個集合。1234521289673104個集合{{1，2}，{3}，{4}，{5}}生成樹中有一條邊{<1,2>}第二次選擇的是<4,5>這條邊，將這條邊加入到生成樹中，并且將它的兩個頂點4、5合并成一個集合。1234521289673103個集合{{1，2}，{3}，{4，5}}生成樹中有2條邊{<1,2>，<4,5>}第一次選擇的是<1,2>這條邊，將這條邊加入到生成樹中，并且16第三次選擇的是<3,5>這條邊，將這條邊加入到生成樹中，并且將它的兩個頂點3、5所在的兩個集合合并成一個集合1234521289673102個集合{{1，2}，{3，4，5}}生成樹中有3條邊{<1,2>，<4,5>，<3，5>}第四次選擇的是<2,5>這條邊，將這條邊加入到生成樹中，并且將它的兩個頂點2、5所在的兩個集合合并成一個集合。1234521289673101個集合{{1，2，3，4，5}}生成樹中有4條邊{<1,2>，<4,5>，<3，5>，<2,5>}第三次選擇的是<3,5>這條邊，將這條邊加入到生成樹中，并且17

算法結束，最小生成樹權值為19。通過上面的模擬能夠看到，Kruskal算法每次都選擇一條最小的，且能合并兩個不同集合的邊，一張n個點的圖總共選取n-1次邊。因為每次我們選的都是最小的邊，所以最后的生成樹一定是最小生成樹。每次我們選的邊都能夠合并兩個集合，最后n個點一定會合并成一個集合。通過這樣的貪心策略，Kruskal算法就能得到一棵有n-1條邊，連接著n個點的最小生成樹。

Kruskal算法的時間復雜度為O(E*logE)，E為邊數(shù)。

18算法描述:初始化并查集。father[x]=x。tot=0將所有邊用快排從小到大排序。計數(shù)器k=0;for(i=1;i<=M;i++)//循環(huán)所有已從小到大排序的邊

if這是一條u,v不屬于同一集合的邊(u,v)(因為已經(jīng)排序，所以必為最小)

begin

①合并u,v所在的集合，相當于把邊(u,v)加入最小生成樹。

②tot=tot+W(u,v)

③k++

④如果k=n-1,說明最小生成樹已經(jīng)生成，則break;end;6.結束，tot即為最小生成樹的總權值之和。算法描述:19【例2】、最短網(wǎng)絡Agri-Net【問題描述】農(nóng)民約翰被選為他們鎮(zhèn)的鎮(zhèn)長！他其中一個競選承諾就是在鎮(zhèn)上建立起互聯(lián)網(wǎng)，并連接到所有的農(nóng)場。當然，他需要你的幫助。約翰已經(jīng)給他的農(nóng)場安排了一條高速的網(wǎng)絡線路，他想把這條線路共享給其他農(nóng)場。為了用最小的消費，他想鋪設最短的光纖去連接所有的農(nóng)場。你將得到一份各農(nóng)場之間連接費用的列表，你必須找出能連接所有農(nóng)場并所用光纖最短的方案。每兩個農(nóng)場間的距離不會超過100000。【輸入格式】第一行：農(nóng)場的個數(shù)，N（3<=N<=100）。第二行..結尾后來的行包含了一個N*N的矩陣,表示每個農(nóng)場之間的距離。理論上，他們是N行，每行由N個用空格分隔的數(shù)組成，實際上，他們限制在80個字符，因此，某些行會緊接著另一些行。當然，對角線將會是0，因為不會有線路從第i個農(nóng)場到它本身?！据敵龈袷健?/p>

只有一個輸出，其中包含連接到每個農(nóng)場的光纖的最小長度。【輸入樣例】agrinet.in40492140817980162117160【輸出樣例】agrinet.out

28【例2】、最短網(wǎng)絡Agri-Net第一行：農(nóng)場的個數(shù)，20【參考程序】#include<cstdio>#include<iostream>#include<algorithm>//sort()需要用到<algorithm>庫usingnamespacestd;structpoint{intx;inty;intv;};

//定義結構類型，表示邊pointa[9901];

//存邊intfat[101];intn,i,j,x,m,tot,k;intfather(intx){if(fat[x]!=x)fat[x]=father(fat[x]);returnfat[x];}voidunionn(intx,inty){intfa=father(x);intfb=father(y);if(fa!=fb)fat[fa]=fb;}【參考程序】21intcmp(constpoint&a,constpoint&b)//sort()自定義的比較函數(shù){if(a.v<b.v)return1;elsereturn0;}intmain(){cin>>n;for(i=1;i<=n;i++)for(j=1;j<=n;j++){cin>>x;if(x!=0){m++;a[m].x=i;a[m].y=j;a[m].v=x;}}for(i=1;i<=n;i++)fat[i]=i;sort(a+1,a+m+1,cmp);//C++標準庫中自帶的快排

//cmp為自定義的比較函數(shù)。表示a數(shù)組的1-m按規(guī)則cmp排序intcmp(constpoint&a,constp22for(i=1;i<=m;i++){if(father(a[i].x)!=father(a[i].y)){unionn(a[i].x,a[i].y);tot+=a[i].v;k++;}if(k==n-1)break;}cout<<tot;return0;}最小生成樹和拓撲排序課件23上機練習1、局域網(wǎng)【問題描述】某個局域網(wǎng)內有n(n<=100)臺計算機，由于搭建局域網(wǎng)時工作人員的疏忽，現(xiàn)在局域網(wǎng)內的連接形成了回路，我們知道如果局域網(wǎng)形成回路那么數(shù)據(jù)將不停的在回路內傳輸，造成網(wǎng)絡卡的現(xiàn)象。因為連接計算機的網(wǎng)線本身不同，所以有一些連線不是很暢通，我們用f(i,j)表示i,j之間連接的暢通程度(f(i,j)<=1000)，f(i,j)值越小表示i,j之間連接越通暢，f(i,j)為0表示i,j之間無網(wǎng)線連接。現(xiàn)在我們需要解決回路問題，我們將除去一些連線，使得網(wǎng)絡中沒有回路，并且被除去網(wǎng)線的Σf(i,j)最大，請求出這個最大值。【輸入格式】第一行兩個正整數(shù)nk接下來的k行每行三個正整數(shù)ijm表示i,j兩臺計算機之間有網(wǎng)線聯(lián)通，通暢程度為m?！据敵龈袷健恳粋€正整數(shù)，Σf(i,j)的最大值【輸入輸出樣例】【輸入樣例】【輸出樣例】551281311532453428上機練習1、局域網(wǎng)【輸入樣例】【輸出樣例】5515242、繁忙的都市【問題描述】城市C是一個非常繁忙的大都市，城市中的道路十分的擁擠，于是市長決定對其中的道路進行改造。城市C的道路是這樣分布的：城市中有n個交叉路口，有些交叉路口之間有道路相連，兩個交叉路口之間最多有一條道路相連接。這些道路是雙向的，且把所有的交叉路口直接或間接的連接起來了。每條道路都有一個分值，分值越小表示這個道路越繁忙，越需要進行改造。但是市政府的資金有限，市長希望進行改造的道路越少越好，于是他提出下面的要求：改造的那些道路能夠把所有的交叉路口直接或間接的連通起來。在滿足要求1的情況下，改造的道路盡量少。在滿足要求1、2的情況下，改造的那些道路中分值最大值盡量小。【編程任務】作為市規(guī)劃局的你，應當作出最佳的決策，選擇那些道路應當被修建。【輸入格式】city.in第一行有兩個整數(shù)n,m表示城市有n個交叉路口，m條道路。接下來m行是對每條道路的描述，u,v,c表示交叉路口u和v之間有道路相連，分值為c。(1≤n≤300，1≤c≤10000)【輸出格式】city.out兩個整數(shù)s,max，表示你選出了幾條道路，分值最大的那條道路的分值是多少。【輸入輸出樣例】【輸入樣例】【輸出樣例】45123145247236348362、繁忙的都市【輸入樣例】【輸出樣例】452363253、聯(lián)絡員【問題描述】

Tyvj已經(jīng)一歲了，網(wǎng)站也由最初的幾個用戶增加到了上萬個用戶，隨著Tyvj網(wǎng)站的逐步壯大，管理員的數(shù)目也越來越多，現(xiàn)在你身為Tyvj管理層的聯(lián)絡員，希望你找到一些通信渠道，使得管理員兩兩都可以聯(lián)絡（直接或者是間接都可以）。Tyvj是一個公益性的網(wǎng)站，沒有過多的利潤，所以你要盡可能的使費用少才可以。目前你已經(jīng)知道，Tyvj的通信渠道分為兩大類，一類是必選通信渠道，無論價格多少，你都需要把所有的都選擇上；還有一類是選擇性的通信渠道，你可以從中挑選一些作為最終管理員聯(lián)絡的通信渠道。數(shù)據(jù)保證給出的通行渠道可以讓所有的管理員聯(lián)通?！据斎敫袷健?/p>

第一行n，m表示Tyvj一共有n個管理員，有m個通信渠道第二行到m+1行，每行四個非負整數(shù)，p,u,v,w當p=1時，表示這個通信渠道為必選通信渠道；當p=2時，表示這個通信渠道為選擇性通信渠道；u,v,w表示本條信息描述的是u，v管理員之間的通信渠道，u可以收到v的信息，v也可以收到u的信息，w表示費用?！据敵龈袷健?/p>

最小的通信費用。3、聯(lián)絡員26561121123113411411225102255【輸入樣例】【輸出樣例】9樣例解釋：1-2-3-4-1存在四個必選渠道，形成一個環(huán)，互相可以到達。需要讓所有管理員聯(lián)通，需要聯(lián)通2和5號管理員，選擇費用為5的渠道，所以總的費用為9注意：u,v之間可能存在多條通信渠道，你的程序應該累加所有u,v之間的必選通行渠道數(shù)據(jù)范圍：對于30%的數(shù)據(jù)，n<=10m<=100對于50%的數(shù)據(jù),n<=200m<=1000對于100%的數(shù)據(jù)，n<=2000m<=1000056【輸入樣例】【輸出樣例】樣例解釋：27拓撲排序拓撲排序28AOV網(wǎng)

在日常生活中，一項大的工程可以看作是由若干個子工程（這些子工程稱為“活動”）組成的集合，這些子工程（活動）之間必定存在一些先后關系，即某些子工程（活動）必須在其它一些子工程（活動）完成之后才能開始，我們可以用有向圖來形象地表示這些子工程（活動）之間的先后關系，子工程（活動）為頂點，子工程（活動）之間的先后關系為有向邊，這種有向圖稱為“頂點活動網(wǎng)絡”，又稱“AOV網(wǎng)”。123567894AOV網(wǎng)12356789429在AOV網(wǎng)中，有向邊代表子工程（活動）的先后關系，我們把一條有向邊起點的活動成為終點活動的前驅活動，同理終點的活動稱為起點活動的后繼活動。而只有當一個活動全部的前驅全部都完成之后，這個活動才能進行。例如在上圖中，只有當工程1完成之后，工程2、3、4、5、6才能開始進行。只有當2、3、4全部完成之后，7才能開始進行。一個AOV網(wǎng)必定是一個有向無環(huán)圖，即不應該帶有回路。否則，會出現(xiàn)先后關系的自相矛盾。1234上圖就是一個出現(xiàn)環(huán)產(chǎn)生自相矛盾的情況。4是1的前驅，想完成1，必須先完成4。3是4的前驅，而2是3的前驅，1又是2的前驅。最后造成想完成1，必須先完成1本身，這顯然出現(xiàn)了矛盾。在AOV網(wǎng)中，有向邊代表子工程（活動）的先后關系，我們把30拓撲排序算法

拓撲排序算法，只適用于AOV網(wǎng)（有向無環(huán)圖）。把AOV網(wǎng)中的所有活動排成一個序列，使得每個活動的所有前驅活動都排在該活動的前面，這個過程稱為“拓撲排序”，所得到的活動序列稱為“拓撲序列”。一個AOV網(wǎng)的拓撲序列是不唯一的，例如下面的這張圖，它的拓撲序列可以是：ABCDE，也可以是ACBDE，或是ADBCE。在下圖所示的AOV網(wǎng)中，工程B和工程C顯然可以同時進行，先后無所謂；但工程E卻要等工程B、C、D都完成以后才能進行。ABCED

構造拓撲序列可以幫助我們合理安排一個工程的進度，由AOV網(wǎng)構造拓撲序列具有很高的實際應用價值。拓撲排序算法拓撲排序算法，只適用于AOV網(wǎng)（有向無31算法思想：構造拓撲序列的拓撲排序算法思想很簡單：1）選擇一個入度為0的頂點并輸出2）然后從AOV網(wǎng)中刪除此頂點及以此頂點為起點的所有關聯(lián)邊；3）重復上述兩步，直到不存在入度為0的頂點為止。4）若輸出的頂點數(shù)小于AOV網(wǎng)中的頂點數(shù)，則輸出“有回路信息”，否則輸出的頂點序列就是一種拓撲序列從第四步可以看出，拓撲排序可以用來判斷一個有向圖是否有環(huán)。只有有向無環(huán)圖才存在拓撲序列。最小生成樹和拓撲排序課件32算法實現(xiàn)：a)數(shù)據(jù)結構：indgr[i]:

頂點i的入度;

stack[

]:

棧b)初始化:top=0(棧頂指針置零)c)將初始狀態(tài)所有入度為0的頂點壓棧d)I=0(計數(shù)器)e)while棧非空(top>0)i.棧頂?shù)捻旤cv出棧；top-1;輸出v；i++；ii.forv的每一個后繼頂點u1.indgr[u]--;u的入度減12.if（u的入度變?yōu)?）頂點u入棧f)算法結束這個程序采用棧來找出入度為0的點，棧里的頂點，都是入度為0的點。算法實現(xiàn)：33我們結合下圖詳細講解：ABCD開始時，只有A入度為0，A入棧。棧：ABCD棧頂元素A出棧并輸出A，A的后繼B、C入度減1，相當于刪除A的所有關聯(lián)邊棧：空拓撲序列：A我們結合下圖詳細講解：ABCD開始時，只有A入度為0，A入棧34BCDB、C的入度都變成0，依次將B、C入棧。棧：BC（入棧順序不唯一）拓撲序列：ABD棧頂元素C出棧并輸出C，C的后繼D入度減1棧：B拓撲序列：ACBCDB、C的入度都變成0，依次將B、C入棧。棧：BC（入棧35D棧頂元素B出棧并輸出B，B的后繼D入度再減1。這時D入度為0，入棧。棧：D拓撲序列：ACBD棧頂元素D出棧并輸出D。?？?，結束棧：空拓撲序列：ACBD（不唯一）簡單&高效&實用的算法。上述實現(xiàn)方法復雜度O(V+E)。D棧頂元素B出棧并輸出B，B的后繼D入度再減1。這時D入度為36【例3】、家譜樹【問題描述】有個人的家族很大，輩分關系很混亂，請你幫整理一下這種關系。給出每個人的孩子的信息。輸出一個序列，使得每個人的后輩都比那個人后列出?！据斎敫袷健康?行一個整數(shù)N（1<=N<=100），表示家族的人數(shù)。接下來N行，第I行描述第I個人的兒子。每行最后是0表示描述完畢?！据敵龈袷健枯敵鲆粋€序列，使得每個人的后輩都比那個人后列出。如果有多解輸出任意一解?！据斎霕永?/p>

5045101053030【輸出樣例】

24531最小生成樹和拓撲排序課件37【參考程序】#include<cstdio>#include<iostream>usingnamespacestd;inta[101][101],c[101],r[101],ans[101];inti,j,tot,temp,num,n,m;intmain(){cin>>n;for(i=1;i<=n;i++){do{cin>>j;if(j!=0){c[i]++;//c[i]用來存點i的出度a[i][c[i]]=j;r[j]++;//a[i,-1]用來存點i的入度。}}while(j!=0);}【參考程序】38for(i=1;i<=n;i++)if(r[i]==0)ans[++tot]=i;

//把圖中所有入度為0的點入棧，棧用一維數(shù)組ans[]表示do{temp=ans[tot];cout<<temp<<"";tot--;num++;

//棧頂元素出棧并輸出for(i=1;i<=c[temp];i++){r[a[temp][i]]--;if(r[a[temp][i]]==0)//如果入度減1后變成0，則將這個后繼點入棧ans[++tot]=a[temp][i];}}while(num!=n);

//如果輸出的點的數(shù)目num等于n，說明算法結束return0;}for(i=1;i<=n;i++)39【例4】獎金【問題描述】由于無敵的凡凡在2005年世界英俊帥氣男總決選中勝出，YaliCompany總經(jīng)理Mr.Z心情好，決定給每位員工發(fā)獎金。公司決定以每個人本年在公司的貢獻為標準來計算他們得到獎金的多少。于是Mr.Z下令召開m方會談。每位參加會談的代表提出了自己的意見：“我認為員工a的獎金應該比b高！”Mr.Z決定要找出一種獎金方案，滿足各位代表的意見，且同時使得總獎金數(shù)最少。每位員工獎金最少為100元。【輸入格式】第一行兩個整數(shù)n,m，表示員工總數(shù)和代表數(shù)；以下m行，每行2個整數(shù)a,b，表示某個代表認為第a號員工獎金應該比第b號員工高?！据敵龈袷健咳魺o法找到合理方案，則輸出“PoorXed”；否則輸出一個數(shù)表示最少總獎金?！据斎霕永?/p>

21

12【輸出樣例】

201最小生成樹和拓撲排序課件40【數(shù)據(jù)規(guī)模】

80％的數(shù)據(jù)滿足n<=1000，m<=2000；100％的數(shù)據(jù)滿足n<=10000，m<=20000。【算法分析】首先構圖，若存在條件“a的錢比b多”則從b引一條有向指向a；然后拓撲排序，若無法完成排序則表示問題無解（存在圈）；若可以得到完整的拓撲序列，則按序列順序進行遞推：設f[i]表示第i個人能拿的最少獎金數(shù)；首先所有f[i]=100（題目中給定的最小值）；然后按照拓撲順序考察每個點i，若存在有向邊(j,i)，則表示f[i]必須比f[j]大，因此我們令f[i]=Max{f[i],f[j]+1}即可；遞推完成之后所有f[i]的值也就確定了，而答案就等于f[1]+…+f[n]。最小生成樹和拓撲排序課件41【參考程序】#include<iostream>usingnamespacestd;inta[10001][301]={0},into[10001],ans[10001],m,n,money;voidinit()

//讀入數(shù)據(jù)，并構建圖，統(tǒng)計入度{inti,x,y;cin>>n>>m;for(i=1;i<=m;i++){cin>>x>>y;a[y][0]++;

//記錄由y引出邊的數(shù)目a[y][a[y][0]]=x;//記錄由a[y][0]引出邊的頂點into[x]++;//統(tǒng)計入度}}booltopsort()//拓撲排序{intt,tot,k,i,j;tot=0;k=0;while(tot<n)//tot頂點個數(shù){t=0;

//用來判斷有無環(huán)for(i=1;i<=n;i++)if(into[i]==0)

【參考程序】42{tot++;t++;money+=100;ans[t]=i;into[i]=0xfffffff;}if(t==0)returnfalse;//存在環(huán)

money+=k*t;k++;for(i=1;i<=t;i++)//去掉相連的邊

for(j=1;j<=a[ans[i]][0];j++)into[a[ans[i]][j]]--;}returntrue;}intmain(){init();money=0;if(topsort())cout<<money<<endl;elsecout<<"PoorXed"<<endl;return0;}{43上機練習4、煩人的幻燈片【問題描述】李教授將于今天下午作一次非常重要的演講。不信的事他不是一個非常愛整潔的人，他把自己演講要用的幻燈片隨便堆在了一起。因此，演講之前他不得不去整理這些幻燈片。作為一個講求效率的學者，他希望盡可能簡單地完成它。教授這次演講一共要用n張幻燈片（n<=26），這n張幻燈片按照演講要使用的順序已經(jīng)用數(shù)字1~n編了號。因為幻燈片是透明的，所以我們不能一下子看清每一個數(shù)字所對應的幻燈片?，F(xiàn)在我們用大寫字母A,B,C……再次把幻燈片依次編號。你的任務是編寫一個程序，把幻燈片的數(shù)字編號和字母編號對應起來，顯然這種對應應該是唯一的；若出現(xiàn)多種對應的情況或是某些數(shù)字編號和字母編號對應不起來，我們稱對應是無法實現(xiàn)的?！据斎敫袷健课募牡谝恍兄挥幸粋€整數(shù)n，表示有n張幻燈片，接下來的n行每行包括4個整數(shù)xmin,xmax,ymin,ymax（整數(shù)之間用空格分開）為幻燈片的坐標，這n張幻燈片按其在文件中出現(xiàn)的順序從前到后依次編號為A,B,C……，再接下來的n行依次為n個數(shù)字編號的坐標x,y，顯然在幻燈片之外是不會有數(shù)字的?！据敵龈袷健咳羰菍梢詫崿F(xiàn)，輸出文件應該包括n行，每一行為一個字母和一個數(shù)字，中間以一個空格隔開，并且每行以字母的升序排列，注意輸出的字母要大寫并且定格；反之，若是對應無法實現(xiàn)，在文件的第一行頂格輸出None即可。首行末無多余的空格。上機練習4、煩人的幻燈片44上機練習【輸入輸出樣例】slides.inslides.out4622102041861682021810244891519171172111A4B1C2D3上機練習slides.inslides.out4A4455、病毒【問題描述】有一天，小y突然發(fā)現(xiàn)自己的計算機感染了一種病毒！還好，小y發(fā)現(xiàn)這種病毒很弱，只是會把文檔中的所有字母替換成其它字母，但并不改變順序，也不會增加和刪除字母?，F(xiàn)在怎么恢復原來的文檔呢！小y很聰明，他在其他沒有感染病毒的機器上，生成了一個由若干單詞構成的字典，字典中的單詞是按照字母順序排列的，他把這個文件拷貝到自己的機器里，故意讓它感染上病毒，他想利用這個字典文件原來的有序性，找到病毒替換字母的規(guī)律，再用來恢復其它文檔?，F(xiàn)在你的任務是：告訴你被病毒感染了的字典，要你恢復一個字母串?！据斎敫袷健縱irus.in第一行為整數(shù)K（≤50000），表示字典中的單詞個數(shù)。以下K行，是被病毒感染了的字典，每行一個單詞。最后一行是需要你恢復的一串字母。所有字母均為小寫?！据敵龈袷健縱irus.out輸出僅一行，為恢復后的一串字母。當然也有可能出現(xiàn)字典不完整、甚至字典是錯的情況，這時請輸出一個0。最小生成樹和拓撲排序課件46【輸入樣例】

6

cebdbac

cac

ecd

dca

aba

bac

cedab【輸出樣例】

abcde【輸入樣例】47最小生成樹和7月18日最小生成樹和7月18日48最小生成樹最小生成樹49一、什么是圖的最小生成樹（MST）？

不知道大家還記不記得樹的一個定理：N個點用N-1條邊連接成一個連通塊，形成的圖形只可能是樹，沒有別的可能。

一個有N個點的圖，邊一定是大于等于N-1條的。圖的最小生成樹，就是在這些邊中選擇N-1條出來，連接所有的N個點。這N-1條邊的邊權之和是所有方案中最小的。一、什么是圖的最小生成樹（MST）？一個有N個點的圖，50二、最小生成樹用來解決什么問題？

就是用來解決如何用最小的“代價”用N-1條邊連接N個點的問題?！疽坑幸粡埑鞘械貓D，圖中的頂點為城市，無向邊代表兩個城市間的連通關系，邊上的權為在這兩個城市之間修建高速公路的造價，研究后發(fā)現(xiàn)，這個地圖有一個特點，即任一對城市都是連通的?，F(xiàn)在的問題是，要修建若干高速公路把所有城市聯(lián)系起來，問如何設計可使得工程的總造價最少？123452471162二、最小生成樹用來解決什么問題？就是用來解決如何用最51Prim算法算法分析&思想講解：Prim算法采用“藍白點”思想：白點代表已經(jīng)進入最小生成樹的點，藍點代表未進入最小生成樹的點。Prim算法每次循環(huán)都將一個藍點u變?yōu)榘c，并且此藍點u與白點相連的最小邊權min[u]還是當前所有藍點中最小的。這樣相當于向生成樹中添加了n-1次最小的邊，最后得到的一定是最小生成樹。我們通過對右圖最小生成樹的求解模擬來理解上面的思想。藍點和虛線代表未進入最小生成樹的點、邊；白點和實線代表已進入最小生成樹的點、邊。123452471162Prim算法算法分析&思想講解：12345247116252初始時所有點都是藍點，min[1]=0,min[2、3、4、5]=∞。權值之和MST=0。123452471162第一次循環(huán)自然是找到min[1]=0最小的藍點1。將1變?yōu)榘c，接著枚舉與1相連的所有藍點2、3、4，修改它們與白點相連的最小邊權。123452471162min[2]=w[1][2]=2;min[3]=w[1][3]=4;min[4]=w[1][4]=7;123452471162第一次循環(huán)自然是找到min[1]=053第二次循環(huán)是找到min[2]最小的藍點2。將2變?yōu)榘c，接著枚舉與2相連的所有藍點3、5，修改它們與白點相連的最小邊權。123452471162min[3]=w[2][3]=1;min[5]=w[2][5]=2;

第三次循環(huán)是找到min[3]最小的藍點3。將3變?yōu)榘c，接著枚舉與3相連的所有藍點4、5，修改它們與白點相連的最小邊權。

123452471162min[4]=w[3][4]=1;由于min[5]=2<w[3][5]=6;所以不修改min[5]的值。123452471162min[3]=w[2][3]=1;54最后兩輪循環(huán)將點4、5以及邊w[2][5],w[3][4]添加進最小生成樹。123452471162最后權值之和MST=6。

這n次循環(huán)，每次循環(huán)我們都能讓一個新的點加入生成樹，n次循環(huán)就能把所有點囊括到其中；每次循環(huán)我們都能讓一條新的邊加入生成樹，n-1次循環(huán)就能生成一棵含有n個點的樹；每次循環(huán)我們都取一條最小的邊加入生成樹，n-1次循環(huán)結束后，我們得到的就是一棵最小的生成樹。這就是Prim采取貪心法生成一棵最小生成樹的原理。算法時間復雜度：O(N2)。123452471162最后權值之和MST=6。55算法描述：以1為起點生成最小生成樹，min[v]表示藍點v與白點相連的最小邊權。MST表示最小生成樹的權值之和。a）初始化：min[v]=∞(v≠1);min[1]=0;MST=0;b）for(i=1;i<=n;i++)1.尋找min[u]最小的藍點u。2.將u標記為白點3.MST+=min[u]4.for與白點u相連的所有藍點vif(w[u][v]<min[v])min[v]=w[u][v];c）算法結束：MST即為最小生成樹的權值之和算法描述：56【例1】、最優(yōu)布線問題【問題描述】學校有n臺計算機，為了方便數(shù)據(jù)傳輸，現(xiàn)要將它們用數(shù)據(jù)線連接起來。兩臺計算機被連接是指它們間有數(shù)據(jù)線連接。由于計算機所處的位置不同，因此不同的兩臺計算機的連接費用往往是不同的。當然，如果將任意兩臺計算機都用數(shù)據(jù)線連接，費用將是相當龐大的。為了節(jié)省費用，我們采用數(shù)據(jù)的間接傳輸手段，即一臺計算機可以間接的通過若干臺計算機（作為中轉）來實現(xiàn)與另一臺計算機的連接。現(xiàn)在由你負責連接這些計算機，任務是使任意兩臺計算機都連通（不管是直接的或間接的）。【輸入格式】輸入文件wire.in，第一行為整數(shù)n（2<=n<=100），表示計算機的數(shù)目。此后的n行，每行n個整數(shù)。第x+1行y列的整數(shù)表示直接連接第x臺計算機和第y臺計算機的費用?！据敵龈袷健枯敵鑫募ire.out，一個整數(shù)，表示最小的連接費用。【輸入樣例】3012101210【輸出樣例】2（注：表示連接1和2，2和3，費用為2）【例1】、最優(yōu)布線問題57【參考程序】#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intg[101][101];//鄰接矩陣intminn[101];//minn[i]存放藍點i與白點相連的最小邊權boolu[101];//u[i]=True，表示頂點i還未加入到生成樹中//u[i]=False，表示頂點i已加入到生成樹中intn,i,j;intmain(){cin>>n;for(i=1;i<=n;i++)for(j=1;j<=n;j++)cin>>g[i][j];memset(minn,0x7f,sizeof(minn));//初始化為maxintminn[1]=0;memset(u,1,sizeof(u));//初始化為True，表示所有頂點為藍點【參考程序】58for(i=1;i<=n;i++){intk=0;for(j=1;j<=n;j++)//找一個與白點相連的權值最小的藍點kif(u[j]&&(minn[j]<minn[k]))k=j;u[k]=false;//藍點k加入生成樹，標記為白點for(j=1;j<=n;j++)//修改與k相連的所有藍點if(u[j]&&(g[k][j]<minn[j]))minn[j]=g[k][j];}inttotal=0;for(i=1;i<=n;i++)//累加權值total+=minn[i];cout<<total<<endl;return0;}知識擴展：本算法在移動通信、智能交通、移動物流、生產(chǎn)調度等物聯(lián)網(wǎng)相關領域都有十分現(xiàn)實的意義，采用好的算法，就能節(jié)省成本提高效率。for(i=1;i<=n;i++)59

【引例】有一張城市地圖，圖中的頂點為城市，無向邊代表兩個城市間的連通關系，邊上的權為在這兩個城市之間修建高速公路的造價，研究后發(fā)現(xiàn)，這個地圖有一個特點，即任一對城市都是連通的?，F(xiàn)在的問題是，要修建若干高速公路把所有城市聯(lián)系起來，問如何設計可使得工程的總造價最少？12345212896731012345212896731060Kruskal算法Kruskal（克魯斯卡爾）算法是一種巧妙利用并查集來求最小生成樹的算法。

Kruskal算法將一個連通塊當做一個集合。Kruskal首先將所有的邊按從小到大順序排序（一般使用快排），并認為每一個點都是孤立的，分屬于n個獨立的集合。然后按順序枚舉每一條邊。如果這條邊連接著兩個不同的集合，那么就把這條邊加入最小生成樹，這兩個不同的集合就合并成了一個集合；如果這條邊連接的兩個點屬于同一集合，就跳過。直到選取了n-1條邊為止。123452128967310Kruskal算法Kruskal（克魯斯卡爾）算法是一種61思想講解：Kruskal（克魯斯卡爾）算法開始時，認為每一個點都是孤立的，分屬于n個獨立的集合。1234521289673105個集合{{1}，{2}，{3}，{4}，{5}}生成樹中沒有邊Kruskal每次都選擇一條最小的邊，而且這條邊的兩個頂點分屬于兩個不同的集合。將選取的這條邊加入最小生成樹，并且合并集合。1234521289673105個集合{{1}，{2}，{62第一次選擇的是<1,2>這條邊，將這條邊加入到生成樹中，并且將它的兩個頂點1、2合并成一個集合。1234521289673104個集合{{1，2}，{3}，{4}，{5}}生成樹中有一條邊{<1,2>}第二次選擇的是<4,5>這條邊，將這條邊加入到生成樹中，并且將它的兩個頂點4、5合并成一個集合。1234521289673103個集合{{1，2}，{3}，{4，5}}生成樹中有2條邊{<1,2>，<4,5>}第一次選擇的是<1,2>這條邊，將這條邊加入到生成樹中，并且63第三次選擇的是<3,5>這條邊，將這條邊加入到生成樹中，并且將它的兩個頂點3、5所在的兩個集合合并成一個集合1234521289673102個集合{{1，2}，{3，4，5}}生成樹中有3條邊{<1,2>，<4,5>，<3，5>}第四次選擇的是<2,5>這條邊，將這條邊加入到生成樹中，并且將它的兩個頂點2、5所在的兩個集合合并成一個集合。1234521289673101個集合{{1，2，3，4，5}}生成樹中有4條邊{<1,2>，<4,5>，<3，5>，<2,5>}第三次選擇的是<3,5>這條邊，將這條邊加入到生成樹中，并且64

算法結束，最小生成樹權值為19。通過上面的模擬能夠看到，Kruskal算法每次都選擇一條最小的，且能合并兩個不同集合的邊，一張n個點的圖總共選取n-1次邊。因為每次我們選的都是最小的邊，所以最后的生成樹一定是最小生成樹。每次我們選的邊都能夠合并兩個集合，最后n個點一定會合并成一個集合。通過這樣的貪心策略，Kruskal算法就能得到一棵有n-1條邊，連接著n個點的最小生成樹。

Kruskal算法的時間復雜度為O(E*logE)，E為邊數(shù)。

65算法描述:初始化并查集。father[x]=x。tot=0將所有邊用快排從小到大排序。計數(shù)器k=0;for(i=1;i<=M;i++)//循環(huán)所有已從小到大排序的邊

if這是一條u,v不屬于同一集合的邊(u,v)(因為已經(jīng)排序，所以必為最小)

begin

①合并u,v所在的集合，相當于把邊(u,v)加入最小生成樹。

②tot=tot+W(u,v)

③k++

④如果k=n-1,說明最小生成樹已經(jīng)生成，則break;end;6.結束，tot即為最小生成樹的總權值之和。算法描述:66【例2】、最短網(wǎng)絡Agri-Net【問題描述】農(nóng)民約翰被選為他們鎮(zhèn)的鎮(zhèn)長！他其中一個競選承諾就是在鎮(zhèn)上建立起互聯(lián)網(wǎng)，并連接到所有的農(nóng)場。當然，他需要你的幫助。約翰已經(jīng)給他的農(nóng)場安排了一條高速的網(wǎng)絡線路，他想把這條線路共享給其他農(nóng)場。為了用最小的消費，他想鋪設最短的光纖去連接所有的農(nóng)場。你將得到一份各農(nóng)場之間連接費用的列表，你必須找出能連接所有農(nóng)場并所用光纖最短的方案。每兩個農(nóng)場間的距離不會超過100000。【輸入格式】第一行：農(nóng)場的個數(shù)，N（3<=N<=100）。第二行..結尾后來的行包含了一個N*N的矩陣,表示每個農(nóng)場之間的距離。理論上，他們是N行，每行由N個用空格分隔的數(shù)組成，實際上，他們限制在80個字符，因此，某些行會緊接著另一些行。當然，對角線將會是0，因為不會有線路從第i個農(nóng)場到它本身?！据敵龈袷健?/p>

只有一個輸出，其中包含連接到每個農(nóng)場的光纖的最小長度?！据斎霕永縜grinet.in40492140817980162117160【輸出樣例】agrinet.out

28【例2】、最短網(wǎng)絡Agri-Net第一行：農(nóng)場的個數(shù)，67【參考程序】#include<cstdio>#include<iostream>#include<algorithm>//sort()需要用到<algorithm>庫usingnamespacestd;structpoint{intx;inty;intv;};

//定義結構類型，表示邊pointa[9901];

//存邊intfat[101];intn,i,j,x,m,tot,k;intfather(intx){if(fat[x]!=x)fat[x]=father(fat[x]);returnfat[x];}voidunionn(intx,inty){intfa=father(x);intfb=father(y);if(fa!=fb)fat[fa]=fb;}【參考程序】68intcmp(constpoint&a,constpoint&b)//sort()自定義的比較函數(shù){if(a.v<b.v)return1;elsereturn0;}intmain(){cin>>n;for(i=1;i<=n;i++)for(j=1;j<=n;j++){cin>>x;if(x!=0){m++;a[m].x=i;a[m].y=j;a[m].v=x;}}for(i=1;i<=n;i++)fat[i]=i;sort(a+1,a+m+1,cmp);//C++標準庫中自帶的快排

//cmp為自定義的比較函數(shù)。表示a數(shù)組的1-m按規(guī)則cmp排序intcmp(constpoint&a,constp69for(i=1;i<=m;i++){if(father(a[i].x)!=father(a[i].y)){unionn(a[i].x,a[i].y);tot+=a[i].v;k++;}if(k==n-1)break;}cout<<tot;return0;}最小生成樹和拓撲排序課件70上機練習1、局域網(wǎng)【問題描述】某個局域網(wǎng)內有n(n<=100)臺計算機，由于搭建局域網(wǎng)時工作人員的疏忽，現(xiàn)在局域網(wǎng)內的連接形成了回路，我們知道如果局域網(wǎng)形成回路那么數(shù)據(jù)將不停的在回路內傳輸，造成網(wǎng)絡卡的現(xiàn)象。因為連接計算機的網(wǎng)線本身不同，所以有一些連線不是很暢通，我們用f(i,j)表示i,j之間連接的暢通程度(f(i,j)<=1000)，f(i,j)值越小表示i,j之間連接越通暢，f(i,j)為0表示i,j之間無網(wǎng)線連接?，F(xiàn)在我們需要解決回路問題，我們將除去一些連線，使得網(wǎng)絡中沒有回路，并且被除去網(wǎng)線的Σf(i,j)最大，請求出這個最大值?！据斎敫袷健康谝恍袃蓚€正整數(shù)nk接下來的k行每行三個正整數(shù)ijm表示i,j兩臺計算機之間有網(wǎng)線聯(lián)通，通暢程度為m?！据敵龈袷健恳粋€正整數(shù)，Σf(i,j)的最大值【輸入輸出樣例】【輸入樣例】【輸出樣例】551281311532453428上機練習1、局域網(wǎng)【輸入樣例】【輸出樣例】5515712、繁忙的都市【問題描述】城市C是一個非常繁忙的大都市，城市中的道路十分的擁擠，于是市長決定對其中的道路進行改造。城市C的道路是這樣分布的：城市中有n個交叉路口，有些交叉路口之間有道路相連，兩個交叉路口之間最多有一條道路相連接。這些道路是雙向的，且把所有的交叉路口直接或間接的連接起來了。每條道路都有一個分值，分值越小表示這個道路越繁忙，越需要進行改造。但是市政府的資金有限，市長希望進行改造的道路越少越好，于是他提出下面的要求：改造的那些道路能夠把所有的交叉路口直接或間接的連通起來。在滿足要求1的情況下，改造的道路盡量少。在滿足要求1、2的情況下，改造的那些道路中分值最大值盡量小?！揪幊倘蝿铡孔鳛槭幸?guī)劃局的你，應當作出最佳的決策，選擇那些道路應當被修建?！据斎敫袷健縞ity.in第一行有兩個整數(shù)n,m表示城市有n個交叉路口，m條道路。接下來m行是對每條道路的描述，u,v,c表示交叉路口u和v之間有道路相連，分值為c。(1≤n≤300，1≤c≤10000)【輸出格式】city.out兩個整數(shù)s,max，表示你選出了幾條道路，分值最大的那條道路的分值是多少?！据斎胼敵鰳永俊据斎霕永俊据敵鰳永?5123145247236348362、繁忙的都市【輸入樣例】【輸出樣例】452363723、聯(lián)絡員【問題描述】

Tyvj已經(jīng)一歲了，網(wǎng)站也由最初的幾個用戶增加到了上萬個用戶，隨著Tyvj網(wǎng)站的逐步壯大，管理員的數(shù)目也越來越多，現(xiàn)在你身為Tyvj管理層的聯(lián)絡員，希望你找到一些通信渠道，使得管理員兩兩都可以聯(lián)絡（直接或者是間接都可以）。Tyvj是一個公益性的網(wǎng)站，沒有過多的利潤，所以你要盡可能的使費用少才可以。目前你已經(jīng)知道，Tyvj的通信渠道分為兩大類，一類是必選通信渠道，無論價格多少，你都需要把所有的都選擇上；還有一類是選擇性的通信渠道，你可以從中挑選一些作為最終管理員聯(lián)絡的通信渠道。數(shù)據(jù)保證給出的通行渠道可以讓所有的管理員聯(lián)通。【輸入格式】

第一行n，m表示Tyvj一共有n個管理員，有m個通信渠道第二行到m+1行，每行四個非負整數(shù)，p,u,v,w當p=1時，表示這個通信渠道為必選通信渠道；當p=2時，表示這個通信渠道為選擇性通信渠道；u,v,w表示本條信息描述的是u，v管理員之間的通信渠道，u可以收到v的信息，v也可以收到u的信息，w表示費用?！据敵龈袷健?/p>

最小的通信費用。3、聯(lián)絡員73561121123113411411225102255【輸入樣例】【輸出樣例】9樣例解釋：1-2-3-4-1存在四個必選渠道，形成一個環(huán)，互相可以到達。需要讓所有管理員聯(lián)通，需要聯(lián)通2和5號管理員，選擇費用為5的渠道，所以總的費用為9注意：u,v之間可能存在多條通信渠道，你的程序應該累加所有u,v之間的必選通行渠道數(shù)據(jù)范圍：對于30%的數(shù)據(jù)，n<=10m<=100對于50%的數(shù)據(jù),n<=200m<=1000對于100%的數(shù)據(jù)，n<=2000m<=1000056【輸入樣例】【輸出樣例】樣例解釋：74拓撲排序拓撲排序75AOV網(wǎng)

在日常生活中，一項大的工程可以看作是由若干個子工程（這些子工程稱為“活動”）組成的集合，這些子工程（活動）之間必定存在一些先后關系，即某些子工程（活動）必須在其它一些子工程（活動）完成之后才能開始，我們可以用有向圖來形象地表示這些子工程（活動）之間的先后關系，子工程（活動）為頂點，子工程（活動）之間的先后關系為有向邊，這種有向圖稱為“頂點活動網(wǎng)絡”，又稱“AOV網(wǎng)”。123567894AOV網(wǎng)12356789476在AOV網(wǎng)中，有向邊代表子工程（活動）的先后關系，我們把一條有向邊起點的活動成為終點活動的前驅活動，同理終點的活動稱為起點活動的后繼活動。而只有當一個活動全部的前驅全部都完成之后，這個活動才能進行。例如在上圖中，只有當工程1完成之后，工程2、3、4、5、6才能開始進行。只有當2、3、4全部完成之后，7才能開始進行。一個AOV網(wǎng)必定是一個有向無環(huán)圖，即不應該帶有回路。否則，會出現(xiàn)先后關系的自相矛盾。1234上圖就是一個出現(xiàn)環(huán)產(chǎn)生自相矛盾的情況。4是1的前驅，想完成1，必須先完成4。3是4的前驅，而2是3的前驅，1又是2的前驅。最后造成想完成1，必須先完成1本身，這顯然出現(xiàn)了矛盾。在AOV網(wǎng)中，有向邊代表子工程（活動）的先后關系，我們把77拓撲排序算法

拓撲排序算法，只適用于AOV網(wǎng)（有向無環(huán)圖）。把AOV網(wǎng)中的所有活動排成一個序列，使得每個活動的所有前驅活動都排在該活動的前面，這個過程稱為“拓撲排序”，所得到的活動序列稱為“拓撲序列”。一個AOV網(wǎng)的拓撲序列是不唯一的，例如下面的這張圖，它的拓撲序列可以是：ABCDE，也可以是ACBDE，或是ADBCE。在下圖所示的AOV網(wǎng)中，工程B和工程C顯然可以同時進行，先后無所謂；但工程E卻要等工程B、C、D都完成以后才能進行。ABCED

構造拓撲序列可以幫助我們合理安排一個工程的進度，由AOV網(wǎng)構造拓撲序列具有很高的實際應用價值。拓撲排序算法拓撲排序算法，只適用于AOV網(wǎng)（有向無78算法思想：構造拓撲序列的拓撲排序算法思想很簡單：1）選擇一個入度為0的頂點并輸出2）然后從AOV網(wǎng)中刪除此頂點及以此頂點為起點的所有關聯(lián)邊；3）重復上述兩步，直到不存在入度為0的頂點為止。4）若輸出的頂點數(shù)小于AOV網(wǎng)中的頂點數(shù)，則輸出“有回路信息”，否則輸出的頂點序列就是一種拓撲序列從第四步可以看出，拓撲排序可以用來判斷一個有向圖是否有環(huán)。只有有向無環(huán)圖才存在拓撲序列。最小生成樹和拓撲排序課件79算法實現(xiàn)：