圖及其基本算法

圖及其基本算法第1頁，共83頁，2023年，2月20日，星期五圖的概念圖（graph）是圖型結(jié)構(gòu)的簡稱。它是一種復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)。圖在各個(gè)領(lǐng)域都著廣泛的應(yīng)用。圖的二元組定義為：G=（V,E）其中V是非空的頂點(diǎn)集合，即V={vi|1<=i<=n,n>=1,vi∈elemtype，n為頂點(diǎn)數(shù)}E是V上頂點(diǎn)的序偶或無序?qū)Φ募?，即對?yīng)邊的集合。第2頁，共83頁，2023年，2月20日，星期五123412453圖1

有向圖圖2

無向圖第3頁，共83頁，2023年，2月20日，星期五圖的基本術(shù)語

1、端點(diǎn)和鄰接點(diǎn)在一個(gè)無向圖中，若存在一條邊（vi，vj），則稱vi,vj為此邊的兩個(gè)端點(diǎn)，并稱它們互為鄰接點(diǎn)（adjacent），即vi是vj的一個(gè)鄰接點(diǎn)，vj也是vi的一個(gè)鄰接點(diǎn)。在一個(gè)有向圖中，若存在一條邊<vi,vj>，則稱此邊是頂點(diǎn)vi的一條出邊（outedge），頂點(diǎn)vj的一條入邊（inedge）；稱Vi為此邊的起始端點(diǎn)，簡稱起點(diǎn)或始點(diǎn)，vj為此邊的終止端點(diǎn)，簡稱終點(diǎn)；稱vi和vj互為鄰接點(diǎn)，并稱vj是vi的出邊鄰接點(diǎn)，vi是vj的入邊鄰接點(diǎn)。第4頁，共83頁，2023年，2月20日，星期五2、頂點(diǎn)的度、入度、出度無向圖頂點(diǎn)v的度（degree）定義為以該頂點(diǎn)為一個(gè)端點(diǎn)的邊的數(shù)目，簡單地說，就是該頂點(diǎn)的邊的數(shù)目，記為D（v）。如圖2中v1頂點(diǎn)的度為2，v2頂點(diǎn)的度為3。有向圖中頂點(diǎn)v的度有入度和出度之分，入度（indegree）是該頂點(diǎn)的入邊的數(shù)目，記為ID（v）；出度（outdegree）是該頂點(diǎn)的出邊的數(shù)目，記為OD（v）頂點(diǎn)v的度等于它的入度和出度之和，即D（v）=ID（v）+OD（v）。第5頁，共83頁，2023年，2月20日，星期五

3、完全圖、稠密圖、稀疏圖若無向圖中的每兩個(gè)頂點(diǎn)之間都存在著一條邊，有向圖中的每兩個(gè)頂點(diǎn)之間都存在著方向相反的兩條邊，則稱此圖為完全圖。顯然，若完全圖是無向的，則圖中包含有n（n-1）/2條邊,若完全圖是有向的，則圖中包含有n（n-1）條邊。當(dāng)一個(gè)圖接近完全圖時(shí)，則可稱為稠密圖，相反地，當(dāng)一個(gè)圖有較少的邊數(shù)（即e<<n（n–1））時(shí)，則可稱為稀疏圖。第6頁，共83頁，2023年，2月20日，星期五12543G112543G212543G3第7頁，共83頁，2023年，2月20日，星期五

4、子圖設(shè)有兩個(gè)圖G=（V,E）和G’＝（V’,E’）,若V’是V的子集，且E’是E的子集，則稱G’是G的子圖。12453124531245圖圖的子圖第8頁，共83頁，2023年，2月20日，星期五5、路徑和回路在一個(gè)圖G中，從頂點(diǎn)v到頂點(diǎn)v’的一條路徑（path）是一個(gè)頂點(diǎn)序列vi0,vi1,vi2,...,vim,其中v=vi0,v’=vim,若此圖是無向圖，則（vi,j-1,vij）∈E（G），（1≤j≤m）；若此圖是有向圖，則<vi,j-1,vij>∈E（G），（1≤j≤m）。路徑長度是指該路徑上經(jīng)過的邊的數(shù)目。若一條路徑上除了前后端點(diǎn)可以相同外，所有頂點(diǎn)均不同，則稱此路徑為簡單路徑。若一條路徑上的前后兩端點(diǎn)相同，則被稱為回路或環(huán)（cycle），前后兩端點(diǎn)相同的簡單路徑被稱為簡單回路或簡單環(huán)。第9頁，共83頁，2023年，2月20日，星期五6、連通和連通分量在無向圖G中，若從頂點(diǎn)vi到頂點(diǎn)vj有路徑，則稱vi和vj是連通的。若圖G中任意兩個(gè)頂點(diǎn)都連通，則稱G為連通圖，否則稱為非連通圖。無向圖G的極大連通子圖稱為G的連通分量。顯然，任何連通圖的連通分量只有一個(gè)，即本身，而非連通圖有多個(gè)連通分量。第10頁，共83頁，2023年，2月20日，星期五1254376G11254G1136G127G13第11頁，共83頁，2023年，2月20日，星期五7、強(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)連通分量。顯然，強(qiáng)連通圖只有一個(gè)強(qiáng)連通分量，即本身，非強(qiáng)連通圖有多個(gè)強(qiáng)連通分量。第12頁，共83頁，2023年，2月20日，星期五12543G112543G2125G2143G22第13頁，共83頁，2023年，2月20日，星期五8、權(quán)和網(wǎng)在一個(gè)圖中．每條邊可以標(biāo)上具有某種含義的數(shù)值，此數(shù)值稱為該邊的權(quán)（weight）。例如，對于一個(gè)反映城市交通線路的圖，邊上的權(quán)可表示該條線路的長度或等級；對于一個(gè)反映電子線路的圖，邊上的權(quán)可表示兩端點(diǎn)間的電阻、電流或電壓；對于一個(gè)反映零件裝配的圖，邊上的權(quán)可表示一個(gè)端點(diǎn)需要裝配另一個(gè)端點(diǎn)的零件的數(shù)量；對于一個(gè)反映工程進(jìn)度的圖，邊上的權(quán)可表示從前一子工程到后一子工程所需要的天數(shù)。邊上帶有權(quán)的圖稱作帶權(quán)圖，也常稱作網(wǎng)（network）。第14頁，共83頁，2023年，2月20日，星期五

圖的存儲結(jié)構(gòu)

1、鄰接矩陣鄰接矩陣（adjacencymatrix）是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G＝（V，E）是具有n個(gè)頂點(diǎn)的圖，頂點(diǎn)序號依次為1、2、···、n，則G的鄰接矩陣是具有如下定義的n階方陣。第15頁，共83頁，2023年，2月20日，星期五鄰接矩陣的表示1234有向圖12453無向圖第16頁，共83頁，2023年，2月20日，星期五2、鄰接表鄰接表（adjacencylist）是對圖中的每個(gè)頂點(diǎn)建立一個(gè)鄰接關(guān)系的單鏈表，并把它們的表頭指針用向量存儲的一種圖的表示方法。為頂點(diǎn)vi建立的鄰接關(guān)系的單鏈表又稱作vi的鄰接表。vi鄰接表中的每個(gè)結(jié)點(diǎn)用來存儲以該頂點(diǎn)為端點(diǎn)或起點(diǎn)的一條邊的信息，因而被稱為邊結(jié)點(diǎn)。vi鄰接表中的結(jié)點(diǎn)數(shù)，對于無向圖來說，等于vi的邊數(shù)，鄰接點(diǎn)數(shù)或度數(shù)；對于有向圖來說，等于vi的出邊數(shù)、出邊鄰接點(diǎn)數(shù)或出度數(shù)。第17頁，共83頁，2023年，2月20日，星期五鄰接表描述邊結(jié)點(diǎn)：

