Kruskal的算法解决了找到任何给定的连接和无向图的最小生成树(MST)的问题。

什么是最小的生成树？

它基本上是给定图的子图，它连接所有顶点，其具有最小数量的边缘，其具有最小可能的重量，无循环。
由于此图形不包含循环，这就是为什么它被称为树。
取决于给定的图形，可能存在多于一个可能的MST。

用于连接给定图中的所有顶点，我们需要具有至少顶点-1边缘。

为什么？

考虑只有两个节点的图形，我们可以使用一个边缘连接这两个节点。
此时我们有2个顶点和一个边缘。
现在，如果我们希望在图表中包含一个包含最小顶点的一个顶点，我们需要从当前图表到此新顶点的边缘。
也就是说，对于每个传入节点，我们需要添加边缘。

因此，顶点和边缘都将增加一个，顶点数量将始终是边缘+ 1，这意味着，数量 edges = vertices-1

算法

Kruskal是一种贪婪的方法，它强调了我们只能在我们的MST中包含的事实，这些方法仅包括所有边缘之间的最小重量，请记住，我们不包括在此循环中创建循环的边缘 MST被建造。

• 我们根据其权重保留以越来越多的顺序排序的所有边缘。
• 从列表中拍摄边缘，检查它是否在此处创建一个周期 MST被建造，
• 如果它没有创建任何周期，那么我们将构建MST中的边缘。
• 如果它创建一个循环，则我们跳过当前边缘，然后继续到排序列表中的下一个边缘。
• 我们需要再次重复相同的过程，直到我们有 (Vertices-1)在最终最小生成树中的边缘。

对于所有这些，我们使用Disjoint Set Union数据结构，其可帮助我们构建MST和检查如果我们包含当前边缘，则在MST中存在任何周期。

以下是我们如何使用Disjoint Set Union执行此操作：

• 最初，每个顶点都是一个 disjoint set本身并在两个顶点之间添加边缘，我们需要合并包含这两个顶点的集合。
• 每个集合都有自己的父级，它代表了整个脱节集和两组合并基本上意味着，使父母成为 two sets same。
• 具有较少数量的顶点的设置将与具有较高数量元素的集合合并，并且通过制造时简单地完成合并 parent of bigger set equal to the parent of smaller set。

现在用于检查周期，我们看看当前当前的电流边缘的顶点位于 same set or not。

• 如果他们 do not谎言 same set然后，可以在MST中包含此边缘，因为该电流边缘的两个顶点位于单独的组中，并且直接或者间接地存在从第一个顶点的路径，这就是它们所在的原因 two DISJOINT sets，直接从v1到v2添加边缘不会创建任何周期。
• 如果他们躺在那里 same set，这意味着它们直接或者间接地彼此连接，最小数量的边缘(具有最小权重)并再次添加一个边缘，再次连接它们在中 Minimum Spanning Tree被建造。

For checking if any two vertices lie in the same set or not, we just need to check the parents/representative of their sets. If they are same, then the two vertices lie in same set or else they lie in different sets.

在实现此算法的同时，以及维护排序边的列表，我们还需要维护两个数组，即， parent array和 size array，它保留了不相交的轨迹。 Parent array告诉父母/代表任何第一个顶点的集合。 Size array对于任何顶点，将在任何第i个顶点的脱节集中保持顶点的轨迹。

最初，任何顶点的父级都是顶点只有其设置等于1的大小，因为此顶点是其不相交集中的唯一元素。
那是， Parent[i] = isize[i] = 1

考虑此图表，找到此给定双向图的最小生成树，我们首先需要以非减少顺序对所有边缘进行排序。

分类的边缘列表：边缘(d，e)重量= 1边缘(f，e)，重量= 2边缘(a，f)，重量= 3边缘(f，b)，重量= 4边缘(b，e )重量= 5边缘(a，b)，重量= 6边缘(a，e)，重量= 7边缘(c，e)，重量= 8边缘(d，c)，重量= 8边缘(b，c )重量= 9 Parent = {0, 1, 2, 3, 4, 5}Size = {1, 1, 1, 1, 1, 1}顶点A在第三索引顶点C处在第1索引顶点C处的第0索引V在第4次索引顶点E处的第5次索引V.

