【文章內(nèi)容簡介】 3 1 1 6 3 1 4 1 6 4 3 1 4 2 1 1 6 4 3 2 1 4 2 5 1 6 5 4 3 2 1 4 2 5 3 3到 2和 5中 ,到 2最短 1 ??????????????????????????????062460632055465051350651601 2 3 4 5 6 1 2 3 4 5 6 1 2 1 4 1 1 例 1 6 5 4 3 2 6 5 1 3 5 6 6 4 2 5 1 5 1 3 1 6 5 4 3 2 6 5 1 3 5 6 6 4 2 5 1 6 5 4 3 2 1 4 2 5 3 以頂點 6為起始點 ?方法二：克魯斯卡爾 (Kruskal)算法 ?算法思想：設(shè)連通網(wǎng) N=(V,{E})， 令最小生成樹 ?初始狀態(tài)為只有 n個頂點而無邊的非連通圖 T=(V,{?})，每個頂點自成一個連通分量 ?在 E中選取代價最小的邊，若該邊依附的頂點落在 T中不同的連通分量上，則將此邊加入到 T中；否則，舍去此邊，選取下一條代價最小的邊 ?依此類推，直至 T中所有頂點都在同一連通分量上為止 例 1 6 5 4 3 2 6 5 1 3 5 6 6 4 2 5 1 6 5 4 3 2 1 2 3 4 5 （ 0）用頂點數(shù)組和邊數(shù)組存放頂點和邊信息 （ 1）初始時，令每個頂點的 jihe互不相同；每個邊的 flag為 0 （ 2）選出權(quán)值最小且 flag為 0的邊 （ 3）若該邊依附的兩個頂點的 jihe 值不同，即非連通，則令 該邊的 flag=1, 選中該邊；再令該邊依附的兩頂點的 jihe 以及兩集合中所有頂點的 jihe 相同 若該邊依附的兩個頂點的 jihe 值相同，即連通，則令該 邊的 flag=2, 即舍去該邊 （ 4）重復(fù)上述步驟，直到選出 n1條邊為止 頂點結(jié)點： typedef struct { int data。 //頂點信息 int jihe。 }VEX。 邊結(jié)點： typedef struct { int vexh, vext。 //邊依附的兩頂點 int weight。 //邊的權(quán)值 int flag。 //標(biāo)志域 }EDGE。 ?算法實現(xiàn)： 例 1 6 5 4 3 2 6 5 1 3 5 6 6 4 2 5 ?算法描述： data jihe 1 2 4 5 3 6 1 2 4 5 3 6 1 2 4 5 3 6 vexh weight 1 1 2 2 1 3 2 3 3 5 4 4 vext flag 6 1最小 5 3 5 5 0 0 0 0 0 0 0 1 3 4 2 5 6 7 8 9 3 3 4 5 5 6 6 6 6 4 2 6 0 0 0 0 1 11 114 211 122 2 2 2 1 6 5 4 3 2 1 2 3 4 5 ?一個無環(huán)的有向圖稱做 有向無環(huán)圖 （ directed acycline praph）。簡稱 DAG圖 ?有向無環(huán)圖 應(yīng)用：描述公共子式 表達(dá)式；工程；系統(tǒng) 的有效工具。 ?關(guān)于 工程： 計劃、施工過程、生產(chǎn)流程、程序流程等都可看成一個工程。 ?活動 (子工程 )； 一個大的工程常常被劃分成許多較小的子工程，這些 子工程 稱為 活動 ，這些活動完成時，整個工程也就完成了。 ?主要的兩個方面 : ?工程的 可行性 。 ?估算整個工程完成所必須的 最短時間 (拓?fù)渑判?、求關(guān)鍵路徑 ) 有向樹、 DAG圖和有向圖示意 ?P179利用有向無環(huán)圖表達(dá)含公共子式的表達(dá)式 ?利用有向無環(huán)圖，可將相同子式共享，以減少信息的重復(fù)表達(dá)。 ?無向圖中，若 DFS過程中遇到回邊，則必定存在環(huán)。 ?有向圖中， DFS的回邊可能是指向 DFS生成森林的另一棵生成樹上頂點的弧。 ?有向圖中， DFS中 v到 u路徑，但又出現(xiàn) u到 v的回邊，則必定存在包含 v和 u的環(huán)。 167。 拓?fù)渑判? ?問題提出：學(xué)生選修課程問題 頂點 —— 表示課程 有向弧 —— 表示先決條件，若課程 i是課程 j的先決條件，則圖中有弧 i,j 學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾、順利地完成學(xué)業(yè) —— 拓?fù)渑判? ? 定義 ?AOV網(wǎng) —— 用頂點表示活動，用弧表示活動間優(yōu)先關(guān)系的有向圖稱為 頂點表示活動的網(wǎng) (Activity On Vertex work)， 簡稱 AOV網(wǎng) ?若 vi,vj是圖中有向邊，則 vi是 vj的直接前驅(qū)； vj是 vi的直接后繼 ,并且具有傳遞性。 ?AOV網(wǎng)中不允許有回路，這意味著某項活動以自己為先決條件（此工程是無法完成的） 167。 拓?fù)渑判? ?拓?fù)渑判?:(數(shù)學(xué)中 ) 由某個集合上的一個 偏序得到該集合上的一個 全序 ,這個操作過程叫 拓?fù)渑判?。 ?偏序 :直觀地說指集合中僅有部分成員之間可比較。 ?全序 :指集合中全體成員之間均可比較。 ?表示偏序和全序的有向圖 P180圖 ?拓?fù)渑判?—— 把 AOV網(wǎng)絡(luò)中各頂點按照它們相互之間的優(yōu)先關(guān)系排列成一個 有序 序列的過程叫 ~ ?檢測 AOV網(wǎng)中是否存在環(huán) （回路） 方法 （拓?fù)渑判颍?：對有向圖構(gòu)造其頂點的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點都在它的拓?fù)溆行蛐蛄兄校瑒t該 AOV網(wǎng)必定不存在環(huán) ?拓?fù)渑判虻姆椒? ?在有向圖中選一個沒有前驅(qū)的頂點且輸出之 ?從圖中刪除該頂點和所有以它為尾的弧 ?重復(fù)上述兩步，直至全部頂點均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點為止 例 課程代號 課程名稱 先修棵 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 無 C1 C1,C2 C1 C3,C4 C11 C3,C6 無 C9 C9 C1,C9,C10 程序設(shè)計基礎(chǔ) 離散數(shù)學(xué) 數(shù)據(jù)結(jié)構(gòu) 匯編語言 語言的設(shè)計和分析 計算機原理 編譯原理 操作系統(tǒng) 高等數(shù)學(xué) 線性代數(shù) 普通物理 數(shù)值分析 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓?fù)湫蛄校?C1C2C3C4C5C7C9C10C11C6C12C8 或 ： C9C10C11C6C1C12C4C2C3C5C7C8 一個 AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏? C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓?fù)湫蛄校?C1 （ 1） C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓?fù)湫蛄校?C1C2 （ 2） C4 C5 C6 C7 C8 C9 C10 C11 C12 拓?fù)湫蛄校?C1C2C3 （ 3） C5 C6 C7 C8 C9 C10 C11 C12 拓?fù)湫蛄校?C1C2C3C4 （ 4） C6 C8 C10 C11 C12 拓?fù)湫蛄校?C1C2C3C4C5C7C9 C6 C8 C11 C12 拓?fù)湫蛄校?C1C2C3C4C5C7C9 C10 （ 8） C6 C7 C8 C9 C10 C11 C12 拓?fù)湫蛄校?C1C2C3C4C5 （ 5） C6 C8 C9 C10 C11 C12 拓?fù)湫蛄校?C1C2C3C4C5C7 （ 6） C6 C8 C12 拓?fù)湫蛄校?C1C2C3C4C5C7C9 C10C11 （ 9） C8 C12 拓?fù)湫蛄校?C1C2C3C4C5C7C9 C10C11C6 （ 10） C8 拓?fù)湫蛄校?C1C2C3C4C5C7C9 C10C11C6C12 （ 11） 拓?fù)湫蛄校?C1C2C3C4C5C7C9 C10C11C6C12C8 （ 12） ?算法實現(xiàn)（棧） ?以鄰接表作存儲結(jié)構(gòu) ?把鄰接表中所有入度為 0的頂點進(jìn)棧 ?棧非空時，輸出棧頂元素 Vj并退棧；在鄰接表中查找Vj的直接后繼 Vk， 把 Vk的入度減 1；若 Vk的入度為 0則進(jìn)棧 ?重復(fù)上述操作直至?？諡橹?。若?？諘r輸出的頂點個數(shù)不是 n， 則有向圖有環(huán)；否則，拓?fù)渑判蛲戤? 鄰接表結(jié)點： typedef struct node { int vex。 //頂點域 struct node *next。 //鏈域 }JD。 表頭結(jié)點： typedef struct tnode { int in。 //入度域 struct node *link。 //鏈域 }TD。 TD g[M]。 //g[0]不用 3 2 1 0 4 ?算法描述 例 1 2 3 4 5 6 0 1 2 2 in link 5 5 4 3 ^ ^ ^ vex next 3 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ top 1 6 top top 0 1 2 2 in link 5 5 4 3 ^ ^ ^ vex next 3 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 3 2 1 0 4 1 6 top top 0 1 2 2 in link 5 5 4 3 ^ ^ ^ vex next 3 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 3 2 1 0 4 1 top p 0 1 2 2 in link 5 5 4 3 ^ ^ ^