Eptr=^enode;Eode=recordadjvex:1..n;w:wtype;next:eptrend;vexnode=recorddata:datatypelink:eptr;end;Adjlnk=array[1..n]ofvexnode;Proccreate(G)Fori:=1tondobegininput(g[i].data);g[i].link:=nil;end;Fork:=1toedobegininput(i,j);new(s);s^.adjvex:=j;s^.next:=g[i].link;g[i].link:=s;end;第18頁，共83頁，2023年，2月20日，星期五1234有向圖1234^23^4^1^有向圖鄰接表12453無向圖42^535431^32^12351^2^無向圖鄰接表4第19頁，共83頁，2023年，2月20日，星期五3、邊集數(shù)組邊集數(shù)組（edgesetarray）是利用一維數(shù)組存儲圖中所有邊的一種圖的表示方法。該數(shù)組中所含元素的個(gè)數(shù)要大于等于圖中邊的條數(shù)，每個(gè)元素用來存儲一條邊的起點(diǎn)、終點(diǎn)（對于無向圖，可選定邊的任一端點(diǎn)為起點(diǎn)或終點(diǎn)）和權(quán)（若有的話），下各邊在數(shù)組中的次序可任意安排，也可根據(jù)具體要求而定。第20頁，共83頁，2023年，2月20日，星期五

圖的遍歷

1、深度優(yōu)先遍歷深度優(yōu)先搜索（depthfirstsearch）遍歷類似樹的先根遍歷，它是一個(gè)遞歸過程.可敘述為：首先訪問一個(gè)頂點(diǎn)vi（開始為初始點(diǎn)），并將其標(biāo)記為已訪問過，然后從vi的一個(gè)未被訪問的鄰接點(diǎn)（無向圖）或出邊鄰接點(diǎn)（有向圖）出發(fā)進(jìn)行深度優(yōu)先搜索遍歷，當(dāng)vi的所有鄰接點(diǎn)均被訪問過時(shí)，則退回到上一個(gè)頂點(diǎn)vk，從vk的另一個(gè)未被訪問過的鄰接點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。算法：procdfs(v)beignprint(v);visited[v]:=true;forj:=1tondoifnotvisited[j]andg[v,j]=1thendfs(j);end第21頁，共83頁，2023年，2月20日，星期五練習(xí)1：無向圖的深度優(yōu)先搜索【問題描述】從文件中讀入無向圖的信息，按深度優(yōu)先搜索的方式遍歷圖中的每一個(gè)結(jié)點(diǎn)，并按訪問的現(xiàn)后順序?qū)⒔Y(jié)點(diǎn)輸出，以V1作為第一個(gè)訪問的結(jié)點(diǎn)。【輸入文件】第一行兩個(gè)整數(shù)m和n，分別表示圖的結(jié)點(diǎn)數(shù)和圖中的邊數(shù)。以下n行表示n條邊：每一行兩個(gè)數(shù)x和y，表示x與y之間有一條邊?！据敵鑫募恳恍校航Y(jié)點(diǎn)的序列。

【示例】

輸入：輸出：

55125341213253545第22頁，共83頁，2023年，2月20日，星期五2、廣度優(yōu)先搜索遍歷廣度優(yōu)先搜索（breadth—firstsearch）遍歷類似樹的按層遍歷，其過程為：首先訪問初始點(diǎn)vi,并將其標(biāo)記為已訪問過，接著訪問vi的所有未被訪問過的鄰接點(diǎn)vi1,vi2,···,vit并均標(biāo)記為已訪問過，然后再按照vi1,vi2,···,vit的次序，訪問每一個(gè)頂點(diǎn)的所有未被訪問過的鄰接點(diǎn)，并均標(biāo)記為已訪問過，依次類推，直到圖中所有和初始點(diǎn)vi有路徑相通的頂點(diǎn)都被訪問過為止。算法：procbfs(v)beginsetnull(Q);print(v);visited[v]:=true;insert(Q,v);repeath:=delete(Q);forj:=1tondoifnotvisited[j]andg[h,j]=1thenbeginprint(j);visited[j]:=true;insert(Q,j);end;untilempty(Q);end;第23頁，共83頁，2023年，2月20日，星期五練習(xí)2：無向圖的廣度優(yōu)先搜索【問題描述】從文件中讀入無向圖的信息，按廣度優(yōu)先搜索的方式遍歷圖中的每一個(gè)結(jié)點(diǎn)，并按訪問的現(xiàn)后順序?qū)⒔Y(jié)點(diǎn)輸出，以V1作為第一個(gè)訪問的結(jié)點(diǎn)。【輸入文件】第一行兩個(gè)整數(shù)m和n，分別表示圖的結(jié)點(diǎn)數(shù)和圖中的邊數(shù)。以下n行表示n條邊：每一行兩個(gè)數(shù)x和y，表示x與y之間有一條邊?！据敵鑫募恳恍校航Y(jié)點(diǎn)的序列。

【示例】

輸入：輸出：

55123541213253545第24頁，共83頁，2023年，2月20日，星期五非連通圖的遍歷前面提到的深度優(yōu)先遍歷和廣度優(yōu)先遍歷都只從圖的一個(gè)頂點(diǎn)開始進(jìn)行一次遍歷，對于連通圖可以遍歷到圖的所有結(jié)點(diǎn)，但如果圖不連通，則有一部分結(jié)點(diǎn)無法訪問到。修改很簡單，每次選取任意一個(gè)沒有被遍歷過的結(jié)點(diǎn)開始一次遍歷，重復(fù)此操作直到遍歷完圖的所有結(jié)點(diǎn)即可。第25頁，共83頁，2023年，2月20日，星期五procbfs(v)beginsetnull(Q);print(v);visited[v]:=true;flag:=flase;{圖中頂點(diǎn)是否訪問完}whilenotflagdobeginflag:=true;insert(Q,v);repeath:=delete(Q);forj:=1tondoifnotvisited[j]andg[h,j]=1thenbeginprint(j);visited[j]:=true;insert(Q,j);end;untilempty(Q);forj:=1tondoifvisited[j]=falsethenbeginv:=j;flag:=false;end;end;end;非連通圖的遍歷第26頁，共83頁，2023年，2月20日，星期五圖的連通分量對于連通圖只有一個(gè)連通分量；對于非連通圖有多個(gè)連通分量。如右圖：有兩個(gè)連通分量，它們分別是：1，2，34，512345第27頁，共83頁，2023年，2月20日，星期五求連通分量的算法procbfs(v)beginsetnull(Q);print(v);visited[v]:=true;flag:=flase;{圖中頂點(diǎn)是否訪問完}whilenotflagdobeginflag:=true;insert(Q,v);repeath:=delete(Q);添加操作：將每一個(gè)出隊(duì)的頂點(diǎn)保存；

