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