Java圖論進(jìn)階之最小生成樹算法詳解
1. 最小生成樹
連通圖中的每一棵生成樹 , 都是原圖的極大無環(huán)子圖 , 即: 從中刪去任何一條邊 , 生成樹就不再連通;反之 , 在其中引入任何一條新邊 , 都會形成一條回路.
若連通圖由n個頂點(diǎn)組成 , 則其生成樹必含n個頂點(diǎn)和n-1條邊 , 因此構(gòu)造最小生成樹有三個準(zhǔn)則:
- 1.只能使用圖中的邊來構(gòu)造最小生成樹
- 2.只能使用恰好n-1條邊來連接圖中的n個頂點(diǎn)
- 3.選用的n-1條邊不能構(gòu)成回路
常見求解最小生成樹的算法有: Kruskal算法和Prime算法.兩種算法都采用逐步求解的貪心策略.
貪心算法: 通過局部最優(yōu)解來推出全局最優(yōu)解.
1.1 Kruskal(克魯斯卡爾) 算法
給定一個有n個頂點(diǎn)的連通網(wǎng)絡(luò)N={V,E}
首先構(gòu)造一個由這n個頂點(diǎn)組成 , 不含任何邊的圖G={V,NULL}.
其次不斷從E中取出權(quán)值最小的一條邊(若有多條任選其一) , 若該邊的兩個頂點(diǎn)來自不同的連通分量 , 則將此邊加入到G中.
如此反復(fù) , 直到G中邊數(shù)達(dá)到頂點(diǎn)數(shù)-1為止.
核心: 每次迭代時 , 選出權(quán)值最小且兩端點(diǎn)不在同一連通分量上的邊 , 加入生成樹.
步驟分析:
1.由于該算法的思想是全局貪心 , 因此將所有圖中所有邊全部放入優(yōu)先級隊列中.
2.構(gòu)造一個最小生成樹 , 將優(yōu)先級隊列中的邊依次加入.
3.為了防止出現(xiàn)環(huán) , 使用并查集判斷每次取出的邊的頂點(diǎn)是否來自同一個集合 .
4.如果不是同一集合 , 將該邊加入最小生成樹并用并查集將該邊的領(lǐng)接頂點(diǎn)放入同一個 集合.
代碼示例:
/** * 克魯斯卡爾算法實(shí)現(xiàn) * @param minTree * @return */ /** * 模擬實(shí)現(xiàn)一條邊 */ static class Edge{ public int srcIndex; public int destIndex; public int weight; public Edge(int srcIndex, int destIndex, int weight) { this.srcIndex = srcIndex; this.destIndex = destIndex; this.weight = weight; } } public int kruskal(GraphOfMatrix minTree) { //1.定義一個優(yōu)先級隊列 PriorityQueue<Edge> minQ = new PriorityQueue<Edge>(new Comparator<Edge>() { @Override public int compare(Edge o1, Edge o2) { return o1.weight - o2.weight; } }); int n = arrayV.length; //2.遍歷領(lǐng)接矩陣,將所有的邊都放入優(yōu)先級隊列中 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i < j && Matrix[i][j] != Integer.MIN_VALUE) { minQ.offer(new Edge(i, j, Matrix[i][j])); } } } //3.構(gòu)造并查集將符合要求的邊加入到最小生成樹中 UnionFindSet ufs = new UnionFindSet(n); int size = 0;//記錄最小生成樹中邊的數(shù)量 int totalWeight = 0;//記錄權(quán)值 while (size < n - 1 && !minQ.isEmpty()) { Edge edge = minQ.poll(); int srcIndex = edge.srcIndex; int destIndex = edge.destIndex; //同一邊的相鄰頂點(diǎn)不能來自同一集合 if (!ufs.isSameUnionFindSet(srcIndex, destIndex)) { //將符合條件的邊加入到最小生成樹中 minTree.addEdgeUseIndex(srcIndex, destIndex, Matrix[srcIndex][destIndex]); System.out.println("選擇的邊"+arrayV[srcIndex]+" -> "+arrayV[destIndex]+Matrix[srcIndex][destIndex]); size++; totalWeight += Matrix[srcIndex][destIndex]; //將添加過的邊的相鄰頂點(diǎn)放入同一集合,防止出現(xiàn)環(huán). ufs.union(srcIndex, destIndex); } } if (size == n - 1) { return totalWeight; } else { throw new RuntimeException("沒有最小生成樹"); } } //按照下標(biāo)將邊加入到最小生成樹中 public void addEdgeUseIndex(int srcIndex,int destIndex,int weight){ Matrix[srcIndex][destIndex] = weight; //如果是無向圖鄰接矩陣對稱位置也要添加 if (!isDirect){ Matrix[destIndex][srcIndex] = weight; } } //測試克魯斯卡爾算法 public static void main(String[] args) { String str = "abcdefghi"; char[] array =str.toCharArray(); graph.GraphOfMatrix g = new graph.GraphOfMatrix(str.length(),false); g.initArray(array); g.addEdge('a', 'b', 4); g.addEdge('a', 'h', 8); //g.addEdge('a', 'h', 9); g.addEdge('b', 'c', 8); g.addEdge('b', 'h', 11); g.addEdge('c', 'i', 2); g.addEdge('c', 'f', 4); g.addEdge('c', 'd', 7); g.addEdge('d', 'f', 14); g.addEdge('d', 'e', 9); g.addEdge('e', 'f', 10); g.addEdge('f', 'g', 2); g.addEdge('g', 'h', 1); g.addEdge('g', 'i', 6); g.addEdge('h', 'i', 7); graph.GraphOfMatrix kminTree = new graph.GraphOfMatrix(str.length(),false); System.out.println(g.kruskal(kminTree)); kminTree.printGraph(); }
構(gòu)造并查集:
public class UnionFindSet { public int[] elem; public UnionFindSet(int n){ this.elem = new int[n]; Arrays.fill(elem,-1); } /** * 查找數(shù)據(jù)x的根節(jié)點(diǎn) * @param x * @return */ public int findRoot(int x){ if (x < 0){ throw new RuntimeException("下表不合法"); } while (elem[x] >= 0){ x = elem[x]; } return x; } /** * 查詢x1和x2是不是同一個集合 * @param x1 * @param x2 * @return */ public boolean isSameUnionFindSet(int x1 , int x2){ int index1 = findRoot(x1); int index2 = findRoot(x2); if (index1 == index2){ return true; } return false; } /** * 這是合并操作 * @param x1 * @param x2 */ public void union(int x1 , int x2){ int index1 = findRoot(x1); int index2 = findRoot(x2); if (index1 == index2) return; elem[index1] = elem[index1] + elem[index2]; elem[index2] = index1; } /** * 有幾對關(guān)系 * @return */ public int getCount(){ int count = 0; for (int x:elem) { if (x < 0){ count++; } } return count; } public void Print(){ for (int x:elem){ System.out.print(x+" "); } System.out.println(); } }
測試結(jié)果:
1.2 Prime(普里姆) 算法
普里姆算法與克魯斯卡爾算法類似 , 核心區(qū)別是普里姆算法采用局部貪心的思想.
首先 , 設(shè)定兩個集合 , X{}已確定頂點(diǎn)的集合 , Y{}未確定頂點(diǎn)的集合.
其次 , 假設(shè)圖中的頂點(diǎn)為 a,b,c,d,e,f,g,h,i.放入Y{}中.
然后 , 任取一個頂點(diǎn)放入X{}中 . 在Y{}中選擇一個與該頂點(diǎn)相連權(quán)值最小的邊 , 加入最小生成樹中.
如此重復(fù) , 直到最小生成樹的邊數(shù)達(dá)到頂點(diǎn)數(shù)-1為止.
代碼示例:
/** * 普里姆算法實(shí)現(xiàn) * @param minTree * @param chV 圖中頂點(diǎn)的起點(diǎn) * @return */ public int prime(GraphOfMatrix minTree,char chV) { int srcIndex = getIndexOfV(chV); //存儲已確定的頂點(diǎn) Set<Integer> setX = new HashSet<>(); setX.add(srcIndex); //初始化未確定的點(diǎn) Set<Integer> setY = new HashSet<>(); int n = arrayV.length; for (int i = 0; i < n; i++) { if (i != srcIndex){ setY.add(i); } } //定義一個優(yōu)先級隊列 PriorityQueue<Edge> minQ = new PriorityQueue<>(new Comparator<Edge>() { @Override public int compare(Edge o1, Edge o2) { return o1.weight - o2.weight; } }); //遍歷srcIndex連接出去的邊,并放入優(yōu)先級隊列中排序 for (int i = 0; i < n; i++) { if (Matrix[srcIndex][i] != Integer.MIN_VALUE){ minQ.offer(new Edge(srcIndex,i,Matrix[srcIndex][i])); } } int size = 0; int totalWeight = 0; while (!minQ.isEmpty()){ Edge min = minQ.poll(); int srcI = min.srcIndex; int destI = min.destIndex; if (setX.contains(destI)){ //此時會構(gòu)成環(huán) }else { minTree.addEdgeUseIndex(srcI,destI,Matrix[srcI][destI]); System.out.println("起點(diǎn)"+arrayV[srcI]+" -> "+"終點(diǎn)"+arrayV[destI]+Matrix[srcI][destI]); size++; totalWeight+=min.weight; if (size == n-1){ return totalWeight; } //更新兩個集合 setX.add(destI); setY.remove(destI); //把dest連出去的所有邊也放到優(yōu)先級隊列中 for (int i = 0; i < n; i++) { if (Matrix[destI][i] != Integer.MIN_VALUE && !setX.contains(i)){ minQ.offer(new Edge(destI,i,Matrix[destI][i])); } } } } throw new RuntimeException("沒有最小生成樹"); } //測試普里姆算法 public static void main3(String[] args) { String str = "abcdefghi"; char[] array =str.toCharArray(); GraphOfMatrix g = new GraphOfMatrix(str.length(),false); g.initArray(array); g.addEdge('a', 'b', 4); g.addEdge('a', 'h', 8); //g.addEdge('a', 'h', 9); g.addEdge('b', 'c', 8); g.addEdge('b', 'h', 11); g.addEdge('c', 'i', 2); g.addEdge('c', 'f', 4); g.addEdge('c', 'd', 7); g.addEdge('d', 'f', 14); g.addEdge('d', 'e', 9); g.addEdge('e', 'f', 10); g.addEdge('f', 'g', 2); g.addEdge('g', 'h', 1); g.addEdge('g', 'i', 6); g.addEdge('h', 'i', 7); GraphOfMatrix primTree = new GraphOfMatrix(str.length(),false); System.out.println(g.prime(primTree,'a')); primTree.printGraph(); }
總結(jié)
到此這篇關(guān)于Java圖論進(jìn)階之最小生成樹算法的文章就介紹到這了,更多相關(guān)Java最小生成樹算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
smslib發(fā)短信實(shí)例代碼(電腦發(fā)短信)
smslib發(fā)短信實(shí)例,大家可以參考使用開發(fā)自己的程序2013-12-12SpringBoot詳細(xì)講解視圖整合引擎thymeleaf
這篇文章主要分享了Spring Boot整合使用Thymeleaf,Thymeleaf是新一代的Java模板引擎,類似于Velocity、FreeMarker等傳統(tǒng)引擎,關(guān)于其更多相關(guān)內(nèi)容,需要的小伙伴可以參考一下2022-06-06java int類型二維數(shù)組實(shí)現(xiàn)“楊輝三角”的完整實(shí)例
這篇文章主要給大家介紹了關(guān)于java int類型二維數(shù)組實(shí)現(xiàn)“楊輝三角”的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12Spring?Data?JPA查詢方式及方法名查詢規(guī)則介紹
這篇文章主要介紹了Spring?Data?JPA查詢方式及方法名查詢規(guī)則,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-11-11IntelliJ IDEA基于Maven構(gòu)建Java項目
在 Java 開發(fā)中,使用 Maven 是一種廣泛采用的構(gòu)建工具,本文主要介紹了IntelliJ IDEA基于Maven構(gòu)建Java項目,具有一定的參考價值,感興趣的可以了解一下2024-03-03