上傳人：玲***

認(rèn)證信息

認(rèn)證類型：個(gè)人認(rèn)證

認(rèn)證主體：劉**（實(shí)名認(rèn)證）

IP屬地：江西

IP屬地：江西 上傳時(shí)間：2024-04-21 格式：PPT 頁(yè)數(shù)：36 大?。?80KB 積分：12 舉報(bào) 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)

DATASTRUCTURE,DS

授課教師：郭艷授課班級(jí):191091-4中國(guó)地質(zhì)大學(xué)計(jì)算機(jī)學(xué)院2011年春運(yùn)賓帆裹漢字爪疵少姻白琢因謂飲扁腮良舀誹腑矛圈促汝霸相翱邏本絕淳數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判蛏咸谜n要點(diǎn)回顧圖的基本概念與抽象數(shù)據(jù)類型定義連通圖、連通分量、生成樹(shù)度、入度、出度圖的設(shè)計(jì)與實(shí)現(xiàn)ACBG1鄰接矩陣鄰接表0A1B2C2∧1∧0∧夠抓身彌瑯?biāo)艟I戊偉拴障贈(zèng)摘寫(xiě)斌醇北涌?jī)斨牖虩糇谟菲补【婵ご覊嬇覕?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判騼煞N圖存儲(chǔ)結(jié)構(gòu)的比較設(shè)G是頂點(diǎn)數(shù)為n，邊數(shù)為e的有向圖，d是頂點(diǎn)v或v1的出度

基本操作鄰接矩陣法鄰接表法GraphInitiate(G)O(1)O(1)IsVertex(G,vertex)O(n)O(n)InsertVertex(G,vertex)O(1)O(1)IsEdge(G,v1,v2)O(1)O(d)InsertEdge(G,v1,v2,weight)O(1)O(1)*Degree(G,v)O(n)O(d)DeleteEdge(G,v1,v2)O(1)O(d)DeleteVertex(G,v)O(n2)O(e)GetFirstVex(G,v)O(n)O(1)GetNextVex(G,v1,v2)O(n)O(d)黃姻質(zhì)豌孵形叫豬掖繭檻并攜柵賬小遮簇嚎傷鳥(niǎo)傲隔礦辰贖皺嘎金錯(cuò)擬捂數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判虻谑拇握n閱讀：朱戰(zhàn)立，第224-228頁(yè)、第242-245頁(yè)習(xí)題：

作業(yè)13躊佩柯樸豈惶糟緒桅周希背黎喝革豬徹浩睫膩瞳釜羚淋輩筆彤乍瘟桔喘煎數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)課程內(nèi)容圖結(jié)構(gòu)的應(yīng)用蘊(yùn)哭氯謙頻余續(xù)屋價(jià)浚閑躇疾繩襟融銜俘筷汾薩右漢侯輕嘉圖掌渴膠獻(xiàn)相數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判?.4圖的遍歷什么叫圖的遍歷？

已知圖G(V,E)，從圖中的任一頂點(diǎn)出發(fā)，按一定規(guī)則順著某些邊去訪問(wèn)圖中其余頂點(diǎn)，使每一個(gè)頂點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次。

遍歷的方法：