在给定的图表中，每个颜色代表自己的脱节集，并且随着我们知道的，所有节点都是孤立的不相交，因此所有顶点都是唯一的彩色。

边缘1：

我们目前处于边缘(d，e)，重量= 1是所有的最小。
首先检查包含此边缘是否创建任何周期。
D&E处于不同的集合，如果我们包含此边缘，则不会形成循环，因此我们可以包含此边缘。

Parent = {0, 1, 2, 4, 4, 5}
Size = {1, 1, 1, 1, 2, 1}
parent [D] = E
Size [E] = Size [E] + Size [D]

边缘2：

我们目前处于边缘(f，e)，重量= 2首先检查是否包含此边缘或者未创建任何周期。
F&E处于不同的集合，因此如果我们包括此边缘，则不会形成循环，因此我们可以包括该边缘并对具有F和E的两个不相交的组执行联合操作。

Parent = {0, 1, 2, 4, 4, 4}
Size = {1, 1, 1, 1, 3, 1}
parent [F] = E
Size [E] = Size [E] + Size [F]

Edge-3：

我们目前处于Edge(A，F)，重量= 3首先检查是否包含此边缘的任何循环。
因此，F&A在不同的集合中，如果我们包括此边缘，则不会形成循环，因此我们可以包括该边缘并对具有A和F的两个不相交的集合执行联合操作，以便组合A和F的差异集，我们需要让父母的一个等于f，但在这里我们看到，f不是自己的集合的父级，这意味着一个父母的父母不会是f，而是父母是f的父母。

Parent = {4, 1, 2, 4, 4, 4}
Size = {1, 1, 1, 1, 4, 1}
parent [A] = parent [F] = E
Size [E] = Size [E] + Size [A]

Edge-4：

我们目前处于Edge(F，B)，重量= 4首次检查是否包含此边缘或者不创建任何周期。
因此，F&B在不同的集合中，如果我们包括该边缘，则不会形成循环，因此我们可以包括该边缘并在具有A和F的两个不相交集合上执行联合操作。
现在，用于组合B和F的差异集合，我们将成为B的父母作为B的父母而不是F直接。

Parent = {4, 4, 2, 4, 4, 4}
Size = {1, 1, 1, 1, 5, 1}
parent [B] = parent [F] = E
Size [E] = Size [E] + Size [B]

边缘5：

我们目前正在 edge (B, E)重量= 5.但是包含此边缘创建一个周期，因为B和E处于相同的设置，因为父[b] =父级[e] = e，并且在b和e之间添加直接边缘将形成一个循环MST被建造。
因此，我们跳过这个边缘。

为了 edge (A, B)，此边缘还将创建一个循环，因为相同的原因，a和b处于相同的不相交集合，其集合的父节点等于e并在a和b之间添加直接边缘将形成一个循环MST被建造。
因此，我们也跳过这个边缘。

为了 edge (A, E)，此边缘还将创建一个循环，具有相同的原因，a和e处于同一脱编集，其集合的父级等于e并在a和e之间添加直接边缘将形成一个周期MST被建造。
因此，我们也跳过这个边缘。

现在，为 edge (C, E)重量= 8，首先检查包含此边缘是否会产生任何周期。
C&E处于不同的集合，如果我们包括该边缘，则不会形成循环，因此我们可以包括该边缘并且在具有C和E的两个不相交集合上执行联合操作。
现在，用于组合C和E的差异集，我们将成为B的父母。

Parent = {4, 4, 4, 4, 4, 4}
Size = {1, 1, 1, 1, 6, 1}
parent [C] = E
Size [E] = Size [E] + Size [C]

现在，我们在最小的生成树中包含了总共5个边缘，这是相当于连接所有顶点的所有顶点和父顶部所需的最小边的边数将是现在的常见顶点。
因此，我们在此终止我们的算法。

最后，这是应用Kruskal算法后获得的最小生成树。

时间复杂性：边缘的排序= e log e现在，对于(v 1)次，我们执行了，联合操作并检查了周期，这似乎是如此 O(1)操作，但这包括在时间复杂度的任何边缘找到顶点的父母 O(Log V)。
当我们知道任何图中的潜在边缘都可以高达^ 2.
因此，Kruskal算法的总体时间复杂性是 O(E log E)

package Graphs;
 
import java.util.Arrays;
import java.util.Scanner;
 