forj:=1tondoifnotvisited[j]andg[h,j]=1thenbeginprint(j);visited[j]:=true;insert(Q,j);end;untilempty(Q);

//repeat..until循環(huán)結(jié)束一次，得到一個(gè)連通分量；forj:=1tondoifvisited[j]=falsethenbeginv:=j;flag:=false;end;end;end;第28頁，共83頁，2023年，2月20日，星期五練習(xí)3：求無向圖的連通分量【問題描述】從文件中讀入無向圖的信息，求出該圖的連通分量個(gè)數(shù)?！据斎胛募康谝恍袃蓚€(gè)整數(shù)m和n，分別表示圖的結(jié)點(diǎn)數(shù)和圖中的邊數(shù)。以下n行表示n條邊：每一行兩個(gè)數(shù)x和y，表示x與y之間有一條邊?！据敵鑫募枯敵鲆粋€(gè)整數(shù)，表示連通分量的個(gè)數(shù)。

【示例】

輸入：輸出：

5521213253523第29頁，共83頁，2023年，2月20日，星期五有向圖的強(qiáng)連通圖分量定義：在有向圖G中，如果兩個(gè)頂點(diǎn)間至少存在一條路徑，稱兩個(gè)頂點(diǎn)強(qiáng)連通(stronglyconnected)。如果有向圖G的每兩個(gè)頂點(diǎn)都強(qiáng)連通，稱G是一個(gè)強(qiáng)連通圖。非強(qiáng)連通圖有向圖的極大強(qiáng)連通子圖，稱為強(qiáng)連通分量(stronglyconnectedcomponents)。下圖中，子圖{1,2,3,4}為一個(gè)強(qiáng)連通分量，因?yàn)轫旤c(diǎn)1,2,3,4兩兩可達(dá)。{5},{6}也分別是兩個(gè)強(qiáng)連通分量。第30頁，共83頁，2023年，2月20日，星期五Tarjan算法Tarjan算法是基于對圖深度優(yōu)先搜索的算法，每個(gè)強(qiáng)連通分量為搜索樹中的一棵子樹。搜索時(shí)，把當(dāng)前搜索樹中未處理的節(jié)點(diǎn)加入一個(gè)堆棧，回溯時(shí)可以判斷棧頂?shù)綏Ｖ械墓?jié)點(diǎn)是否為一個(gè)強(qiáng)連通分量。定義DFN(u)為節(jié)點(diǎn)u搜索的次序編號(時(shí)間戳)，Low(u)為u或u的子樹能夠追溯到的最早的棧中節(jié)點(diǎn)的次序號。由定義可以得出：

Low(u)=Min{DFN(u),Low(v),(u,v)為樹枝邊，u為v的父節(jié)點(diǎn)

DFN(v),(u,v)為指向棧中節(jié)點(diǎn)的后向邊(非橫叉邊)—指向其祖先的邊

橫叉邊---從一個(gè)連通分量到另一個(gè)連通分量之間的邊}

當(dāng)DFN(u)=Low(u)時(shí)，以u為根的搜索子樹上所有節(jié)點(diǎn)是一個(gè)強(qiáng)連通分量（當(dāng)前遞歸棧內(nèi)存在一個(gè)SCC）。第31頁，共83頁，2023年，2月20日，星期五算法偽代碼如下：tarjan(u){ DFN[u]=Low[u]=++Index//為節(jié)點(diǎn)u設(shè)定次序編號和Low初值

Stack.push(u)//將節(jié)點(diǎn)u壓入棧中

foreach(u,v)inE//枚舉每一條邊

if(visnotvisted)//如果節(jié)點(diǎn)v未被訪問過---說明是樹枝

tarjan(v)//繼續(xù)向下找

Low[u]=min(Low[u],Low[v]) elseif(vinS)//如果節(jié)點(diǎn)v還在棧內(nèi)—說明是后向邊

Low[u]=min(Low[u],DFN[v])//if(visvistedandvnotinS)---(u,v)是橫叉邊 if(DFN[u]==Low[u])//如果節(jié)點(diǎn)u是強(qiáng)連通分量的根

repeat v=S.pop//將v退棧，為該強(qiáng)連通分量中一個(gè)頂點(diǎn)

printv until(u==v)}第32頁，共83頁，2023年，2月20日，星期五算法流程的演示：從節(jié)點(diǎn)1開始DFS，把遍歷到的節(jié)點(diǎn)加入棧中。搜索到節(jié)點(diǎn)u=6時(shí)，DFN[6]=LOW[6]，找到了一個(gè)強(qiáng)連通分量。退棧到u=v為止，{6}為一個(gè)強(qiáng)連通分量。返回節(jié)點(diǎn)5，發(fā)現(xiàn)DFN[5]=LOW[5]，退棧后{5}為一個(gè)強(qiáng)連通分量。第33頁，共83頁，2023年，2月20日，星期五返回節(jié)點(diǎn)3，繼續(xù)搜索到節(jié)點(diǎn)4，把4加入堆棧。發(fā)現(xiàn)節(jié)點(diǎn)4向節(jié)點(diǎn)1有后向邊，節(jié)點(diǎn)1還在棧中，所以LOW[4]=1。節(jié)點(diǎn)6已經(jīng)出棧，(4,6)是橫叉邊，返回3，(3,4)為樹枝邊，所以LOW[3]=LOW[4]=1。繼續(xù)回到節(jié)點(diǎn)1，最后訪問節(jié)點(diǎn)2。訪問邊(2,4)，4還在棧中，所以LOW[2]=DFN[4]=5。返回1后，發(fā)現(xiàn)DFN[1]=LOW[1]，把棧中節(jié)點(diǎn)全部取出，組成一個(gè)連通分量{1,3,4,2}。運(yùn)行Tarjan算法的過程中，每個(gè)頂點(diǎn)都被訪問了一次，且只進(jìn)出了一次堆棧，每條邊也只被訪問了一次，所以該算法的時(shí)間復(fù)雜度為O(N+M)。第34頁，共83頁，2023年，2月20日，星期五每一頭牛的愿望就是變成一頭最受歡迎的牛?，F(xiàn)在有N頭牛，給你M對整數(shù)(A,B)，表示牛A認(rèn)為牛B受歡迎。這種關(guān)系是具有傳遞性的，如果A認(rèn)為B受歡迎，B認(rèn)為C受歡迎，那么牛A也認(rèn)為牛C受歡迎。你的任務(wù)是求出有多少頭牛被所有的牛認(rèn)為是受歡迎的?！据斎胛募康谝恍袃蓚€(gè)數(shù)N,M。接下來M行，每行兩個(gè)數(shù)A,B，意思是A認(rèn)為B是受歡迎的（給出的信息有可能重復(fù)，即有可能出現(xiàn)多個(gè)A,B）【輸出文件】一個(gè)數(shù)，即有多少頭牛被所有的牛認(rèn)為是受歡迎的?！緲永斎搿?3122123【樣例輸出】1練習(xí)4：受歡迎的牛第35頁，共83頁，2023年，2月20日，星期五圖的生成樹與最小生成樹在一個(gè)連通圖G中，如果取它的全部頂點(diǎn)和一部分邊構(gòu)成一個(gè)子圖G’，即：若邊集E（G’）中的邊既將圖中的所有頂點(diǎn)連通又不形成回路，則稱子圖G’是原圖G的一棵生成樹。最小生成樹：給圖中每個(gè)邊賦一權(quán)值，所有生成樹中所選擇邊的權(quán)值之和最小的生成樹，稱之為最小代價(jià)生成樹，即是最小生成樹。第36頁，共83頁，2023年，2月20日，星期五3124566555136462圖31245651342圖的最小生成樹31245655564圖的非最小生成樹第37頁，共83頁，2023年，2月20日，星期五普里姆算法