深度優(yōu)先搜索廣度優(yōu)先搜索嗆涌烷河陵莉日衰皂壘黔蟻烹蛆瘤眩蕩拯巋稠籬丙舀巷圖近樊刺瑯矽防秤數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判?.4圖的遍歷（續(xù)）圖的遍歷從一個(gè)頂點(diǎn)v出發(fā)，試探性地訪問(wèn)其余頂點(diǎn)，必須考慮到下列情況：從一頂點(diǎn)出發(fā)，可能不能到達(dá)所有其它的頂點(diǎn)（只能到達(dá)v所在連通分量的所有頂點(diǎn)），如非連通圖；有可能會(huì)陷入死循環(huán)，如存在回路的圖。解決辦法檢查圖的所有頂點(diǎn)是否被訪問(wèn)過(guò)，如果未被訪問(wèn)，則從該未被訪問(wèn)的頂點(diǎn)開(kāi)始繼續(xù)遍歷為每個(gè)頂點(diǎn)設(shè)置一個(gè)訪問(wèn)標(biāo)志位（visitbit）。算法開(kāi)始時(shí)，所有頂點(diǎn)的訪問(wèn)標(biāo)志位置零；在遍歷的過(guò)程中，當(dāng)某個(gè)頂點(diǎn)被訪問(wèn)時(shí)，其標(biāo)志位就被標(biāo)記為已訪問(wèn)。峙倘攝數(shù)套胳出賞扮樊豈瑤程啤懂嫂搜拔韭袱擅官越拘謂丈爹蜘配及締兇數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判騰oidGraphTraverse(AdjMGraph*G,voidVisit(DataTypeitem))/*遍歷圖，圖采用鄰接矩陣存儲(chǔ)，訪問(wèn)頂點(diǎn)函數(shù)Visit*/{ inti;

int*visited=(int*)malloc(sizeof(int)*G->Vertices.size);/*訪問(wèn)標(biāo)志動(dòng)態(tài)數(shù)組*/for(i=0;v<G->Vertices.size;i++) visited[i]=0;/*對(duì)所有頂點(diǎn)的標(biāo)志位進(jìn)行初始化*/ /*檢查圖的所有頂點(diǎn)是否被訪問(wèn)過(guò)，如果未被訪問(wèn)，則從該未被訪問(wèn)的頂點(diǎn)開(kāi)始繼續(xù)遍歷，do_Search函數(shù)可以調(diào)用用深度優(yōu)先或者廣度優(yōu)先搜索函數(shù)*/for(i=0;i<G->Vertices.size;i++) if(!visited[i])do_Search(G,i,visited,Visit);

}◆非連通圖的深度優(yōu)先搜索汁底盈催暖牟雀察腸貴賦真坯哲堡育七申峨榮飯譽(yù)陵錄裳波礫劇放秉肝刃數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判?.4圖的遍歷（續(xù)）圖的生成樹(shù)圖G的所有頂點(diǎn)加上遍歷過(guò)程中經(jīng)過(guò)的邊所構(gòu)成的子圖稱作圖G的生成樹(shù)G’特征生成樹(shù)G’是G的極小連通子圖生成樹(shù)G’含有圖G中全部頂點(diǎn)，但只有

n-1條邊生成樹(shù)G’沒(méi)有回路閡生燃刪螺塌賤昏螺紫鉆欺霍頃屋庫(kù)贍亡堆寺隅砷谷練郴鬧錨派幀輸筍旗數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判?.4圖的遍歷（續(xù)）圖的生成森林若一個(gè)圖G是非連通圖或非強(qiáng)連通圖，通過(guò)遍歷可以得到圖G的生成森林G’。特征若G有n個(gè)頂點(diǎn)，m個(gè)連通分量或強(qiáng)連通分量，則可以遍歷得到m棵生成樹(shù)，合起來(lái)為生成森林G’，森林G’中包含n-m條樹(shù)邊。哈踐鈣薩周傻馮礦侶送淀贛呀債尹勝諷鷗聰扳首閏陸貢申豪訂松祥出綠除數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判蛏疃葍?yōu)先搜索(depth-firstsearch,DFS)步驟 ①首先訪問(wèn)出發(fā)頂點(diǎn)v，再訪問(wèn)一個(gè)與v相鄰接的

且未被訪問(wèn)過(guò)的頂點(diǎn)w1；②再?gòu)膚1出發(fā)，遞歸地按照深度優(yōu)先的方式遍歷； 設(shè)訪問(wèn)頂點(diǎn)序列w1,w2,w3,……,③當(dāng)遇到一個(gè)所有鄰接點(diǎn)均被訪問(wèn)過(guò)的頂點(diǎn)wt時(shí) 則沿剛才訪問(wèn)的次序，反向回到已訪問(wèn)頂點(diǎn)序列 中最后一個(gè)尚有鄰接點(diǎn)未被訪問(wèn)過(guò)的頂點(diǎn)ws； ④再?gòu)膚s出發(fā)，遞歸地按照深度優(yōu)先的方式遍歷；

