算法拓?fù)渑判驅(qū)W習(xí)教案

1、會(huì)計(jì)學(xué)1算法算法(sun f)拓?fù)渑判蛲負(fù)渑判虻谝豁?yè)，共47頁(yè)。第2頁(yè)/共47頁(yè)第二頁(yè)，共47頁(yè)。3 計(jì)劃、施工過(guò)程、生產(chǎn)流程、程序流程等都是計(jì)劃、施工過(guò)程、生產(chǎn)流程、程序流程等都是“工程工程”。除了很小的工程外，一般都把工程分為。除了很小的工程外，一般都把工程分為若干個(gè)叫做若干個(gè)叫做“活動(dòng)活動(dòng)”的子工程。完成了這些活動(dòng)的子工程。完成了這些活動(dòng)，這個(gè)工程就可以完成了。，這個(gè)工程就可以完成了。 例如，計(jì)算機(jī)專(zhuān)業(yè)學(xué)生的學(xué)習(xí)就是一個(gè)工程，每例如，計(jì)算機(jī)專(zhuān)業(yè)學(xué)生的學(xué)習(xí)就是一個(gè)工程，每一門(mén)課程的學(xué)習(xí)就是整個(gè)工程的一些活動(dòng)。其中一門(mén)課程的學(xué)習(xí)就是整個(gè)工程的一些活動(dòng)。其中有些課程要求先修課程，有些則不要求。

2、這樣在有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領(lǐng)先有的課程之間有領(lǐng)先(ln xin)關(guān)系，有的課程關(guān)系，有的課程可以并行地學(xué)習(xí)?？梢圆⑿械貙W(xué)習(xí)。第3頁(yè)/共47頁(yè)第三頁(yè)，共47頁(yè)。4例例課程代號(hào)課程代號(hào) 課程名稱(chēng)課程名稱(chēng) 先修棵先修棵C1C2C3C4C5C6C7C8C9C10C11C12無(wú)無(wú)C1C1,C2C1C3,C4C11C3.C5C3,C6無(wú)無(wú)C9C9C1,C9,C10程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)基礎(chǔ)離散數(shù)學(xué)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)匯編語(yǔ)言匯編語(yǔ)言語(yǔ)言的設(shè)計(jì)和分析語(yǔ)言的設(shè)計(jì)和分析計(jì)算機(jī)原理計(jì)算機(jī)原理編譯原理編譯原理操作系統(tǒng)操作系統(tǒng)高等數(shù)學(xué)高等數(shù)學(xué)線性代數(shù)線性代數(shù)普通物理普通物理數(shù)值分

3、析數(shù)值分析C1C2C3C4C5C6C7C8C9C10C11C12第4頁(yè)/共47頁(yè)第四頁(yè)，共47頁(yè)。51 1、在、在AOVAOV中中拓?fù)溆行蛐蛄校簩⒏鱾€(gè)頂點(diǎn)拓?fù)溆行蛐蛄校簩⒏鱾€(gè)頂點(diǎn) ( (代表各個(gè)活動(dòng)代表各個(gè)活動(dòng)) )排列成一個(gè)線性有排列成一個(gè)線性有序的序列，使得序的序列，使得AOVAOV網(wǎng)絡(luò)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得網(wǎng)絡(luò)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿足。到滿足。拓?fù)渑判蛲負(fù)渑判?pi x)(pi x)把把AOVAOV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間的網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間的優(yōu)先關(guān)系排列成一個(gè)線性序列的過(guò)程。優(yōu)先關(guān)系排列成一個(gè)線性序列的過(guò)程。檢測(cè)檢測(cè)AOVAOV網(wǎng)中是否存在環(huán)方

4、法：對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蚓W(wǎng)中是否存在環(huán)方法：對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄校艟W(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該序列，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該AOVAOV網(wǎng)必網(wǎng)必定不存在環(huán)。定不存在環(huán)。二、拓?fù)涠?、拓?fù)?tu p)排序排序第5頁(yè)/共47頁(yè)第五頁(yè)，共47頁(yè)。6C1C2C3C4C5C6C7C8C9C10C11C12拓?fù)渫負(fù)?tu p)序列：序列：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8或或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8一個(gè)一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇蔷W(wǎng)的拓?fù)湫蛄胁皇?b shi)唯

