Shulou(Shulou.com)06/02 Report--

This article introduces the relevant knowledge of "the example introduction of Prim algorithm and Kruskal algorithm in java". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Minimum spanning tree

Now that we have mastered the concept and basic operation of diagrams, let's take a look at the problems that diagrams can solve. Diagrams are mainly used to solve many-to-many problems, such as problems with multiple starting points and endpoints, or multiple choices. For example, we need to find the shortest path from the following figure to connect each vertex, or to find the shortest path from vertex v0 to vertex v3:

Now what we want to study is to find the shortest path that can connect each vertex. We call the minimum cost spanning tree to construct a connected network as the minimum spanning tree. There are two classical algorithms for this problem, namely, Prim algorithm and Kruskal algorithm.

Prim algorithm

The idea of Prim algorithm is to select the least expensive vertex among the vertices that have never been selected every time, and update the minimum generation value of the remaining vertices. We take the above figure as an example to demonstrate the process of Prim algorithm.

First, select a vertex, such as v0. The vertex connected to v0 records its minimum generation value as the actual value, and the remaining vertices as ∞, as shown below:

Next, select the vertex v1 closest to v0 to join the selected list, and update the distance value from the remaining nodes to the selected list, as follows:

Next, select the vertex closest to the selected list again, obviously v5, and the result is as follows:

In the same way, we select v8 to add to the selected list, as follows:

Repeat this, and finally we get the following path, which is the minimum spanning tree we want to construct:

Kruskal (Kruskal) algorithm

Prim algorithm starts from vertices, we can also start from edges. Kruskal algorithm is to select the smallest edge to join the selected list every time, until all the vertices are connected. Let's take the above figure as an example to demonstrate its process.

Because you have to operate on the edges, you should first sort all the edges according to the cost. Do you remember how the edge set array of the graph is stored? We sort the edges and put them in an array of edge sets, as follows:

First of all, we think of each vertex as a separate tree, and these vertices form a forest, and our goal is to combine the forest into a tree, as follows:

In the first step, we take the shortest edge from the edge set array and connect the corresponding vertices in the forest. The first edge is (v4, v7) with a weight of 7, as shown below:

Vertices v4 and v7 now belong to the same tree, and then we find the shortest edge, its two can not be in the same tree, the second edge is (v2, v8), as follows:

Following the same steps, we continue to connect the remaining edges until we are finished (v3, v7) as follows:

The next shortest edge is (V5, V6), but vertices V5 and V6 are in the same tree, and if you join them together, it will form a ring, which is obviously wrong, so this edge is invalid. The next (v1, v2) is the same, so we should connect (v6, v7), as follows:

At this point, all the vertices are connected, and you can see that the results are consistent with the Prim algorithm.

Code implementation of Prim algorithm

Still take the adjacency matrix as an example to demonstrate the implementation process of the Prim algorithm, the code is as follows:

Public void prim (AMGraph graph) {int len = graph.getVertexNum (); int min = 0; / / coordinates of related vertices int [] adjvex = new int [len]; / / minimum cost int [] lowcost = new int [len]; / / add vertices at position 0 to spanning tree and set lowcost to 0 lowcost [0] = 0; adjvex [0] = 0; for (int I = 1; I)

< len; i++) { // 和v0相连的顶点的权值存入数组 lowcost[i] = graph.getWeight(0, i); // 全部坐标都初始化为v0下标 adjvex[i] = 0; } for (int i = 1; i < len; i++) { // INFINITE是一个不可能的值，这里设置为Int的最大值 min = INFINITE; int j = 1, k = 0; while (j < len) { // 循环剩下的全部顶点，寻找lowcoast if (lowcost[j] != 0 && lowcost[j] < min) { min = lowcost[j]; k = j; } j++; } System.out.println("当前顶点中最小权值的边是：(" + adjvex[k] + ", " + k + ")" + "最小值为：" + min); // 把此顶点的权值设为0 lowcost[k] = 0; for (j = 1; j < len; j++) { // 把当前的k顶点加入已选列表，并更新剩余顶点的权值 if (lowcost[j] != 0 && graph.getWeight(k, j) < lowcost[j]) { lowcost[j] = graph.getWeight(k, j); adjvex[j] = k; } } }} 可以看到，因为双重for循环的原因，普里姆算法的时间复杂度为O(n2)。 克鲁斯卡尔算法public void kruskal(Edge[] edges) { int len = edges.length; // 定义一个数组，保存每个顶点的父结点，也就是它所在的树结构中的父结点 int[] parent = new int[len]; for (int i = 0; i < len; i++) { parent[i] = 0; } int begin,end; for (int i = 0; i < len; i++) { // begin顶点所在树的根结点 begin = find(parent,edges[i].getBegin()); // end顶点所在树的根结点 end = find(parent,edges[i].getEnd()); // 不在同一棵树上 if (end != begin){ parent[end] = begin; System.out.println("加入边：(" + edges[i].getBegin()+", "+edges[i].getEnd() +") , weight = "+edges[i].getWeight()); } }}private int find(int[] parent, int find){ // 找到这棵树的根结点 while (parent[find]>

0) {find = parent [find];} return find;}

The code for converting the adjacency matrix to an array of edge sets and sorting the array of edge sets is omitted. It can be seen that the time complexity of Kruskal algorithm is related to the number of edges. If the number of edges is e, the time complexity of Kruskal algorithm is O (eloge).

Summary

Both Prim algorithm and Kruskal algorithm have their own scope of application. Although the time complexity of Kruskal algorithm is low, its actual value is closely related to the number of edges. When the number of edges is small, its efficiency is very high. In dense graphs with a large number of edges, it is better to use Prim algorithm.

This is the end of the introduction of the examples of Prim algorithm and Kruskal algorithm in java. Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.