1、拓?fù)渑判蛲負(fù)渑判驈?fù)習(xí)小結(jié)和作業(yè)復(fù)習(xí)圖的深度優(yōu)先搜索：簡單路徑圖的廣度優(yōu)先搜索：最短路徑圖的遍歷方法v1v3v2v5v6v7v4拓?fù)渑判騿栴}的引入拓?fù)渑判虻亩x拓?fù)渑判蚍椒?拓?fù)渑判蚍椒?練習(xí)拓?fù)渑判?問題引入某學(xué)校的部分課程結(jié)構(gòu)java語言數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)庫原理算法分析與設(shè)計操作系統(tǒng)軟件工程軟件測試如何制定教學(xué)計劃？拓?fù)渑判?定義按照有向圖給出的次序關(guān)系，將圖中頂點排成一個線性序列，對于有向圖中沒有限定次序關(guān)系的頂點，則可以人為加上任意的次序關(guān)系。由此所得頂點的線性序列稱之為拓?fù)溆行蛐蛄?。拓?fù)渑判蚴菍τ邢驘o圈圖的頂點的一種排序，使得如果存在一條從vi到vj的路徑，那么在排序中vj就出現(xiàn)在vi的后面

2、。 顯然，如果圖中含有圈，那么拓?fù)渑判蚴遣豢赡艿模驗閷τ谌ι系膬蓚€頂點v和w，v優(yōu)先于w同時w又優(yōu)先于v。拓?fù)渑判?定義BDAC不能求得它的拓?fù)溆行蛐蛄?。因為圖中存在一個回路 B, C, D拓?fù)渑判?舉例BDAC可求得拓?fù)溆行蛐蛄校?A B C D 或 A C B D拓?fù)渑判?舉例 拓?fù)湫蛄胁皇俏ㄒ坏?。v1v3v2v5v6v7v4可能的拓?fù)湫蛄袨椋簐1,v2,v5,v4,v3,v7,v6v1,v2,v5,v4,v7,v3,v6拓?fù)渑判?舉例 拓?fù)渑判?方法11、從有向圖中選取一個沒有前驅(qū)的頂點，并輸出;2、從有向圖中刪去此頂點以及所有以它為尾的弧;3、重復(fù)上述兩步，直至圖空，或者圖不空但找不

3、到無前驅(qū)的頂點為止。acgbdhfebhacdgfe拓?fù)湫蛄校?拓?fù)渑判?方法1 拓?fù)渑判?方法11、從有向圖中選取一個沒有前驅(qū)的頂點，并輸出;2、從有向圖中刪去此頂點以及所有以它為尾的弧;3、重復(fù)上述兩步，直至圖空，或者圖不空但找不到無前驅(qū)的頂點為止。入度為0的頂點弧頭頂點的入度減1void topsort( ) for(int counter=0;counterNUM_VERTICES;counter+) Vertex v=findNewVertexOfIndegreeZero( ); /尋找一個尚未被分配拓?fù)渚幪柕娜攵葹?的頂點if(v=null) /圖中有圈 throw new Cyc

4、leFoundException(); v.topNum=counter; /頂點v的拓?fù)渚幪杅or each Vertex w adjacent to v w.indegree-; /弧頭頂點的入度減1 拓?fù)渑判?方法1v1v3v2v5v6v7v4出隊前的入度頂點 1 2 3 4 5 6 7 v1 v2 v3 v4 v5 v6 v7入隊出隊0123132v1012132v210321v50131v4200v3,v7v3v7100v6v1v2v5v4p274, 9.2隊列和棧是否都能實現(xiàn)拓?fù)渑判颍?拓?fù)渑判?方法1void topsort( ) throws CycleFoundExcepti

5、on Queue q=new Queue( ); int counter=0; /對輸出頂點計數(shù) for each Vertex v if(v.indegree=0) /頂點的入度為0，則入隊 q.enqueue(v); while (!q.isEmpty( ) /如果隊列非空 if (counter!=NUM_VERTICES) /有圈 throw new CycleFoundException( ); 拓?fù)渑判?方法1void topsort( ) throws CycleFoundException . while (!q.isEmpty( ) /如果隊列非空 .Vertex v=q.d

6、equeue( );v.topNum=+counter;for each Vertex w adjacent to vif(-w.indegree=0)q.enqueue(w); 拓?fù)渑判?方法1總的時間復(fù)雜度：O(n+e)算法分析： 拓?fù)渑判?方法1acgbdhfebhacdgfe拓?fù)湫蛄校?拓?fù)渑判?方法2對有向無環(huán)圖利用深度優(yōu)先搜索進(jìn)行拓?fù)渑判?。acgbdhfebhacdgfe 此圖的一個拓?fù)湫蛄袨椋篴cgbdhfe退出DFS函數(shù)順序：efgdcahb 拓?fù)渑判?方法2最先退出DFS函數(shù)的頂點是出度為零的頂點，為拓?fù)渑判蛐蛄兄凶詈笠粋€頂點。因此，按退出DFS函數(shù)的先后記錄下來的頂點序列即為逆向的拓?fù)渑判蛐蛄?。結(jié)論： 拓?fù)渑判?方法2void DFS-ToplogicalSort () int v； for (v=0; vvexNum; +v) vertexsv.visited = false; / 訪問標(biāo)志初始化 Stack S; /存放頂點，按照出DFS的次序 for (v=0; v=0; w=NextAdjVex(v,w) if (!vertexsw.visited) DFS-T(w); / 對v的尚未訪問的鄰接頂點w遞歸調(diào)用DFS-T S.push(v); /頂點v的DFS函數(shù)執(zhí)行完畢 / DFS-T 拓?fù)渑判?方法2acgbdhfe寫出下圖的所有的