數(shù)據(jù)結(jié)構(gòu)有向無環(huán)圖及其應(yīng)用

數(shù)據(jù)結(jié)構(gòu)有向無環(huán)圖及其應(yīng)用第一頁(yè)，共三十六頁(yè)，編輯于2023年，星期三一、定義

一個(gè)無環(huán)的有向圖稱為有向無環(huán)圖，簡(jiǎn)寫為DAG（directedacyclinegraph）。與有向二叉樹相比，有向無環(huán)圖是更一般的特殊有向圖。實(shí)例：有向樹有向無環(huán)圖有向圖教材179頁(yè)給出了有向無環(huán)圖的一個(gè)簡(jiǎn)單應(yīng)用：用有向無環(huán)圖描述算術(shù)表達(dá)式。第二頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判?.引例：現(xiàn)有計(jì)算機(jī)課程12門，如下表所示：課程編號(hào)課程名稱先修課程c1程序設(shè)計(jì)基礎(chǔ)無c2離散數(shù)學(xué)c1c3數(shù)據(jù)結(jié)構(gòu)c1,c2c4匯編語言c1c5語言的設(shè)計(jì)和分析c3,c4c6計(jì)算機(jī)組成原理c11c7編譯原理c5,c3c8操作系統(tǒng)c3,c6c9高等數(shù)學(xué)無c10線性代數(shù)c9c11普通物理c9c12數(shù)值分析c9,c10,c1c1c9c4c2c12c10c11c3c5c6c7c8第三頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判騝1c9c4c2c12c10c11c3c5c6c7c82.拓?fù)渑判颍浩蚴侵讣现袃H有部分元素可比較大小(或先后)；

全序是指集合中所有元素均可比較大?。ɑ蛳群螅?。第四頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判騝1c9c4c2c12c10c11c3c5c6c7c82.拓?fù)渑判颍和負(fù)渑判蚴侵笇⒁粋€(gè)偏序關(guān)系轉(zhuǎn)化為全序關(guān)系的過程的特殊操作。第五頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判騝1c9c4c2c12c10c11c3c5c6c7c83.方法：①在有向圖中選擇一個(gè)沒有前驅(qū)（即入度為0）的頂點(diǎn)并輸出之。②在有向圖中刪除剛剛輸出的頂點(diǎn)及所有以該頂點(diǎn)為尾的弧。③圖中若不再有入度為0的頂點(diǎn)，則結(jié)束；否則轉(zhuǎn)①。第六頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判騝1c9c4c2c12c10c11c3c5c6c7c83.方法：c1拓?fù)湫蛄校篶2c3c4c5c7c9c10c11c6c12c8第七頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判?.方法：c1拓?fù)湫蛄校篶2c3c4c5c7c9c10c11c6c12c8注意1：從某種意義下來說，拓?fù)渑判虻慕Y(jié)果是不唯一的。注意2：這種以頂點(diǎn)表示活動(dòng)的有向無環(huán)圖稱為活動(dòng)在頂點(diǎn)的網(wǎng)，簡(jiǎn)稱AOV(ActivityOnVertexNetwork)網(wǎng)。第八頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判?.算法說明：為了使說明過程簡(jiǎn)單起見，我們以下圖為例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^datafirstarcadjvexnextarc另外增設(shè)一個(gè)存放各頂點(diǎn)的入度值的一維數(shù)組indegree:indegree[0..5]021230012345第九頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判?.算法說明：為了使說明過程簡(jiǎn)單起見，我們以下圖為例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增設(shè)一個(gè)存放各頂點(diǎn)的入度值的一維數(shù)組indegree:indegree[0..5]021230012345求indegree一維數(shù)組初值的程序：FindInDegree(ALGraphG,indegree[0..G.vexnum-1]{for(i=0;i<G.vexnum;++i){p=G.vertices[i].firstarc;while(p){k=p->adjvex;++indegree[k];p=p->nextarc;}}}//FindInDegree第十頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判?.算法說明：為了使說明過程簡(jiǎn)單起見，我們以下圖為例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增設(shè)一個(gè)存放各頂點(diǎn)的入度值的一維數(shù)組indegree:indegree[0..5]021230012345拓?fù)渑判蛩惴ㄋ枷耄孩僭O(shè)一個(gè)棧S，入度為0的頂點(diǎn)的序號(hào)進(jìn)棧。如0，5進(jìn)棧。count=0(打印頂點(diǎn)個(gè)數(shù)計(jì)數(shù)器)。②當(dāng)棧S不空時(shí)，出棧一個(gè)元素并打印相應(yīng)頂點(diǎn)；count加1。該頂點(diǎn)的所有鄰接點(diǎn)的入度減1，減1后入度為0的頂點(diǎn)的序號(hào)進(jìn)棧。③重復(fù)第二步，直至棧空時(shí)轉(zhuǎn)④。

④若count=G.vexnum,則拓?fù)渑判虺晒Γ环駝t圖中必有環(huán)路，拓?fù)渑判蚴　５谑豁?yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判?.算法說明：為了使說明過程簡(jiǎn)單起見，我們以下圖為例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增設(shè)一個(gè)存放各頂點(diǎn)的入度值的一維數(shù)組indegree:indegree[0..5]02123001234550s第十二頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判?.算法說明：為了使說明過程簡(jiǎn)單起見，我們以下圖為例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增設(shè)一個(gè)存放各頂點(diǎn)的入度值的一維數(shù)組indegree:indegree[0..5]0212300123450s5打印G.vertices[5].data4號(hào)和3號(hào)頂點(diǎn)的入度分別減1第十三頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判?.算法說明：為了使說明過程簡(jiǎn)單起見，我們以下圖為例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增設(shè)一個(gè)存放各頂點(diǎn)的入度值的一維數(shù)組indegree:indegree[0..5]0211200123450s第十四頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判?.算法說明：為了使說明過程簡(jiǎn)單起見，我們以下圖為例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增設(shè)一個(gè)存放各頂點(diǎn)的入度值的一維數(shù)組indegree:indegree[0..5]021120012345