假設(shè)G=（V，E）是一個(gè)具有n個(gè)頂點(diǎn)的連通網(wǎng)，T=（U，TE）是G的最小生成樹，其中U是T的頂點(diǎn)集，TE是T的邊集，U和TE的初值均為空集。算法開始時(shí)，首先從V中任取一個(gè)頂點(diǎn)（假定取v1），將它并入U(xiǎn)中，此時(shí)U={v1}，然后只要U是V的真子集，就從那些其一個(gè)端點(diǎn)已在T中，另一個(gè)端點(diǎn)仍在T外的所有邊中，找一條最短（即權(quán)值最?。┻?，假定為（vi，vj），其中，并把該邊（vi，vj）和頂點(diǎn)vj分別并入T的邊集TE和頂點(diǎn)集U，如此進(jìn)行下去，每次往生成樹里并入一個(gè)頂點(diǎn)和一條邊，直到（n一1）次后就把所有n個(gè)頂點(diǎn)都并入到生成樹T的頂點(diǎn)集中，此時(shí)U＝V，TE中含有（n一1）條邊，T就是最后得到的最小生成樹。第38頁，共83頁，2023年，2月20日，星期五普里姆算法的關(guān)鍵之處是：每次如何從生成樹T中到T外的所有邊中，找出一條最短邊。例如，在第k次前，生成樹T中已有k個(gè)頂點(diǎn)和（k-1）條邊，此時(shí)T中到T外的所有邊數(shù)為k（n-k），當(dāng)然它包括兩頂點(diǎn)間沒有直接邊相連，其權(quán)值被看作為“無窮大”的邊在內(nèi)，從如此多的邊中查找最短邊，其時(shí)間復(fù)雜性為O（k（n-k）），顯然是很費(fèi)時(shí)的。是否有一種好的方法能夠降低查找最短邊的時(shí)間復(fù)雜性呢？關(guān)鍵問題第39頁，共83頁，2023年，2月20日，星期五方法是：假定在進(jìn)行第k次前已經(jīng)保留著從T中到T外每一頂點(diǎn)（共（n-k）個(gè)頂點(diǎn)）的各一條最短邊，進(jìn)行第k次時(shí)，首先從這（n-k）條最短邊中，找出一條最最短的邊（它就是從T中到T外的所有邊中的最短邊），假設(shè)為（vi,vj），此步需進(jìn)行（n-k）次比較；然后把邊（vi,vj）和頂點(diǎn)vj分別并入T中的邊集TE和頂點(diǎn)集U中，此時(shí)T外只有n-（k+1）個(gè)頂點(diǎn)，對于其中的每個(gè)頂點(diǎn)vt，若（vj,vt）邊上的權(quán)值小于已保留的從原T中到vt的最短邊的權(quán)值，則用（vj，vt）修改之，使從T中到T外頂點(diǎn)vt的最短邊為（vj，vt），否則原有最短邊保持不變，這樣，就把第k次后從T中到T外每一頂點(diǎn)vt的各一條最短邊都保留下來了。為進(jìn)行第（k+1）次運(yùn)算做好了準(zhǔn)備，此步需進(jìn)行（n-k-1）次比較。所以，利用此方法求第k次的最短邊共需比較2（n-k）-1次，即時(shí)間復(fù)雜性為O（n-k）。解決辦法第40頁，共83頁，2023年，2月20日，星期五prim算法設(shè)一個(gè)輔助數(shù)組closedge，以記錄從U到V-U具有最小代價(jià)的邊。數(shù)組中的每個(gè)元素closedge[v]是記錄類型，包含兩個(gè)域：

closedge[v].lowcast=Min{cost(u,v)|u∈U};closedge[v].vex存儲該邊依附的在U中的頂點(diǎn)。第41頁，共83頁，2023年，2月20日，星期五代碼procmintree_prim(gn:adjmatrix;u0:integer);beginforv:=1tondoifv<>u0thenwithclosedage[v]do[vex:=u0;lowcast:=gn[u0,v];]closedge[u0].lowcast:=0;{并入U(xiǎn)集合}fori:=1ton-1dobegink:=min(closedge);{尋找代價(jià)最小的邊}write(closedge[k].vex,k);第42頁，共83頁，2023年，2月20日，星期五

closedge[k].lowcast:=0;{并入U(xiǎn)集合}forv:=1tondoifgn[k,v]<closedge[v].lowcastthenbeginclosedge[v].lowcast:=gn[k,v];closedge[v].vex:=k;end;

end;end;第43頁，共83頁，2023年，2月20日，星期五練習(xí)1：prim算法實(shí)現(xiàn)【問題描述】從文件中讀入連通帶權(quán)圖的信息，按prim算法求出該圖的最小生成樹，以V1作為初始結(jié)點(diǎn)?！据斎胛募康谝恍袃蓚€(gè)整數(shù)m和n，分別表示圖的結(jié)點(diǎn)數(shù)和圖中的邊數(shù)。以下n行表示n條邊：每一行三個(gè)數(shù)x、y和k，k表示x與y之間邊的權(quán)值?！据敵鑫募抗瞞行，第一行：最小生成樹的權(quán)；以下m-1行表示選取的邊，邊的第1個(gè)結(jié)點(diǎn)小于第2個(gè)結(jié)點(diǎn)，并按結(jié)點(diǎn)由小到大輸出。

【示例】

輸入：輸出：

57451217142330151452424103534243571523第44頁，共83頁，2023年，2月20日，星期五練習(xí)2：EddypaintingEddybeginstolikepaintingpicturesrecently,heissureofhimselftobecomeapainter.EverydayEddydrawspicturesinhissmallroom,andheusuallyputsouthisnewestpicturestolethisfriendsappreciate.buttheresultitcanbeimagined,thefriendsarenotinterestedinhispicture.Eddyfeelsverypuzze,inordertochangeallfriends'sviewtohistechnicalofpaintingpictures,soEddycreatesaproblemforthehisfriendsofyou.

