最小生成樹(shù) kruskal

In Electronic Circuit we often required less wiring to connect pins together. We can model this wiring problem with a connected, undirected graph G=(V, E), where V is the set of pins, E is the set of possible interconnections between pair of pins, and for each edge we have a weight w(u,v) specifying the cost (amount of wire needed) to connect u and v. We then wish to find an acyclic subset T that connects all of the vertices and whose total weight w(T)= sum of all the weights in T is minimized . Since T is acyclic and connects all of the vertices, it must form a tree, which we call a spanning tree since it spans the graph G. We call this problem minimum spanning tree problem.

在電子電路中，我們通常需要較少的接線來(lái)將引腳連接在一起。 我們可以使用連接的無(wú)向圖G =(V，E)來(lái)建模此布線問(wèn)題，其中V是引腳組， E是引腳對(duì)之間可能的互連集，對(duì)于每個(gè)邊，我們都有權(quán)重w( u，v)指定連接u和v的成本(所需的電線數(shù)量)。 然后，我們希望找到一個(gè)無(wú)環(huán)子集T ，它連接所有頂點(diǎn)，并且總權(quán)重w(T)= T中所有權(quán)重的總和最小 。 由于T是無(wú)環(huán)的并且連接所有頂點(diǎn)，因此它必須形成一棵樹(shù)，由于它跨越了圖G ，因此我們將其稱(chēng)為生成樹(shù) 。 我們稱(chēng)這個(gè)問(wèn)題為最小生成樹(shù)問(wèn)題 。

MST Green color edges are the selected edges for MST.

MST綠色邊緣是MST的選定邊緣。

There are two algorithm to solve this problem: Kruskal's Algorithm and Prim's Algorithm. Each of them run in O(E lg V )

有兩種算法可以解決此問(wèn)題： Kruskal算法和Prim算法 。 它們每個(gè)都以O(shè)(E lg V)運(yùn)行

Here we are discussing Kruskal's Algorithm...

在這里，我們討論的是Kruskal算法...

克魯斯卡爾算法 (Kruskal's Algorithm)

This Algorithm first makes the forest of each vertex and then sorts the edges according to their weights, and in each step, it adds the minimum weight edge in the tree that connects two distinct vertexes that do not belong to the same tree in the forest.

該算法首先創(chuàng)建每個(gè)頂點(diǎn)的森林，然后根據(jù)其權(quán)重對(duì)邊緣進(jìn)行排序，然后在每個(gè)步驟中，在連接兩個(gè)不屬于該森林中同一棵樹(shù)的不同頂點(diǎn)的樹(shù)中添加最小權(quán)重邊緣。

It uses a disjoint set data structure to maintain several disjoint sets of elements. Each set contains the vertices in one tree of the current forest.

它使用不連續(xù)集數(shù)據(jù)結(jié)構(gòu)來(lái)維護(hù)幾個(gè)不連續(xù)元素集。 每一組包含當(dāng)前森林的一棵樹(shù)中的頂點(diǎn)。

Example: Here we are finding the cost of MST.

示例：在這里我們發(fā)現(xiàn)MST的成本。

Program:

程序：

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*;public class MST{static class set{int parent,rank;}//find set which represents vertex istatic int find(set subsets[],int i ){if(subsets[i].parent==i)return i;return find(subsets,subsets[i].parent);}//function for adding edges whose vertex belongs //to the different tree ie. UNIONstatic void UNION(set subsets[],int x,int y){int xroot=find(subsets,x);int yroot=find(subsets,y);if(subsets[xroot].rank>subsets[yroot].rank)subsets[yroot].parent=xroot;else if(subsets[xroot].rank<subsets[yroot].rank)subsets[xroot].parent=yroot;else{subsets[yroot].parent=xroot;subsets[xroot].rank++;}}static int mst(int n, Integer[][] edges) {set subsets[]=new set[n];//Create forest of vrtices that is separate tree for each vertexfor(int i=0;i<n;i++) { subsets[i]=new set();subsets[i].parent=i; // Each vertex is its own parentsubsets[i].rank=0; //Having no child}int e=0,i=0,count=0;//Create graph having exactly vertex-1 ie. n-1 edgeswhile(e<n-1){//find set from which current vertex belongsint x=find(subsets,edges[i][0]-1); //find set from which current vertex belongsint y=find(subsets,edges[i][1]-1); if(x!=y){count+=edges[i][2]; e++;// union the two vertex in the same tree //if they belong to the different setUNION(subsets,x,y); }i++;}return count;}public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt(); //number of nodesint m = in.nextInt(); //number of edgesInteger [][]edges = new Integer[m][3];for(int edges_i = 0; edges_i < m; edges_i++){for(int edges_j = 0; edges_j < 3; edges_j++){edges[edges_i][edges_j] = in.nextInt();}}//Sort edges two dimensional array according to //its third column i.e. weightArrays.sort(edges,new Comparator<Integer[]>(){@Overridepublic int compare(Integer[] i1,Integer[] i2){//Comparing third column having index 2return i1[2].compareTo(i2[2]); }});int result=mst(n,edges);System.out.println(result);in.close();} }

Output

輸出量

翻譯自: https://www.includehelp.com/java/minimum-spanning-tree-problem-using-kruskals-algorithm.aspx

最小生成樹(shù) kruskal

總結(jié)

以上是生活随笔為你收集整理的最小生成树 kruskal_使用Kruskal算法求解Java最小生成树问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。