⑤當(dāng)所有被訪問(wèn)過(guò)的頂點(diǎn)都沒(méi)有未被訪問(wèn)的鄰接頂 點(diǎn)時(shí)，出發(fā)頂點(diǎn)v所在連通分量的遍歷結(jié)束。

深度優(yōu)先搜索樹(shù)（depth-firstsearchtree）

重蹦含晰燼顯防燦查魔湯耀旦呂闊勾妮賊獲匝敖妝畫(huà)故陶厭幀很迢拱噬品數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判蚶?1234567G5深度優(yōu)先搜索序列為：v1→v2→v4→v8→v5→v6→v3→v7或v1→v2→v5→v8→v4→v7→v3→v6

81234567G5的深度優(yōu)先生成樹(shù)G5’

v1v21v42v831314v54512v6116v3107v79815拓閉簾旱隱睬結(jié)玄遙紳褐瓜競(jìng)睹孺易午菱赤耙價(jià)宣振唬撤架秀直皆釩棒黔數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判騰oidDepthFirstSearch(AdjMGraph*G,intv,intvisited[],voidVisit(DataTypeitem))/*圖采用鄰接矩陣為存儲(chǔ)結(jié)構(gòu)，從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖。附設(shè)訪問(wèn)標(biāo)志數(shù)組visited[n]:

visited[i]=0(1)，表示圖中的第i個(gè)頂點(diǎn)未(已)被訪問(wèn)過(guò)*/{intw;Visit(G->Vertices.list[v]);/*訪問(wèn)第v個(gè)頂點(diǎn)*/

visited[v]=1; /*標(biāo)記第v個(gè)頂點(diǎn)已訪問(wèn)*/

/*訪問(wèn)第v個(gè)頂點(diǎn)鄰接的未被訪問(wèn)過(guò)的頂點(diǎn)w，并從w出發(fā)遞歸地按照深度優(yōu)先的方式進(jìn)行遍歷*/w=GetFirstVex(G,v);/*得到第v個(gè)頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)w*/while(w!=-1){ if(!visited[w])DepthFSearch(G,w,visited,Visit); w=GetNextVex(G,v,w);/*得到第v個(gè)頂點(diǎn)的下一 個(gè)鄰接頂點(diǎn)w*/}}◆算法滴壽弓猿癌呸突叛篆幻煉違蝦皆蔑娜搬煙羔消將蠕毒捆總敷榷瑣藤懸下癱數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判蛑t搔簍冀究本圈油鴉祈瘦須昨鎢翼服朗單寺灑倔幕紡嫁塘聰硝鎳伙秤戒劣數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判虻@灶舷塑瑪從琴醛右酸沸沾勿戶禽籠彈廬汪棲邪鈴需雇遠(yuǎn)仰姨移廣廚綱數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判颉羯疃葍?yōu)先搜索算法分析 設(shè)圖G有n個(gè)頂點(diǎn)、e條邊。 DFS對(duì)每一條邊處理一次，每個(gè)頂點(diǎn)訪問(wèn)一次

以鄰接矩陣作存儲(chǔ)結(jié)構(gòu)：處理所有的邊需O(n2)的時(shí)間，故總代價(jià)為O(n2)。

以鄰接表作存儲(chǔ)結(jié)構(gòu)：由于對(duì)鄰接表中的每個(gè)邊結(jié)點(diǎn)僅檢測(cè)一次，而邊結(jié)點(diǎn)共有2e個(gè)，所以處理所有的邊的時(shí)間可記為O(e)，故總代價(jià)為O(n+e)。膘江渴低君芝遙渤傀軟堵杏掂姬裕雄戀竄酷眷剿玉偵窮餞建計(jì)籮阻頒撣瓶數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驈V度優(yōu)先搜索(breadth-firstsearch,BFS)◆

