“This is the 10th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Minimum spanning tree Prim algorithm Java version

Algorithm description:

  1. In a weighted connected graph, the set of vertices V and the set of edges E
  2. Select any point as the initial vertex, mark visit, calculate the distance of all points connected to it, select the shortest distance, mark VISIT.
  3. Repeat the following until all points are marked visit:

At the remaining hours, calculate the point least distant from the point marked visit and mark visit to prove that the minimum spanning tree has been added.

Compare kruskal’s algorithm

Assuming that there are n nodes and E edges in the network, the time complexity of Prim algorithm is O(n^2), and that of Kruskal algorithm is O(eloge). It can be seen that the former has nothing to do with the number of edges in the network, while the latter has the opposite. Therefore, Prim algorithm is suitable for networks with dense edges while Kruskal algorithm is suitable for networks with sparse edges.

The time complexity of Kruskal algorithm is mainly determined by the sorting method, and the sorting method of Kruskal algorithm is only related to the number of edges in the network, and has nothing to do with the number of vertices in the network. When the sorting method of TIME complexity O (Elog2e) is used, the time complexity of Kruskal algorithm is O (log2e). Therefore, when the number of vertices is large but the number of edges is small, kruskal algorithm is better to construct a minimum spanning tree

Code

package com.company; import java.util.*; public class MinTree { public static void main(String[] args) { int[][] arr = new int[][]{ // 0 1 2 3 4 5 6 7 8 {-0, 4, 0, 0, 0, 0, 0, 7, 0}, {4, 0, 8, 0, 0, 0, 0, 11, 0}, {0, 8, 0, 7, 0, 4, 0, 0, 2}, {0, 0, 7-0, 9, 14, 0, 0, 0}, {0, 9, 0, 0, 0, 10, 0, 0, 0}, {0, 0, 4, 14, 10, 0, 2, 0, 0}, {0, 0, 0, 0, 0, 2, 0, 1, 6}, {7, 11, 0, 0, 0, 0, 1, 0, 7}, {0, 0, 2, 0, 0, 0, 6, 7,-0}}; boolean[] visited=new boolean[arr.length]; visited[0]=true; PriorityQueue<Integer[]> queue=new PriorityQueue<>(new Comparator<Integer[]>() { @Override public int compare(Integer[] o1, Integer[] o2) { return o1[0]-o2[0]; }}); int count=1; for (int i = 0; i < arr.length; i++) { if(arr[0][i]! = 0 &&! visited[i]){ queue.add(new Integer[]{arr[0][i],0,i}); } } while (count<arr.length){ Integer[] temp=null; while (! queue.isEmpty()){ temp=queue.poll(); if(visited[temp[2]])continue; break; } visited[temp[2]]=true; System. The out. Println (" starting point: "+ temp [1] +" ending: "+ temp [2] +" length is: "+ temp [0]). for (int i = 0; i < arr.length; i++) { if(arr[temp[2]][i]! = 0 &&! visited[i]){ queue.add(new Integer[]{arr[temp[2]][i],temp[2],i}); } } count++; }}}Copy the code

The output

Starting point: 0 Finishing point: 1 Length: 4 Starting point: 0 finishing point: 7 Length: 7 Starting point: 7 Finishing point: 6 Length: 1 Starting point: 6 Finishing point: 5 Length: 2 Starting point: 5 Finishing point: 2 Length: 4 Starting point: 2 Finishing point: 8 Length: 2 Starting point: 2 Finishing point: 3 Length: 7 Starting point: 3 Finishing point: 3 4 The value contains 9 Process finished with exit code 0Copy the code