public class kruskals {
 
	public static class edge implements Comparable<edge> {
		int u;
		int v;
		int weight;
 
		public edge(int u, int v, int weight) {
			this.u = u;
			this.v = v;
			this.weight = weight;
		}
 
		public String toString() {
			return this.u + " " + this.v + " " + this.weight;
		}
 
		//sorting of the edges will be done on the basis of weights.
		@Override
		public int compareTo(edge o) {
			return this.weight - o.weight;
		}
	}
 
	public static void main(String[] args) {
 
		Scanner scn = new Scanner(System.in);
		int nodes = scn.nextInt();
		int[][] graph = new int[nodes + 1][nodes + 1];
		int numEdges = scn.nextInt();
		edge[] edges = new edge[numEdges];
		for (int edge = 0; edge < numEdges; edge++) {
			int u = scn.nextInt(), v = scn.nextInt(), w = scn.nextInt();
			/*
			 * as the graph will be bidirectional then 'v' will be
			 *  neighbour of 'u' and vice-versa
			 */
			graph[u][v] = graph[v][u] = w;
 
			/* add the edge in the edges array which will be 
                         * sorted later */
			edges[edge] = new edge(u, v, w);
		}
 
		kruskalsAlgo(nodes, numEdges, edges, graph);
 
	}
 
	public static void kruskalsAlgo(int numVertices, int numEdges, edge[] edges, int[][] graph) {
 
		/* for storing minimum spanning tree formed */
		int[][] mst = new int[graph.length][graph.length];
		/* sort the edges on the basis of their weights 
		 * in an increasing order */
		Arrays.sort(edges);
 
		/* we use parents & size array for creating disjoint sets */
		int[] parents = new int[numVertices + 1];
		int[] size = new int[numVertices + 1];
		for (int vertex = 1; vertex < graph.length; vertex++) {
			/*
			 * initially all the vertices are a set in 
			 * themselves, hence, they are the parent of their
			 * own set, and the size of their set is also one
			 */
			parents[vertex] = vertex;
			size[vertex] = 1;
		}
 
		int edgeCounter = 0;
		int edgedTaken = 1;
		/* for connecting all the vertices we need to have 
		 * atleast vertices-1 edges */
		while (edgedTaken <= numVertices - 1) {
			edge e = edges[edgeCounter];
			edgeCounter++;
			/*
			 * we will include only those edges which does 
			 * not create any cycle in the constructed minimum 
			 * spanning tree
			 */
			if (isCyclic(e.u, e.v, parents))
				continue;
			/*
			 * for combining the edge into the MST, we first
			 * need to find the parents of both the vertices, 
			 * and then the put combine the smaller set with 
			 * larger set
			 */
			union(findParent(e.u, parents), findParent(e.v, parents), parents, size);
			mst[e.u][e.v] = e.weight;
			edgedTaken++;
		}
 
		/* tree display */
		for (int u = 1; u < mst.length; u++) {
			for (int v = 0; v < mst.length; v++) {
				if (mst[u][v] != 0) {
					System.out.println(u + " " + v + " " + mst[u][v]);
				}
			}
		}
 
	}
 
	public static boolean isCyclic(int u, int v, int[] parents) {
		/*
		 * if the parents of both the vertices of the 
		 * edge are same, this means they are connected 
		 * to a common vertex, and hence if we put this
		 *  edge in the MST then it will create a cycle.
		 */
		return findParent(u, parents) == findParent(v, parents);
	}
 
	public static void union(int u, int v, int[] parents, int[] size) {
		/*find the parent of both the vertices in the current
		 * edge, and merge the larger disjoint set with smaller
		 * disjoint set*/
		 u = findParent(u, parents);
		 v = findParent(v, parents);
		if (size[u] > size[v]) {
			parents[v] = u;
			size[u] += size[v];
		} else {
			parents[u] = v;
			size[v] += size[u];
		}
	}
 
	public static int findParent(int u, int[] parents) {
		/*if the parent of any vertex is the vertex itself,
		 * then this is the parent of the the vertex of the
		 *  current edge being processed*/
		if (parents[u] == u) {
			return u;
		} else {
			/*path compression*/
			parents[u] = findParent(parents[u], parents);
			return parents[u];
		}
	}
 
}