小生成樹并查集最短路-在線瀏覽
2025-07-16 11:21本頁面
【正文】 ？ 并查集 ? 每個集合用一棵 “ 有根樹 ” 表示 ? 定義數(shù)組 set[1..n] ? set[i] = i , 則 i表示本集合，并是集合對應(yīng)樹的根 ? set[i] = j, ji, 則 j 是 i 的父節(jié)點 . 1 2 3 4 5 6 7 8 9 10 1 2 3 2 1 3 4 3 3 4 i Set(i) 1 5 2 4 7 10 3 6 8 9 并查集 find2(x) { r = x。 return r。 else set[a] = b。 set[b] = a。 else set[b] = a。 while (set[r] != r) r = set[r]。 } 最壞情況 Θ(log N) Θ(1) 并查集 ? 思想： 每次查找的時候，如果路徑較長，則修改信息，以便下次查找的時候速度更快（ 路徑壓縮 ） ? 步驟 : ? 第一步，找到根結(jié)點 ? 第二步，修改查找路徑上的 所有節(jié)點 ，將它們都指向根結(jié)點 并查集 ? find3(x) ? { ? r = x。 ? i = x。 ? set[i] = r。 ? } } 并查集 9 10 8 12 20 21 16 4 6 11 1 6 4 11 1 10 12 9 8 20 21 16 并查集 ? 最小生成樹紅色字體的兩個函數(shù)： ? int findroot(int p){ //找父親 if(father[p]!=p) father[p]=findroot(father[p])。 } ? void unionset(int p,int q){ //合并集合 father[q]=p。省政府 “ 暢通工程 ” 的目標(biāo)是使全省任何兩個城鎮(zhèn)間都可以實現(xiàn)交通（但不一定有直接的道路相連，只要互相間接通過道路可達(dá)即可）。 ? int findx(int x) ? { ? int r=x。 ? return r。 ? fx = findx(x)。 ? if(fx != fy) ? bin[fx] = fy。 ? while(scanf(%d,amp。i=n。 ? for(scanf(%d,amp。m0。x,amp。 ? merge(x,y)。i=n。 ? printf(%d\n,count)。s Life ? HDU1198 Farm Irrigation 最短路徑 SPFA ? 求單源最短路的 SPFA算法的全稱是：Shortest Path Faster Algorithm。 最短路徑 SPFA ? 很多時候，給定的圖存在負(fù)權(quán)邊，這時類似Dijkstra等算法便沒有了用武之地，而 BellmanFord算法的復(fù)雜度又過高， SPFA算法便派上用場了。當(dāng)然，我們可以在執(zhí)行該算法前做一次拓?fù)渑判?，以判斷是否存在?fù)權(quán)回路，但這不是我們討論的重點。我們采取的方法是松弛：設(shè)立一個先進(jìn)先出的隊列用來保存待優(yōu)化的結(jié)點，優(yōu)化時每次取出隊首結(jié)點 u，并且用 u點當(dāng)前的最短路徑估計值對離開 u點所指向的結(jié)點 v進(jìn)行松弛操作，如果 v點的最短路徑估計值有所調(diào)整，且 v點不在當(dāng)前的隊列中，就將 v點放入隊尾。 最短路徑 SPFA ? 定理 : 只要最短路徑存在，上述 SPFA算法必定能求出最小值。換言之，每次的優(yōu)化將會有某個點
研究報告相關(guān)推薦
鄂ICP備17016276號-1