Problemdescriptionsasfollows:Givenyousomecoordinatespiontsonadrawingpaper,everypointlinkswiththeinkwiththestraightline,causesallpointsfinallytolinkinthesameplace.Howmanydistantsdoesyourdutydiscovertheshortestlengthwhichtheinkdraws?Input：Thefirstlinecontains0<n<=100,thenumberofpoint.Foreachpoint,alinefollows;eachfollowinglinecontainstworealnumbersindicatingthe(x,y)coordinatesofthepoint.

Inputcontainsmultipletestcases.Processtotheendoffile.Output：Yourprogramprintsasinglerealnumbertotwodecimalplaces:theminimumtotallengthofinklinesthatcanconnectallthepoints.SampleInput：31.01.02.02.02.04.0SampleOutput：3.41第45頁，共83頁，2023年，2月20日，星期五

克魯斯卡爾算法假設(shè)G＝（V，E）是一個(gè)具有n個(gè)頂點(diǎn)的連通網(wǎng)，T＝（U，TE）是G的最小生成樹，U的初值等于V，即包含有G中的全部頂點(diǎn)，TE的初值為空。此算法的基本思想是，將圖G中的邊按權(quán)值從小到大的順序依次選取，若選取的邊使生成樹T不形成回路，則把它并入TE中，保留作為T的一條邊，若選取的邊使生成樹T形成回路，則將其舍棄，如此進(jìn)行下去，直到TE中包含有n－1條邊為止。此時(shí)的T即為最小生成樹。第46頁，共83頁，2023年，2月20日，星期五克魯斯卡爾算法的關(guān)鍵之處是：如何判斷欲加入的一條邊是否與生成樹中已選取的邊形成回路。這可將各頂點(diǎn)劃分為所屬集合的方法來解決，每個(gè)集合中的頂點(diǎn)表示一個(gè)無回路的連通分量。算法開始時(shí)，由于生成樹的頂點(diǎn)集等于圖G的頂點(diǎn)集，邊集為空，所以n個(gè)頂點(diǎn)分屬于n個(gè)集合。每個(gè)集合中只有一個(gè)頂點(diǎn)，表明頂點(diǎn)之問互不連通。關(guān)鍵問題第47頁，共83頁，2023年，2月20日，星期五Kruskal算法procmintree_krusk(gn:adjmatrix);beginfori:=1tondoun[i]:=i;fori:=1ton-1dobeginminedge(a,b);write(a,b,gn[a,b]);k:=un[b];fori:=1tondo{兩個(gè)連通分量合并}ifun[i]=kthenun[i]:=un[a];end;end;procminedge(vara:integer;varb:integer);用于在剩下的邊中選取不再同一連通分量上的最小代價(jià)的邊，邊的結(jié)點(diǎn)分別為a和b。為了實(shí)現(xiàn)該過程，可以將圖中的邊生成邊結(jié)點(diǎn)（包含兩個(gè)頂點(diǎn)和代價(jià)）數(shù)組，由小到大排序，然后通過排序后的數(shù)組進(jìn)行處理；un數(shù)組：用來記載隨著邊的加入，各頂點(diǎn)屬于哪個(gè)連通分量。第48頁，共83頁，2023年，2月20日，星期五練習(xí)3：Kruskal算法實(shí)現(xiàn)【問題描述】從文件中讀入連通帶權(quán)圖的信息，按Kruskal算法求出該圖的最小生成樹，以V1作為初始結(jié)點(diǎn)?！据斎胛募康谝恍袃蓚€(gè)整數(shù)m和n，分別表示圖的結(jié)點(diǎn)數(shù)和圖中的邊數(shù)。以下n行表示n條邊：每一行三個(gè)數(shù)x、y和k，k表示x與y之間邊的權(quán)值?！据敵鑫募抗瞞行，第一行：最小生成樹的權(quán)；以下m-1行表示選取的邊，按選取邊的權(quán)值由小到大輸出。

【示例】

輸入：輸出：

57451217142330351452424101534243571523第49頁，共83頁，2023年，2月20日，星期五練習(xí)4：判斷最小生成樹是否唯一Givenaconnectedundirectedgraph,tellifitsminimumspanningtreeisunique.

Definition1(SpanningTree):Consideraconnected,undirectedgraphG=(V,E).AspanningtreeofGisasubgraphofG,sayT=(V',E'),withthefollowingproperties:

1.V'=V.

2.Tisconnectedandacyclic.