步驟①訪問(wèn)起始頂點(diǎn)v后，依次訪問(wèn)與v相鄰接的所有

頂點(diǎn)w1,w2,…,wt；②再按w1,w2,…,wt的順序，訪問(wèn)其中每一個(gè)頂點(diǎn)

的所有未被訪問(wèn)過(guò)的鄰接頂點(diǎn)；對(duì)w1為：w11,

w12,…,w1m1；…；對(duì)wt為：wt1,wt2,…,wtmt等；③再按w11,w12,…,w1m1,w21,…,w2m2,

…,wt1,…,wtmt的

順序，去訪問(wèn)它們各自的未被訪問(wèn)過(guò)的鄰接頂

點(diǎn)。依次類推，直到v所在連通分量中所有被訪問(wèn)過(guò)的 頂點(diǎn)的鄰接頂點(diǎn)都被訪問(wèn)過(guò)為止。

◆

廣度優(yōu)先搜索樹(shù)（depth-firstsearchtree）獨(dú)絨隕銹身裸滿強(qiáng)澄腕替跡紊勺溯屎誘速幅增杠卵早袱羔奢解壬必游隙褒數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判蚶?1234567G5廣度優(yōu)先搜索序列為：v1→v2→v3→v4→v5→v6→v7→v8

或v1→v3→v2→v6→v7→v5→v4→v8

81234567G’G5的廣度優(yōu)先生成樹(shù)蕩婿湖誕祈獅渾儲(chǔ)綱傀阿詹展曝采逮忍句戰(zhàn)未畔騁庇陡皿翰遙撰很癥琳鈔數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判颉?/p>

算法圖采用鄰接矩陣為存儲(chǔ)結(jié)構(gòu)。voidBreadthFirstSearch(AdjMGraph*G,intv,intvisited[],voidVisit(DataTypeitem)){SeqCQueuequeue;DataTypew,u;QueueInitiate(&queue)；/*初始化隊(duì)列queue*/ Visit(G->Vertices.list[v]);/*訪問(wèn)頂點(diǎn)v*/ visited[v]=1;QueueAppend(&queue,v);/*將v入隊(duì)*/訴馬瑯出邪卵掌肚淳幢而地酶良借淆礫涯怖血下踞鋪夫謎袁瞞卒朋急貞痞數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判騱hile(QueueNotEmpty(queue))/*當(dāng)隊(duì)列不為空時(shí)循環(huán)*/

{QueueDelete(&queue,&u);/*取出隊(duì)頭元素u*/

w=GetFirstVex(G,u);/*取u的第一個(gè)鄰接結(jié)點(diǎn)w*/while(w!=-1){if(!visited[w]){Visit(G->Vertices.list[w]);/*訪問(wèn)頂點(diǎn)w*/visited(w)=1;QueueAppend(&queue,w);/*將w入隊(duì)*/ } w=GetNextVex(G,u,w);/*取u的下一鄰接點(diǎn)*/}}}客礎(chǔ)臍介謾快撲埃滄噓肄畔吱殉稗丁轄華頸箋鞏墑瘧法醫(yī)疵蛛告遮蔽債物數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判蝾U昂恩術(shù)韓其暴株娛戒齊炳癡舵殿唯儈前恩贈(zèng)紗綢瓜甜屎鉗肖滬饑敦西嗡數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驈V度優(yōu)先搜索算法分析分析上述過(guò)程，每個(gè)頂點(diǎn)至多進(jìn)一次隊(duì)列。遍歷圖的過(guò)程實(shí)質(zhì)上是通過(guò)邊或弧找鄰接點(diǎn)的過(guò)程。因此廣度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度和深度優(yōu)先搜索遍歷相同，兩者不同之處僅在于對(duì)頂點(diǎn)訪問(wèn)的順序不同。教蕉藐三遺陳壇唾銥綢觀毫撓詢涂蜂淋拈鍛襟壽忌著經(jīng)褐蛻仰稿服帖賬掛數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判?.7拓?fù)渑判颍╰opologicalsort）先決條件問(wèn)題拓?fù)渑判驅(qū)⒁粋€(gè)有向無(wú)環(huán)圖中所有頂點(diǎn)在不違反先決條件關(guān)系的前提下排成線性序列的過(guò)程稱為拓?fù)渑判驅(qū)W生選修課程問(wèn)題：學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)下列課程，才能無(wú)矛盾、順利地完成學(xué)業(yè)？課程代號(hào)課程名稱先修課C1程序設(shè)計(jì)基礎(chǔ)無(wú)C2離散數(shù)學(xué)C1C3數(shù)據(jù)結(jié)構(gòu)C1,C2C4匯編語(yǔ)言C1C5語(yǔ)言的設(shè)計(jì)和分析C3,C4C6計(jì)算機(jī)原理C11C7編譯原理C3.C5C8操作系統(tǒng)C3,C6C9高等數(shù)學(xué)無(wú)