5、一的唯一的第6頁(yè)/共47頁(yè)第六頁(yè)，共47頁(yè)。7BDAC對(duì)于(duy)有向圖不能求得它的拓?fù)?tu p)有序序列。因?yàn)閳D中存在一個(gè)(y )回路 B, C, D第7頁(yè)/共47頁(yè)第七頁(yè)，共47頁(yè)。8第8頁(yè)/共47頁(yè)第八頁(yè)，共47頁(yè)。abcghdfeabhcdgfe 沒(méi)有前驅(qū)的頂點(diǎn)沒(méi)有前驅(qū)的頂點(diǎn)(dngdin)刪除頂點(diǎn)刪除頂點(diǎn)(dngdin)及以它為及以它為尾的弧尾的弧 弧頭頂弧頭頂(tudng)點(diǎn)的入度減點(diǎn)的入度減1abcghdfe需要設(shè)一個(gè)數(shù)組indegreew，記錄頂點(diǎn)(dngdin)的入度數(shù) 入度為零的頂點(diǎn)入度為零的頂點(diǎn)第9頁(yè)/共47頁(yè)第九頁(yè)，共47頁(yè)。10C0C1C2C3C4C5 C0 C1

6、 C2 C3 0 C4 C5 0012345ind data firstarc 130103 1adjvex next 3 0 5 1 5 0 0 1 5 0第10頁(yè)/共47頁(yè)第十頁(yè)，共47頁(yè)。11鄰接鄰接(ln ji)表結(jié)點(diǎn)：表結(jié)點(diǎn)：typedef struct node int adjvex; /頂點(diǎn)域頂點(diǎn)域 struct node *next; /鏈域鏈域JD;表頭表頭(bio tu)結(jié)點(diǎn)：結(jié)點(diǎn)：typedef struct tnode int ind; /入度域入度域 struct node *link; /鏈域鏈域TD;TD gM; 第11頁(yè)/共47頁(yè)第十一頁(yè)，共47頁(yè)。124 4、

7、拓?fù)渑判蛩惴ā⑼負(fù)渑判蛩惴?sun f)(sun f)實(shí)現(xiàn)實(shí)現(xiàn)第12頁(yè)/共47頁(yè)第十二頁(yè)，共47頁(yè)。13例例1234560122inlink 5 5 4 3vex next3 2 5 2 4012345632104top16toptop第13頁(yè)/共47頁(yè)第十三頁(yè)，共47頁(yè)。140122inlink 5 5 4 3vex next3 2 5 2 40123456輸出輸出(shch)序列：序列：63210416toptop第14頁(yè)/共47頁(yè)第十四頁(yè)，共47頁(yè)。150122inlink 5 5 4 3vex next3 2 5 2 40123456輸出序列：輸出序列：6321041topp第15頁(yè)/

8、共47頁(yè)第十五頁(yè)，共47頁(yè)。160122inlink 5 5 4 3vex next2 2 5 2 40123456輸出輸出(shch)序列：序列：6321041topp第16頁(yè)/共47頁(yè)第十六頁(yè)，共47頁(yè)。170122inlink 5 5 4 3vex next2 2 5 2 40123456輸出輸出(shch)序列：序列：6321041topp第17頁(yè)/共47頁(yè)第十七頁(yè)，共47頁(yè)。180112inlink 5 5 4 3vex next2 2 5 2 40123456輸出輸出(shch)序列：序列：6321041topp第18頁(yè)/共47頁(yè)第十八頁(yè)，共47頁(yè)。190112inlink 5 5

9、 4 3vex next2 2 5 2 40123456輸出輸出(shch)序列：序列：6321041topp=NULL第19頁(yè)/共47頁(yè)第十九頁(yè)，共47頁(yè)。200112inlink 5 5 4 3vex next2 2 5 2 40123456輸出輸出(shch)序列：序列：6 1321041toptop第20頁(yè)/共47頁(yè)第二十頁(yè)，共47頁(yè)。210112inlink 5 5 4 3vex next2 2 5 2 40123456輸出輸出(shch)序列：序列：6 132104topp第21頁(yè)/共47頁(yè)第二十一頁(yè)，共47頁(yè)。220102inlink 5 5 4 3vex next2 2 5 2

10、 40123456輸出輸出(shch)序列：序列：6 132104topp4第22頁(yè)/共47頁(yè)第二十二頁(yè)，共47頁(yè)。230102inlink 5 5 4 3vex next2 2 5 2 40123456輸出輸出(shch)序列：序列：6 132104p4top第23頁(yè)/共47頁(yè)第二十三頁(yè)，共47頁(yè)。240102inlink 5 5 4 3vex next2 2 5 2 40123456輸出輸出(shch)序列：序列：6 132104p4top第24頁(yè)/共47頁(yè)第二十四頁(yè)，共47頁(yè)。250002inlink 5 5 4 3vex next2 2 5 2 40123456輸出輸出(shch)序列