s0打印G.vertices[0].data3號(hào)、2號(hào)、1號(hào)頂點(diǎn)的入度分別減1第十五頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判?.算法說明：為了使說明過程簡(jiǎn)單起見，我們以下圖為例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增設(shè)一個(gè)存放各頂點(diǎn)的入度值的一維數(shù)組indegree:indegree[0..5]01002001234523s第十六頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判?.算法說明：為了使說明過程簡(jiǎn)單起見，我們以下圖為例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增設(shè)一個(gè)存放各頂點(diǎn)的入度值的一維數(shù)組indegree:indegree[0..5]01002001234523s第十七頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判?.算法說明：為了使說明過程簡(jiǎn)單起見，我們以下圖為例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增設(shè)一個(gè)存放各頂點(diǎn)的入度值的一維數(shù)組indegree:indegree[0..5]010020012345

3s2打印G.vertices[2].data4號(hào)、1號(hào)頂點(diǎn)的入度分別減1第十八頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判?.算法說明：為了使說明過程簡(jiǎn)單起見，我們以下圖為例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增設(shè)一個(gè)存放各頂點(diǎn)的入度值的一維數(shù)組indegree:indegree[0..5]00001001234513s第十九頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判?.算法說明：為了使說明過程簡(jiǎn)單起見，我們以下圖為例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增設(shè)一個(gè)存放各頂點(diǎn)的入度值的一維數(shù)組indegree:indegree[0..5]000010012345

3s1打印G.vertices[1].data第二十頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判?.算法說明：為了使說明過程簡(jiǎn)單起見，我們以下圖為例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增設(shè)一個(gè)存放各頂點(diǎn)的入度值的一維數(shù)組indegree:indegree[0..5]000010012345

3s第二十一頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判?.算法說明：為了使說明過程簡(jiǎn)單起見，我們以下圖為例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增設(shè)一個(gè)存放各頂點(diǎn)的入度值的一維數(shù)組indegree:indegree[0..5]000010012345

s3打印G.vertices[3].data4號(hào)頂點(diǎn)的入度減1第二十二頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判?.算法說明：為了使說明過程簡(jiǎn)單起見，我們以下圖為例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增設(shè)一個(gè)存放各頂點(diǎn)的入度值的一維數(shù)組indegree:indegree[0..5]000000012345

4s第二十三頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判?.算法說明：為了使說明過程簡(jiǎn)單起見，我們以下圖為例：v10v21v32v43v65v54G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增設(shè)一個(gè)存放各頂點(diǎn)的入度值的一維數(shù)組indegree:indegree[0..5]000000012345