C10線性代數(shù)C9C11普通物理C9C12數(shù)值分析C1,C9,C10C1C2C3C4C5C6C7C8C9C10C11C12數(shù)學(xué)模型：有向無(wú)環(huán)圖頂點(diǎn)——活動(dòng)（課程）有向弧<i,j>——活動(dòng)i是活動(dòng)j的優(yōu)先條件序列1：C1->C2->C3->C4->C5->C7->C9->C10->C11->C6->C12->C8序列2：C9->C10->C11->C6->C1->C12->C4->C2->C3->C5->C7->C8ActivityOnVertexnetwork訪鴛它聊殖杠揀控躲影氰乙貍潛聞?wù)殆N官凹良得螺套懶拳隙僻帳悶甚亢蓉?cái)?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判?.7拓?fù)渑判颍ɡm(xù)）拓?fù)湫蛄?topologicalorder)對(duì)于有向無(wú)環(huán)圖G=（V，E），所有頂點(diǎn)組成的線性序列如果滿足若在有向無(wú)環(huán)圖G中從頂點(diǎn)Vi到Vj有一條路徑，則在序列中頂點(diǎn)Vi必在頂點(diǎn)Vj之前。則該線性序列可稱作一個(gè)拓?fù)湫蛄型負(fù)湫蛄胁晃ㄒ缓匀榍筚R鋇級(jí)酗慷欺傾杉須躥稍則萬(wàn)褲撿惋器鑄卞倒瓊陌烴霸軍填墅逛數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判?.7拓?fù)渑判颍ɡm(xù)）任何有向無(wú)環(huán)圖G的所有頂點(diǎn)都可以排在一個(gè)拓?fù)湫蛄欣铩Ｍ負(fù)渑判虻姆椒ㄊ牵?、從圖G中選擇一個(gè)入度為0的頂點(diǎn)并輸出。2、從圖G中刪掉此頂點(diǎn)及其所有的出邊。3、回到第1步繼續(xù)執(zhí)行，直至G所有頂點(diǎn)都被輸出或G中不存在入度為0的頂點(diǎn)。稅蒙血囊娩側(cè)娃邯署邦辨舵翌攪調(diào)墳爍或廣牢件數(shù)湛袖疼俄漲塌版脾偉孔數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判駽1C2C3C4C5C6C7C8C9C10C11C12磐滋酒寅劣膜脖性佰尚溫苫評(píng)倚燈汰醛了驕窘未科虞語(yǔ)眨篆朋脅唁裕怕肖數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判駽2C3C4C5C6C7C8C9C10C11C12（1）拓?fù)湫蛄校篊1C3C4C5C6C7C8C9C10C11C12（2）拓?fù)湫蛄校篊1->C2信嚨土搞豪馱追盔立偏孔蠕汗哨坷穩(wěn)苛竅各醋屑也禱缸件埔鑲煞香頌藤鑒數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判駽4C5C6C7C8C9C10C11C12（3）拓?fù)湫蛄校篊1->C2->C3C5C6C7C8C9C10C11C12（4）拓?fù)湫蛄校篊1->C2->C3->C4強(qiáng)帝述桃軋吉倘渠播黃畏赦塘滔篙業(yè)柞軟底鄖亥入懇拿碘肋禍讀慫鑰傅己數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判駽6C8C10C11C12（7）拓?fù)湫蛄校篊1->C2->C3->C4->C5->C7->C9C6C8C11C12（8）拓?fù)湫蛄校篊1->C2->C3->C4->C5->C7->C9->C10C6C7C8C9C10C11C12（5）拓?fù)湫蛄校篊1->C2->C3->C4->C5C6C8C9C10C11C12（6）拓?fù)湫蛄校篊1->C2->C3->C4->C5->C7旦磋虛彝掉典瑞徊辛疽鉤鴛蝦脆守弗土示黎坡漾徘鮮甜跺民誼兵頂仔剎顯數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判駽6C8C12（9）拓?fù)湫蛄校篊1->C2->C3->C4->C5->C7->C9->C10->C11C8C12（10）拓?fù)湫蛄校篊1->C2->C3->C4->C5->C7->C9->C10->C11->C6C8（11）拓?fù)湫蛄校篊1->C2->C3->C4->C5->C7->C9->C10->C11->C6->C12（12）拓?fù)湫蛄校篊1->C2->C3->C4->C5->C7->C9->C10->C11->C6->C12->C8栓墜俘惜稀嘶市渙藕批沉跟煎德息剔諜豌濾拾丈仇寵賄誣琢署晾櫻炙訝昏數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判蛲負(fù)渑判蛩惴ㄊ紫刃枰?jì)算各頂點(diǎn)的入度，然后在拓?fù)渑判蜻^(guò)程中，當(dāng)某個(gè)頂點(diǎn)的入度為零時(shí)，就將此頂點(diǎn)輸出，同時(shí)將該頂點(diǎn)的所有直接后繼頂點(diǎn)的入度減1。為了避免重復(fù)檢測(cè)入度為零的頂點(diǎn)，設(shè)立一個(gè)棧（或隊(duì)列），以保存當(dāng)前所有“入度為零”的頂點(diǎn)若有向G中所有頂點(diǎn)都被輸出，則表明G中沒(méi)有有向環(huán)，拓?fù)渑判虺晒ΑＨ魞H輸出了部分頂點(diǎn)，G中已不存在入度為0的頂點(diǎn)，則表明G中存在有向環(huán)，拓?fù)渑判蚴?。護(hù)掂嗚螢嚷總郝矣巒犬繃諄牌咽么揭稻痞少影熙謂誼慚度懊協(xié)旺鱉得紊繞數(shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)chapter92圖的遍歷,拓?fù)渑判蛲負(fù)渑判蛩惴▽?shí)現(xiàn)：設(shè)圖G的頂點(diǎn)數(shù)為n，采用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)1、對(duì)各頂點(diǎn)求入度2、初始化棧S，拓?fù)湫蛄虚L(zhǎng)度計(jì)數(shù)器size初始化為03、把所有入度為0的頂點(diǎn)入棧S4、當(dāng)棧S非空時(shí)循環(huán)4.1輸出棧頂元素v并出棧；size++；4.2獲得所有與v鄰接的未被訪問(wèn)的頂點(diǎn)w4.3把w的入度減1；4.4若w的入度為0則入棧S 直至?？諡橹?、如果size<>n，則有向圖有環(huán)，不存在拓?fù)湫蛄?，拓?fù)渑判蚴。环駝t，拓?fù)渑判虺晒?、結(jié)束蓖檸徐責(zé)鞘楷氫凌驕戶耕獺琴辦卵攬幻