Definition2(MinimumSpanningTree):Consideranedge-weighted,connected,undirectedgraphG=(V,E).TheminimumspanningtreeT=(V,E')ofGisthespanningtreethathasthesmallesttotalcost.ThetotalcostofTmeansthesumoftheweightsonalltheedgesinE'.InputThefirstlinecontainsasingleintegert(1<=t<=20),thenumberoftestcases.Eachcaserepresentsagraph.Itbeginswithalinecontainingtwointegersnandm(1<=n<=100),thenumberofnodesandedges.Eachofthefollowingmlinescontainsatriple(xi,yi,wi),indicatingthatxiandyiareconnectedbyanedgewithweight=wi.Foranytwonodes,thereisatmostoneedgeconnectingthem.OutputForeachinput,iftheMSTisunique,printthetotalcostofit,orotherwiseprintthestring'NotUnique!'.SampleInput23312123231344122232342412SampleOutput3NotUnique!第50頁，共83頁，2023年，2月20日，星期五最短路徑由于從一頂點(diǎn)到另一頂點(diǎn)可能存在著多條路徑。每條路徑上所經(jīng)過的邊數(shù)可能不同，即路徑長度不同，我們把路徑長度最短（即經(jīng)過的邊數(shù)最少）的那條路徑叫做最短路徑，其路徑長度叫做最短路徑長度或最短距離。求圖中一頂點(diǎn)vi到其余各頂點(diǎn)的最短路徑和最短距離比較容易，只要從該頂點(diǎn)vi，出發(fā)對圖進(jìn)行一次廣度優(yōu)先搜索遍歷，在遍歷時(shí)記下每個(gè)結(jié)點(diǎn)的層次即可。第51頁，共83頁，2023年，2月20日，星期五若圖是帶權(quán)圖（假定權(quán)值非負(fù)）從源點(diǎn)vi到終點(diǎn)vj的每條路徑上的權(quán)（它等于該路徑上所經(jīng)邊上的權(quán)值之和，稱為該路徑的帶權(quán)路徑長度）可能不同，我們把權(quán)值最小的那條路徑也稱做最短路徑，其權(quán)值也稱作最短路徑長度或最短距離。實(shí)際上，這兩類最短路徑問題可合并為一類，這只要把第一類的每條邊的權(quán)都設(shè)為1就歸屬于第二類了，所以在以后的討論中，若不特別指明，均是指第二類的最短路徑問題。第52頁，共83頁，2023年，2月20日，星期五求圖的最短路徑問題包括兩個(gè)子問題：一是求圖中一頂點(diǎn)到其余各頂點(diǎn)的最短路徑，二是求圖中每對頂點(diǎn)之間的最短路徑。下面分別進(jìn)行討論。解決問題第53頁，共83頁，2023年，2月20日，星期五從一頂點(diǎn)到其余各頂點(diǎn)的最短路徑迪杰斯特拉（Dijkstra）于1959年提出了解決此問題的一般算法，具體做法是按照從源點(diǎn)到其余每一頂點(diǎn)的最短路徑長度的升序依次求出從源點(diǎn)到各頂點(diǎn)的最短路徑及長度，每次求出從源點(diǎn)vi到一個(gè)終點(diǎn)vj的最短路徑及長度后，都要以vj作為新考慮的中間點(diǎn)，用vi到vj的最短路徑和最短路徑長度對vi到其它尚未求出最短路徑的那些終點(diǎn)的當(dāng)前路徑及長度作必要的修改，使之成為當(dāng)前新的最短路徑和最短路徑長度，當(dāng)進(jìn)行n-2次后算法結(jié)束。第54頁，共83頁，2023年，2月20日，星期五始點(diǎn)終點(diǎn)最短路徑路徑長度v0v1無v2(v0,v2)10v3(v0,v4,v3)50v4(v0,v4)30v5(v0,v4,v3,v5)600123455105020103010060有向圖第55頁，共83頁，2023年，2月20日，星期五始點(diǎn)終點(diǎn)最短路徑路徑長度v1V2(v1,v2)10V3(v1,v2,v3)27V4(v1,v5,v4)20v5(v1,v5)71253410751317492834無向圖第56頁，共83頁，2023年，2月20日，星期五Dijkstra算法首先，引進(jìn)一個(gè)輔助向量dist，dist[i]表示當(dāng)前所找到的從始點(diǎn)V到每個(gè)終點(diǎn)Vi的最短路徑長度。其初態(tài)為：若<v,vi>存在，則dist[i]為其上的權(quán)值，否則為最大值（計(jì)算機(jī)能表示）。算法:(1)用鄰接矩陣cost表示帶權(quán)圖。S表示已找到的從v出發(fā)的最短路徑的終點(diǎn)的集合，初態(tài)為空。dist向量的初值為：dist[v,i]=cost[v,i];(2)選擇vj，使得：dist[j]=Min{dist[i]|vi∈V-S}；vj就是當(dāng)前求得從v出發(fā)的最短路徑的終點(diǎn)。S=S+{j};(3)修改從v出發(fā)到集合V-S上任意頂點(diǎn)vk可達(dá)的最短路徑長度。ifdist[j]+cost[j,k]<dist[k]thendist[k]:=dist[j]+cost[j,k];(4)重復(fù)(2)(3)共n-1次。第57頁，共83頁，2023年，2月20日，星期五procshort_dij;beginfori:=1tondobegindist[i]:=cost[v0,i];ifdist[i]<maxthenpath[i]:=[v0]+[i]elsepath[i]:=[];end;s:=[v0];fork:=1ton-1dobeginwm:=max;j:=v0;fori:=1tondoifnot(iins)and(dist[i]<wm)thenbeginj:=i;wm:=dist[i];end;s:=s+[j];

fori:=1tondoifnot(iins)and(dist[j]+cost[j,i]<dist[i])thenbegindist[i]:=dist[j]+cost[j,i];path[i]:=path[j]+[i];end;end;end;其中：cost：鄰接矩陣；path[i]：存儲從v0到頂點(diǎn)i的最短路徑；是以集合作為數(shù)組元素；dist[i]：存儲相應(yīng)路徑長度；s：集合，表示已處理的頂點(diǎn)。第58頁，共83頁，2023年，2月20日，星期五練習(xí)5：Dijkstra算法練習(xí)【問題描述】從文件中讀入帶權(quán)圖的信息，按Dijkstra算法根據(jù)給定源點(diǎn)求出從源點(diǎn)到該圖中其余頂點(diǎn)的最短路徑?！据斎胛募康谝恍校阂粋€(gè)整數(shù)L：L=0表示無向圖，L=1表示有向圖；第二行三個(gè)整數(shù)m、n和k，分別表示圖的結(jié)點(diǎn)數(shù)、圖中的邊數(shù)以及源點(diǎn)。以下n行表示n條邊：每一行三個(gè)數(shù)x、y和z，z表示x與y之間邊的權(quán)值。【輸出文件】共m-1行，每一行的數(shù)據(jù)包括：頂點(diǎn)：最短路徑：路徑，如果不存在路徑，數(shù)據(jù)為：頂點(diǎn)：Nopath。

【示例】

輸入：輸出：

6812：Nopath13103：10：1315304：50：154161005：30：132356：60：15463450461054205660第59頁，共83頁，2023年，2月20日，星期五練習(xí)6：路由選擇問題【問題描述】X城有一個(gè)含有N個(gè)節(jié)點(diǎn)的通信網(wǎng)絡(luò)，在通信中，我們往往關(guān)心信息從一個(gè)節(jié)點(diǎn)I傳輸?shù)焦?jié)點(diǎn)J的最短路徑。遺憾的是，由于種種原因，線路中總有一些節(jié)點(diǎn)會(huì)出故障，因此在傳輸中要避開故障節(jié)點(diǎn)。

任務(wù)一：在己知故障節(jié)點(diǎn)的情況下，求避開這些故障節(jié)點(diǎn)，從節(jié)點(diǎn)I到節(jié)點(diǎn)J的最短路徑S0。

任務(wù)二：在不考慮故障節(jié)點(diǎn)的情況下，求從節(jié)點(diǎn)I到節(jié)點(diǎn)J的最短路徑S1、第二最短路徑S2。【輸入文件】第1行：NIJ(節(jié)點(diǎn)個(gè)數(shù)起始節(jié)點(diǎn)目標(biāo)節(jié)點(diǎn))

第2—N+1行：Sk1Sk2…SkN(節(jié)點(diǎn)K到節(jié)點(diǎn)J的距離為SkJK=1，2，……，N)

最后一行：PT1T2……Tp(故障節(jié)點(diǎn)的個(gè)數(shù)及編號)【輸出文件】S0S1S2(S1<=S2從節(jié)點(diǎn)I到節(jié)點(diǎn)J至少有兩條不同路徑)【輸入輸出樣例】route.in515

010500

1000620

5003035

063006

0203560

12route.out402230第60頁，共83頁，2023年，2月20日，星期五每對頂點(diǎn)之間的最短路徑求圖中每對頂點(diǎn)之間的最短路徑是指把圖中任意兩個(gè)頂點(diǎn)vi和vj（i≠j）之間的最短路徑都計(jì)算出來。解決此問題有兩種方法：一是分別以圖中的每個(gè)頂點(diǎn)為源點(diǎn)共調(diào)用n次迪杰斯特拉算法，此方法的時(shí)間復(fù)雜性為O（n3）；二是采用下面介紹的弗洛伊德（Floyed）算法，此算法的時(shí)間復(fù)雜性仍為O（n3），但比較簡單。第61頁，共83頁，2023年，2月20日，星期五弗洛伊德算法實(shí)際上是一個(gè)動(dòng)態(tài)規(guī)劃的算法。從圖的鄰接矩陣開始，按照頂點(diǎn)v1，v2，···，vn的次序，分別以每個(gè)頂點(diǎn)vk（1≤k≤n）作為新考慮的中間點(diǎn)，在第k-1次運(yùn)算Ak-1（A（0）為原圖的鄰接矩陣G）的基礎(chǔ)上，求出每對頂點(diǎn)vi到vj的最短路徑長度計(jì)算公式為：第62頁，共83頁，2023年，2月20日，星期五Floyd算法procshortpath_floyd;beginfori:=1tondoforj:=1tondobeginlength[i,j]:=cost[i,j];iflength[i,j]<maxthenpath[i,j]:=[i]+[j];end;fork:=1tondofori:=1tondoforj:=1tondo

