【正文】 P(1 = P = 10,000)個(gè)雙向的小路連接。 最短路徑 Dijkstra算法 ? 第八步 ? 算法描述 2： SP_Dijkstra(G, s) //求單源 s到其它點(diǎn)的最短距離 for i=1 to n do dis[i] ? ∞ // 初始化每點(diǎn)到 s距離 inA[i] ? false //設(shè)頂點(diǎn)不在 A中 dis[s] ? 0 //將 dis[s]設(shè)為 0，準(zhǔn)備取出 for i=1 to n do v ? getmin() //取 dis[?]中最小的值 c和頂點(diǎn) v, inA[ v ] ? true //v放入 A中 sum ? sum+c //c加入 MST的總和中 updata( v ) //檢查 (v,B),松馳 dis[? ] 最短路徑 Dijkstra算法 與 prim不相同點(diǎn) cooking Bessie喜歡為在外面的奶牛做晚餐， Bessie按響鈴給他們一個(gè)信號(hào)叫他們進(jìn)來(lái)就可以了。否則轉(zhuǎn) (2) 最短路徑 Dijkstra算法 ? 算法描述圖示 ： 邊權(quán) =0,如果 dis[v] dis[x]，則 x永遠(yuǎn)不會(huì)松馳 v，故 v點(diǎn)確定下來(lái)。 ? 算法描述 1： SP_Dijkstra(G, s) (1)將 G中頂點(diǎn)分成兩個(gè)集合 A、 B， A集合中由已經(jīng)求出最短路徑的頂點(diǎn)組成， B集合是其它頂點(diǎn)。 x與 y之間的距離是 len[x][y]，則有下面的“ 三角形定理 ”： dis[x] + len[x][y] = dis[y] ? 松馳 若在處理過(guò)程中，有兩點(diǎn) x、 y出現(xiàn)不符合“三角形定理”，則可改進(jìn)一下 —松馳 ： if ( dis[x]+len[x][y] dis[y] ) dis[y] = dis[x]+len[x][y]。統(tǒng)稱 單源最短路徑問(wèn)題 。 簡(jiǎn)單講： 找出連接兩個(gè)給定點(diǎn)的最低成本路徑 ? 單源最短路徑問(wèn)題 ：求從源點(diǎn) s到其它所有點(diǎn)的最短路徑問(wèn)題。 最好： M*N*N=24,000,000 超 1s ? 動(dòng)態(tài)維護(hù)樹 構(gòu)成第一棵 MST 讀入邊 e(a,b,c)， BFS找 , 所在路徑，取其中邊最大的 x,如果 ，刪除邊 x,加入邊 e. M*N 1,200,000 ? 簡(jiǎn)化算法？ 由于每次只保留 N1條邊，每次重新做 Kruskal算法： M*N*logN 9,600,000 大致可行。 ? 如果可以了，你從已經(jīng)修復(fù)的邊中，選擇一些邊，使得這些邊的總長(zhǎng)度最小，輸出最小值。 最小生成樹 (MST)實(shí) 例二 輸入格式： ? 第一行 : 兩個(gè)整數(shù)： N， W。注意：兩個(gè)點(diǎn)之間可能有多條邊。但是一開始，所有的邊都是被破壞了的，即不可用。注：邊只能水源、居民點(diǎn)之間直接相連。 //加入這條邊的權(quán) if (++c == n1) break。 //右端點(diǎn)所在連通塊 “根 ” if(v != u) //如果不在同一連通塊 union(v,u)。 //取邊的計(jì)數(shù)器 for i=1 to m do //從小到大取邊 v ?find_set( e[i].v )。 //初始化并查集 sort( e, e+m)。 x,y為兩集合的“根” void union(int x,y ) { f[x] = y。 return (f[x])。 i++) f[ i ] = i。 for (i=1。 最小生成樹 (MST) Kruskal算法 ? 并查集 ： 并查集詳細(xì)內(nèi)容可參見有關(guān)文章。 begin f[x]:=y。 //合并兩個(gè)集合。 exit(f[x])。 //查找 x所在類的“根” 代表，并壓縮路徑 function find_set(x:longint):longint。下面是 Pascal段： //初始化，使每個(gè)集合只一個(gè)元素。 ? 并查集 ： 連通點(diǎn)集之類問(wèn)題，有高效算法 并查集 。 ? 問(wèn)題可化為 ： 判斷邊 (x,y)的兩個(gè)頂點(diǎn) x,y在圖（實(shí)際是森林）mst中最否已經(jīng)連通。 最小生成樹 (MST)Prim算法 ? 算法描述 2： MST_Prim(G, r) //從任意點(diǎn) r出發(fā)，生長(zhǎng)成一 MST for i=1 to n do dis[i] ? ∞ // 初始化每點(diǎn)到 A集合的最小值 inA[i] ? false //設(shè)頂點(diǎn)不在 A中 dis[r] ? 0 //將 r設(shè)為 0（或 ∞ ），準(zhǔn)備取出 for i=1 to n do v ? getmin() //取 dis[?]中最小的值 c和頂點(diǎn) v, inA[ v ] ? true //v放入 A中 sum ? sum+c //c加入 MST的總和中 updata( v ) //枚舉交叉邊 (v,B),改進(jìn) dis[ ] 最小生成樹 (MST)Prim算法 ? 算法描述 3： MST_Kruskal(G) (1)將 G所有條邊按權(quán)從小到大排序；圖 mst開始為空 (2)從小到大次序取邊 (x,y) (3)若加入邊 (x,y)， mst就有環(huán)，則放棄此邊，轉(zhuǎn) (2) (4)將邊 (x,y)加入 mst，如果已經(jīng)加了 n1條邊，結(jié)束。 其實(shí)每次 A中只是增加一個(gè)新頂點(diǎn) v，最多有交叉邊 (v,y)，修改量只有與 v有邊的頂點(diǎn)，為 O(n)。否則，轉(zhuǎn) (3) ? 算法證明 ： 根據(jù)剪切屬性 圖 (?) 最小生成樹 (MST)Prim算法 ? 算法要點(diǎn) ： 每次求最小權(quán)交叉邊時(shí)，如果都重新計(jì)算，則顯然要枚舉 (x,y) x∈ A ,y∈ B。反之不然。 最小生成樹 (MST)算法原理 7 4 9 ? 最小邊原則 ：圖中權(quán)值最小的邊 (如果唯一的話 )一定在最小生成樹上。交叉邊為地些頂點(diǎn)在兩個(gè)不同集合的邊?，F(xiàn)在我們需要除去一些連線，使得網(wǎng)絡(luò)中沒(méi)有回路，并且被除去網(wǎng)線的 Σ f(i,j)最大，請(qǐng)求出這個(gè)最大值。 簡(jiǎn)單講： 找出連接所有點(diǎn)的最低成本路線 最小生成樹 (MST)定 義 紅邊連接了所有頂點(diǎn) , 所以構(gòu)成一棵生成樹 權(quán)和 =1+2+4+4+7+8+9 局域網(wǎng) ()[RQNOJ] 某局域網(wǎng)內(nèi)有 n(n=100)臺(tái)計(jì)算機(jī)，由于建網(wǎng)時(shí)工作人員的疏忽，現(xiàn)在網(wǎng)內(nèi)存在回路，造成網(wǎng)絡(luò)卡的現(xiàn)象。 屬性： |v|1條邊、連通、無(wú)環(huán)。 visited[jid]=++S_index。j!=NULL。 visited[k] = ++search_index。fron=back。 front=back=0。 void BFS( int k ) { int front,back。k++) if ( !visited[k] ) BFS( k )。 for(k=0。kn_nodes。 標(biāo)識(shí)項(xiàng)點(diǎn)有沒(méi)有訪問(wèn)過(guò) 每個(gè)頂點(diǎn)都有鄰接鏈表 鄰接鏈表的節(jié)點(diǎn) 數(shù)據(jù)結(jié)構(gòu) 圖的寬度優(yōu)先 (BreadthFirst)遍歷 :鄰接鏈表、 C++