s4打印G.vertices[4].data最后輸出的拓?fù)湫蛄袨椋簐6v1v3v2v4v5第二十四頁(yè)，共三十六頁(yè)，編輯于2023年，星期三二、拓?fù)渑判?.程序：StatusTopologicalSort(ALGraph){FindIndegree(G,indegree);InitStack(S);for(i=0;i<G.vexnum;++i)if(!indegree[i])Push(S,i);//入度為0的頂點(diǎn)的序號(hào)進(jìn)棧count=0;while(!StackEmpty(S)){Pop(S,i);cout<<i<<""<<G.vertices[i].data;++count;for(p=G.vertices[i].firstarc;p;p=p->nextarc){

第二十五頁(yè)，共三十六頁(yè)，編輯于2023年，星期三StatusTopologicalSort(ALGraph){FindIndegree(G,indegree);InitStack(S);for(i=0;i<G.vexnum;++i)if(!indegree[i])Push(S,i);//入度為0的頂點(diǎn)的序號(hào)進(jìn)棧count=0;while(!StackEmpty(S)){Pop(S,i);cout<<i<<""<<G.vertices[i].data;++count;for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;--indegree[k];if(!(indegree[k]))Push(S,k);}第二十六頁(yè)，共三十六頁(yè)，編輯于2023年，星期三StatusTopologicalSort(ALGraph){FindIndegree(G,indegree);InitStack(S);for(i=0;i<G.vexnum;++i)if(!indegree[i])Push(S,i);//入度為0的頂點(diǎn)的序號(hào)進(jìn)棧count=0;while(!StackEmpty(S)){Pop(S,i);cout<<i<<""<<G.vertices[i].data;++count;for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;--indegree[k];if(!(indegree[k]))Push(S,k);}}//whileif(count==G.vexnum)returnOK;elsereturnERROR;}//TopologicalSort第二十七頁(yè)，共三十六頁(yè)，編輯于2023年，星期三StatusTopologicalSort(ALGraph){FindIndegree(G,indegree);InitStack(S);for(i=0;i<G.vexnum;++i)if(!indegree[i])Push(S,i);//入度為0的頂點(diǎn)的序號(hào)進(jìn)棧count=0;while(!StackEmpty(S)){Pop(S,i);cout<<i<<""<<G.vertices[i].data;++count;for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;--indegree[k];if(!(indegree[k]))Push(S,k);}}//whileif(count==G.vexnum)returnOK;elsereturnERROR;}//TopologicalSort第二十八頁(yè)，共三十六頁(yè)，編輯于2023年，星期三三、關(guān)鍵路徑1.實(shí)例：v10v21v32v43v54v65v76v87v98a1=6a4=1a2=4a3=5a5=1a6=2a7=9a11=4a10=2a8=7a9=4①頂點(diǎn)vi表示事件；②弧既描述事件之間的依賴關(guān)系，又表示某種活動(dòng)ai的持續(xù)時(shí)間；③從“起點(diǎn)”(v1)開始到“終點(diǎn)”(v9)的最長(zhǎng)路徑稱為關(guān)鍵路徑；④每個(gè)活動(dòng)ai都有一個(gè)最早開始時(shí)間e(i)和一個(gè)最遲開始時(shí)間l(i)；例如：對(duì)于a5，有：

e(5)=4；l(5)=6⑤關(guān)鍵路徑上的活動(dòng)ai稱為關(guān)鍵活動(dòng)，一定滿足：e(i)=l(i)；⑥每個(gè)事件v也有一個(gè)最早開始時(shí)間ve(k)和一個(gè)最遲開始時(shí)間vl(k);例如：對(duì)于事件v3，有：ve(2)=4；vl(2)=6第二十九頁(yè)，共三十六頁(yè)，編輯于2023年，星期三三、關(guān)鍵路徑1.實(shí)例：v10v21v32v43v54v65v76v87v98a1=6a4=1a2=4a3=5a5=1a6=2a7=9a11=4a10=2a8=7a9=4⑦活動(dòng)ai和它所依附的頂點(diǎn)的關(guān)系：設(shè)有：jkai=dut(<j,k>)則有：1.e(i)=ve(j)2.l(i)=vl(k)-dut(<j,k>)即：活動(dòng)ai的最早開始時(shí)間等于事件j的最早開始時(shí)間；活動(dòng)ai的最遲開始時(shí)間等于事件k的最遲開始時(shí)間減活動(dòng)ai的持續(xù)時(shí)間。第三十頁(yè)，共三十六頁(yè)，編輯于2023年，星期三三、關(guān)鍵路徑1.實(shí)例：v10v21v32v43v54v65v76v87v98a1=6a4=1a2=4a3=5a5=1a6=2a7=9a11=4a10=2a8=7a9=4⑧求關(guān)鍵路徑的算法思想：1）設(shè)ve(0)=0；按拓?fù)漤樞蚶萌缦鹿揭来吻笃溆喔黜旤c(diǎn)j(j=1,2,...n-1)的ve(j):2）設(shè)vl(n-1)=ve(n-1)；按拓?fù)淠骓樞蚶萌缦鹿揭来吻笃溆喔黜旤c(diǎn)j(j=n-2,...,2,1,0)的vl(j)