iflength[i,k]+length[k,j]<length[i,j]thenbeginlength[i,j]:=length[i,k]+length[k,j];path[i,j]:=path[i,k]+path[k,j];end;end;其中：cost為鄰接矩陣；path[i,j]：表示頂點(diǎn)i到j(luò)的最短路徑；length[i,j]：第63頁，共83頁，2023年，2月20日，星期五練習(xí)7：Floyd算法練習(xí)【問題描述】從文件中讀入帶權(quán)圖的信息，按Dijkstra算法根據(jù)給定源點(diǎn)求出從源點(diǎn)到該圖中其余頂點(diǎn)的最短路徑?！据斎胛募康谝恍校阂粋€(gè)整數(shù)L：L=0表示無向圖，L=1表示有向圖；第二行三個(gè)整數(shù)m、n，分別表示圖的結(jié)點(diǎn)數(shù)和圖中的邊數(shù)。以下n行表示n條邊：每一行三個(gè)數(shù)x、y和z，z表示x與y之間邊的權(quán)值。第n+2行：整數(shù)R，以下R行每行一個(gè)整數(shù)表示頂點(diǎn)標(biāo)號作為源點(diǎn)。【輸出文件】共R行，每一行的數(shù)據(jù)表示源點(diǎn)到其余頂點(diǎn)的距離，按頂點(diǎn)編號由小大輸出，如果沒有路徑，輸出-1?！臼纠枯斎耄?輸出：-11050306068-1–1–1203013101530161002353450461054205660215第64頁，共83頁，2023年，2月20日，星期五拓?fù)渑判?/p>

在實(shí)際工作中，經(jīng)常用一個(gè)有向圖來表示施工的流程圖，或產(chǎn)品生產(chǎn)的流程圖。一個(gè)工作往往可以分為若干個(gè)子工程，把子工程稱為“活動(dòng)”。在有向圖種若以頂點(diǎn)表示“活動(dòng)”的網(wǎng)(ActivityOnVertexnetwork),簡稱為AOV網(wǎng)。第65頁，共83頁，2023年，2月20日，星期五對于一個(gè)AOV網(wǎng)，構(gòu)造其所有頂點(diǎn)的線性序列，使此序列不僅保持網(wǎng)中各頂點(diǎn)間原有的先后關(guān)系，而且使原來沒有先后關(guān)系的頂點(diǎn)之間也建立起人為的先后關(guān)系。這樣的線性序列稱為拓?fù)溆行蛐蛄?。?gòu)造AOV網(wǎng)的拓?fù)溆行蛐蛄械倪\(yùn)算稱為拓?fù)渑判颉Ｄ硞€(gè)AOV網(wǎng)，如果它的拓?fù)溆行蛐蛄斜粯?gòu)造成功，則該網(wǎng)中不存在有向回路，其各個(gè)子工程可按拓?fù)溆行蛐蛄械拇涡蜻M(jìn)行安排。顯然，一個(gè)AOV網(wǎng)的拓?fù)溆行蛐蛄胁⒉皇俏ㄒ坏摹５?6頁，共83頁，2023年，2月20日，星期五