11、：序列：6 132104p4top3第25頁(yè)/共47頁(yè)第二十五頁(yè)，共47頁(yè)。260002inlink 5 5 4 3vex next2 2 5 2 40123456輸出輸出(shch)序列：序列：6 132104p4top3第26頁(yè)/共47頁(yè)第二十六頁(yè)，共47頁(yè)。270002inlink 5 5 4 3vex next2 2 5 2 40123456輸出輸出(shch)序列：序列：6 132104p4top3第27頁(yè)/共47頁(yè)第二十七頁(yè)，共47頁(yè)。280001inlink 5 5 4 3vex next2 2 5 2 40123456輸出輸出(shch)序列：序列：6 132104p4top3

12、第28頁(yè)/共47頁(yè)第二十八頁(yè)，共47頁(yè)。290001inlink 5 5 4 3vex next2 2 5 2 40123456輸出輸出(shch)序列：序列：6 132104p=NULL4top3第29頁(yè)/共47頁(yè)第二十九頁(yè)，共47頁(yè)。300001inlink 5 5 4 3vex next2 2 5 2 40123456輸出輸出(shch)序列：序列：6 1 3321044top3第30頁(yè)/共47頁(yè)第三十頁(yè)，共47頁(yè)。310001inlink 5 5 4 3vex next2 2 5 2 40123456輸出輸出(shch)序列：序列：6 1 3321044topp第31頁(yè)/共47頁(yè)第三十

13、一頁(yè)，共47頁(yè)。320001inlink 5 5 4 3vex next1 2 5 2 40123456輸出輸出(shch)序列：序列：6 1 3321044topp第32頁(yè)/共47頁(yè)第三十二頁(yè)，共47頁(yè)。330001inlink 5 5 4 3vex next1 2 5 2 40123456輸出輸出(shch)序列：序列：6 1 3321044topp第33頁(yè)/共47頁(yè)第三十三頁(yè)，共47頁(yè)。340000inlink 5 5 4 3vex next1 2 5 2 40123456輸出輸出(shch)序列：序列：6 1 3321044topp2第34頁(yè)/共47頁(yè)第三十四頁(yè)，共47頁(yè)。350000

14、inlink 5 5 4 3vex next1 2 5 2 40123456輸出輸出(shch)序列：序列：6 1 3321044topp2第35頁(yè)/共47頁(yè)第三十五頁(yè)，共47頁(yè)。360000inlink 5 5 4 3vex next1 2 5 2 40123456輸出輸出(shch)序列：序列：6 1 3321044top2p=NULL第36頁(yè)/共47頁(yè)第三十六頁(yè)，共47頁(yè)。370000inlink 5 5 4 3vex next1 2 5 2 40123456輸出輸出(shch)序列：序列：6 1 3 2321044top2p=NULL第37頁(yè)/共47頁(yè)第三十七頁(yè)，共47頁(yè)。380000

15、inlink 5 5 4 3vex next1 2 5 2 40123456輸出輸出(shch)序列：序列：6 1 3 2321044topp=NULL第38頁(yè)/共47頁(yè)第三十八頁(yè)，共47頁(yè)。390000inlink 5 5 4 3vex next1 2 5 2 40123456輸出輸出(shch)序列：序列：6 1 3 2 4321044top第39頁(yè)/共47頁(yè)第三十九頁(yè)，共47頁(yè)。400000inlink 5 5 4 3vex next1 2 5 2 40123456輸出輸出(shch)序列：序列：6 1 3 2 432104topp第40頁(yè)/共47頁(yè)第四十頁(yè)，共47頁(yè)。410000inl

16、ink 5 5 4 3vex next0 2 5 2 40123456輸出輸出(shch)序列：序列：6 1 3 2 432104topp5第41頁(yè)/共47頁(yè)第四十一頁(yè)，共47頁(yè)。420000inlink 5 5 4 3vex next0 2 5 2 40123456輸出輸出(shch)序列：序列：6 1 3 2 4 532104topp=NULL第42頁(yè)/共47頁(yè)第四十二頁(yè)，共47頁(yè)。430000inlink 5 5 4 3vex next0 2 5 2 40123456輸出輸出(shch)序列：序列：6 1 3 2 432104topp=NULL5第43頁(yè)/共47頁(yè)第四十三頁(yè)，共47頁(yè)。440000inlink 5 5 4 3vex next0 2 5 2 40