第七章圖（graphs）-預(yù)覽頁
【正文】 網(wǎng)頁設(shè)計 中國網(wǎng)頁設(shè)計 圖的遍歷 圖的遍歷： 從某個結(jié)點出發(fā)，訪問圖的每個結(jié)點恰好一次。 訪問 v1的鄰接點 w1,w2,…,wm。 模型 ： n個結(jié)點的圖，結(jié)點連線的權(quán)表示建設(shè)兩點間通信線路的費用。 中國網(wǎng)頁設(shè)計 最小生成樹 Prim算法 假設(shè) N=(V， {E})是連通網(wǎng)， T=(U,{TE})表示下列算法構(gòu)造的 N上最小生成樹。 中國網(wǎng)頁設(shè)計 最小生成樹 普里姆算法 A DB CE6941 27685A DB CEA DB CE6A DB CE675A DB CE6475A DB CE67無 向 網(wǎng) N初 始 狀 態(tài) A 作 為 開 始 頂 點 B 放 入 集 合 U 中D 放 入 集 合 U 中 E 放 入 集 合 U 中 C 放 入 集 合 U 中中國網(wǎng)頁設(shè)計 v1 v3 v2 v4 v5 4 8 5 7 12 11 3 6 (a) v2 v4 5 (b) (c) v5 3 v2 v4 5 (d) v1 4 v5 3 v2 v4 5 v3 6 (e) v1 4 v5 3 v2 v4 5 圖 721 按 prime算法從 v2出發(fā)構(gòu)造最小生成樹的過程 中國網(wǎng)頁設(shè)計 最小生成樹 Prim算法 中國網(wǎng)頁設(shè)計 最小生成樹 Kruskal算法 ① 克魯斯卡爾 基本思想 ： 考慮問題的出發(fā)點 : 為使生成樹上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小。其中有些課程要求先修課程，有些則不要求。 C2 C1 C3 C4 C5 C8 C9 C7 C6 ? AOV活動能夠順利進(jìn)行的條件是不存在有向環(huán) 。 C2 C1 C3 C4 C5 C8 C9 C7 C6 中國網(wǎng)頁設(shè)計 ? 如果 AOV網(wǎng)絡(luò)存在一個拓?fù)湫蛄?，則該 AOV網(wǎng)絡(luò)中必定不會出現(xiàn)有向環(huán) ? 相反，如果不存在拓?fù)湫蛄?，則說明 AOV網(wǎng)絡(luò)中存在有向環(huán)，此 AOV網(wǎng)絡(luò)所代表的工程是不可行的。 中國網(wǎng)頁設(shè)計 V 1 V 2 V 3 V 5 a 1 = 5 a 2 = 4 a 4 = 2 a 5 = 1 頂點表示事件，弧表示活動，權(quán)表示活動持續(xù)的時間。 事件（頂點）的最晚開始時間： vl(i) = 從頂點 i到匯點的最短路徑長度。 中國網(wǎng)頁設(shè)計 最短路徑 設(shè) G是帶權(quán)有向圖 ， 最短路徑問題 ：如果從圖中某一頂點出發(fā)到達(dá)另一頂點的路徑可能不止一條 ， 如何找到一條長度最小的路徑 。 2. 求出源點到各個頂點下一個最短路徑：設(shè)其終點是 u，則 v0到 u的最短路徑或者是邊 v0,u，或者由一條已求得的最短路徑（ v0… v)和邊 v,u構(gòu)成； 3. 重復(fù) 2直到從頂點 v0到其它各頂點的最短路徑全部求出為止 。 (n1)/2 C. n(n+1)/2 D. 0 E. n2 一個 n個頂點的連通無向圖，其邊的個數(shù)至少為（ ）。 A． 1/2 B． 2 C． 1 D． 4 D D B B C 中國網(wǎng)頁設(shè)計 下面結(jié)構(gòu)中最適于表示稀疏無向圖的是（ C ），適于表示稀疏有向圖的是（ B
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1