對AOV網(wǎng)進(jìn)行拓?fù)渑判虻姆椒ê筒襟E是：在網(wǎng)中選擇一個(gè)沒有前趨的頂點(diǎn)且輸出之；從網(wǎng)中刪去該頂點(diǎn)，并且刪去從該頂點(diǎn)發(fā)出的全部有向邊；重復(fù)上述兩步，直至網(wǎng)中不存在沒有前趨的頂點(diǎn)為止。第67頁，共83頁，2023年，2月20日，星期五圖中v1和v6沒有前驅(qū)，則任選一個(gè)。假設(shè)為v6，輸出v6；在刪除v6及<v6,v4>和<v6,v5>之后，只有v1沒有前驅(qū)；輸出v1及刪除<v1,v2>,<v1,v3>,<v1,v4>；之后v3，v4都沒有前驅(qū)，以此類推?？傻玫酵?fù)渑判蚪Y(jié)果：v6-v1-v4-v3-v2-v5123456第68頁，共83頁，2023年，2月20日，星期五拓?fù)渑判蛩惴╰ypearcptr=^arctp;arctp=recordadjvex:integer;nextarc:arcptr;end;vexnode=recordvexdata:integer;indegree:integer;firstarc:arcptr;end;functiontopsort:boolean;begincrt_adjlist(dig);init(top);fori:=1tondoifdig[i].indegree=0thenpush(top,i);m:=0;whilenotempty(top)dobeginj:=pop(top);write(dig[j].data);m:=m+1;q:=dig[j].firtarc;whileq<>nildobegink:=q^.adjvex;dig[k].indegree:=dig[k].indegree-1;ifdig[k].indegree=0thenpush(top,k);q:=q^.nextarc;end;end;ifm<nthenreturnfalseelsereturntrue;end;其中，dig為鄰接表；top為棧；第69頁，共83頁，2023年，2月20日，星期五拓?fù)渑判蚋倪M(jìn)算法proctoposort(GL);{對鄰接表進(jìn)行拓?fù)渑判騷begintop:=0;fori:=1tondoifGL[i].indegree=0then[Gl[i].indegree:=top;top:=i;]m:=0;whiletop<>0dobeginj:=top;top:=GL[top].indegree;write(GL[j].data);m:=m+1;p:=GL[j].firstarc;whilep<>nildobegink:=p^.adjvex;GL[k].indegree:=GL[k].indegree-1;ifGL[k].indegree=0then[GL[k].indegree:=top;top:=k;]p:=p^.next;end;ifm<nthenwriteln("thenetworkhasacycle");end;end;第70頁，共83頁，2023年，2月20日，星期五該算法不用棧實(shí)現(xiàn)，對于入度為0的頂點(diǎn)，利用頂點(diǎn)的indegree域，將所有的入度為0的頂點(diǎn)利用靜態(tài)鏈表的形式組織起來。第71頁，共83頁，2023年，2月20日，星期五練習(xí)1：拓?fù)渑判蛱幚怼締栴}描述】從文件中讀入AO網(wǎng)的信息，求出該網(wǎng)的一個(gè)拓?fù)渑判蛐蛄小＃ㄗ⒁猓河邢驁D）【輸入文件】第一行兩個(gè)整數(shù)m和n，分別表示網(wǎng)的結(jié)點(diǎn)數(shù)和網(wǎng)中的邊數(shù)。以下n行表示n條邊：每一行兩個(gè)數(shù)x和y，表示x與y之間有一條邊?！据敵鑫募恐挥幸恍?。如果不能進(jìn)行拓?fù)渑判?，輸出：can’tsort；否則，輸出該網(wǎng)的拓?fù)渑判蛐蛄?。【示例】輸入?8輸出：6132451213143235456465第72頁，共83頁，2023年，2月20日，星期五逆拓?fù)渑判驅(qū)OV網(wǎng)進(jìn)行逆拓?fù)渑判虻姆椒ê筒襟E是：在網(wǎng)中選擇一個(gè)沒有后繼的頂點(diǎn)且輸出之；從網(wǎng)中刪去該頂點(diǎn)，并且刪去以該頂點(diǎn)作為弧頭的全部有向邊；重復(fù)上述兩步，直至網(wǎng)中不存在沒有后繼的頂點(diǎn)為止。第73頁，共83頁，2023年，2月20日，星期五練習(xí)2：逆拓?fù)渑判蚓毩?xí)【問題描述】從文件中讀入AO網(wǎng)的信息，求出該網(wǎng)的一個(gè)逆拓?fù)渑判蛐蛄?。（注意：有向圖）【輸入文件】第一行兩個(gè)整數(shù)m和n，分別表示網(wǎng)的結(jié)點(diǎn)數(shù)和網(wǎng)中的邊數(shù)。以下n行表示n條邊：每一行兩個(gè)數(shù)x和y，表示x與y之間有一條邊?！据敵鑫募恐挥幸恍?。如果不能進(jìn)行逆拓?fù)渑判?，輸出：can’tsort；否則，輸出該網(wǎng)的逆拓?fù)渑判蛐蛄??！臼纠枯斎耄?8輸出：5462311213143235456465第74頁，共83頁，2023年，2月20日，星期五練習(xí)3：軟件安裝盤軟件安裝通常是一件令人頭疼的事。軟件一般都包括若干個(gè)相對獨(dú)立的部分（稱為“組件”），在安裝的時(shí)候由用戶決定安裝哪些部分。并且，這些相對獨(dú)立的組件之間在安裝時(shí)有一定的先后順序要求。由于當(dāng)代的個(gè)人計(jì)算機(jī)普遍安裝了軟盤驅(qū)動(dòng)器，所以軟件的最流行的載體形式是軟盤。然而，由于軟盤的容量有限，稍大一些的軟件就無法用一張軟盤裝下。這時(shí)，這些軟件往往要用很多張軟盤來存儲。每張磁盤上存儲了軟件的一個(gè)或多個(gè)組件。這些軟盤稱為軟件的安裝盤。由于軟件的各個(gè)組件分散在不同的軟盤上，而在安裝時(shí)又有一定的先后順序要求，所以很容易發(fā)生要求用戶反復(fù)換盤的情況。而計(jì)算機(jī)用戶在安裝軟件的時(shí)候，最反感的就是反復(fù)在軟盤之間切換：找盤、插盤、取盤、找盤、插盤、取盤、…，一切都顯得那么瑣碎和無序。因此，有必要對軟件安裝盤的制作提出下述要求：永遠(yuǎn)不要讓用戶將一張磁盤插入兩次。更精確地，要求對安裝盤從1開始順序編號，使得安裝的時(shí)候，用戶只要按順序插入磁盤即可。出于經(jīng)濟(jì)的考慮，通常要求安裝盤的總數(shù)最少。寫一個(gè)程序，對于給定的軟件，制定最優(yōu)的安裝盤方案。輸入輸入文件的第一行是一個(gè)正整數(shù)M（1<=M<=109），給出了每張磁盤的最大容量（字節(jié)數(shù)）。輸入文件的第二行是一個(gè)正整數(shù)N（1<=N<=100），給出了軟件的組件數(shù)。接下來的N行每行給出一個(gè)組件的詳細(xì)信息。包括：組件所占的字節(jié)數(shù)；在安裝該組件之前應(yīng)先安裝的組件序號（如有多個(gè)組件須先安裝，則每個(gè)都應(yīng)列出其序號，若無須先安裝其它組件，則該行只含組件所占字節(jié)數(shù)）。輸入文件中同一行相鄰兩項(xiàng)之間用一個(gè)或多個(gè)空格隔開。輸出輸出文件的第一行給出了最優(yōu)安裝盤方案的軟盤數(shù)。如果不存在最優(yōu)安裝盤方案，則輸出0。接下來的每一行順序給出了每張盤上存儲的組件的序號。如果一張盤上存儲了多個(gè)組件，則輸出所有這些組件的序號，中間用一個(gè)空格隔開。樣例輸入1457664351266591234518325421樣例輸出2123第75頁，共83頁，2023年，2月20日，星期五關(guān)鍵路徑由于在AOE-網(wǎng)中有些活動(dòng)可以并行的進(jìn)行，所以完成工程的最短時(shí)間是從開始點(diǎn)到完成點(diǎn)的最長路經(jīng)的長度（指的是路徑上各活動(dòng)持續(xù)時(shí)間之和，不是路徑上弧的數(shù)目），路徑上最長的路徑叫做關(guān)鍵路徑。假設(shè)開始點(diǎn)是v1，從v1到vi的最長路徑長度稱為事件vi的最早發(fā)生時(shí)間。這個(gè)時(shí)間決定了所有以vi為尾的弧所表示活動(dòng)的最早開始時(shí)間。用e(i)表示。再定義一個(gè)活動(dòng)ai的最遲開始時(shí)間l(i)，這是在不推遲整個(gè)工程完成的前提下，活動(dòng)ai最遲必須開始的時(shí)間。l(i)-e(i)是完成活動(dòng)ai的時(shí)間余量。l(i)=e(i)的活動(dòng)叫關(guān)鍵活動(dòng)。關(guān)鍵路徑上的活動(dòng)都是關(guān)鍵活動(dòng)，因此提前完成非關(guān)鍵活動(dòng)并不能加快工程的進(jìn)度。第76頁，共83頁，2023年，2月20日，星期五結(jié)點(diǎn)表示事件，弧表示活動(dòng)。如下圖中的網(wǎng)，從v1到v9的最長路徑是(v1,v2,v5,v8,v9),路徑長度為18，即v9的最早發(fā)生時(shí)間是18。而活動(dòng)a6的最早開始時(shí)間是5，最遲開始時(shí)間為8。分析關(guān)鍵路徑的目的是辨析哪些是關(guān)鍵活動(dòng)，以便爭取提高關(guān)鍵活動(dòng)的工效，縮短整個(gè)工期。123456789a3=5a1=6a2=4a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4第77頁，共83頁，2023年，2月20日，星期五尋找關(guān)鍵活動(dòng)判別關(guān)鍵活動(dòng)即是找e(i)=l(i)的活動(dòng)。為了求AOE-網(wǎng)中活動(dòng)的e(i)=l(i),首先應(yīng)求得事件的最早發(fā)生時(shí)間ve(j)和最遲開始時(shí)間vl(j)。如果活動(dòng)ai由<j,k>表示，其持續(xù)時(shí)間記為dut(<j,k>),則有：e(i)=ve(j)l(i)=vl(k)-dut(<j,k>);求ve(j)和le(j):(1)從ve(1)=0出發(fā)向前推進(jìn)：ve(j)=Max{ve(i)+dut(<i,j>)},<i,j>€T,2≤j≤n其中，T表示所有以j為頭的弧