數(shù)據(jù)結(jié)構(gòu)mstppt課件-閱讀頁
2024-11-18 22:17本頁面
【正文】 取 E中第 i條邊 (u,v)。 //否則產(chǎn)生回路 ， 放棄此邊 if （ T已是一棵樹 ） then return T； }//endfor } 16 Kruskal算法（續(xù)） ?例子： 略 ?時(shí)間： ?對(duì)邊排序 O(elge) ?for循環(huán)中： 檢測每條邊的兩個(gè)頂點(diǎn)是否在同一連通分量 （ 樹 ） 上 只要采用合適的數(shù)據(jù)結(jié)構(gòu) ， 檢測時(shí)間為 O(lge) 因此 ， 此時(shí)間亦為 O(elge)。 17 167。 ?二元關(guān)系： 集合 A B的一個(gè) 子集 R， 稱為集合 A與 B上的一個(gè)二元關(guān)系 ，簡稱關(guān)系 。 若 (x， y)∈ R， 則稱 x和 y有關(guān)系 R， 亦可記為 xRy，否則 x和 y沒有關(guān)系 R， 記為 xRy。 ?集合 A上的關(guān)系 R是 對(duì)稱的 ， 若 xRy， 則 yRx。 ?集合 A上的關(guān)系 R是 反對(duì)稱的 ， 若 xRy， yRx,則必有 x＝ x,y ∈ A。 其中 x,y,z ∈ A。 偏序關(guān)系 R一般記為 ≤ ，若將關(guān)系看作是比較，則偏序關(guān)系是指集合中僅有 部分 元素是可以比較的。 數(shù)集合上的大小關(guān)系是全序關(guān)系 全序關(guān)系是指集合中 全體成員 之間均可比較。 這種給頂點(diǎn)定序的操作稱為拓?fù)渑判?。 唯一嗎 ？ ?幾何意義： 將 G中頂點(diǎn)按拓?fù)湫蛄械拇涡蚺懦梢恍?， 則 G中所有的有向邊的指向均為從在到右 ?例子： v2 v3 v1 v4 v3 v1 v2 v4 21 相關(guān)概念 ?拓?fù)渑判? ?拓?fù)渑判虺晒Φ某湟獥l件： 無環(huán) 。 若 G表示施工圖、生產(chǎn)流程圖、學(xué)習(xí)計(jì)劃安排，則在只能串行工作時(shí)，拓?fù)湫蛄惺且环N可行的方案或計(jì)劃。 NonPreFirstTopSort（ G） { while( G中有入度為 0的頂點(diǎn) ) do { 從 G中選 1個(gè)入度為 0的頂點(diǎn) v輸出之； 從 G中刪 v及其出邊，出邊終點(diǎn)的入度減 1； } if ( 輸出的頂點(diǎn)數(shù) | V(G) | ) then Error ( “G有環(huán)，排序失敗” )。 NonSuccFirstTopSort（ G） { //應(yīng)選 G的逆鄰接表 while( G中有出度為 0的頂點(diǎn) ) do { 從 G中選 1個(gè)出度為 0的頂點(diǎn) v輸出之； 從 G中刪 v及其入邊，入邊起點(diǎn)的出度減 1； } if ( 輸出的頂點(diǎn)數(shù) | V(G) | ) then Error ( “G有環(huán)，排序失敗” )。 ?算法： DFSTopSort（ G， i， T） { //在 DFSTraverse中調(diào)用此算法 ， T是棧 visited[i]=TRUE。T, i） //從 i出發(fā)的搜索已完成，輸出 i } ?特點(diǎn)： 與 NonSuccFirstTopSort算法類似； 若 G有環(huán)，則不能正常工作
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1