The principle and implementation of Prime algorithm in Java (summary sharing)

This article brings you relevant knowledge about java. The Prime algorithm is an exhaustive search algorithm to construct a minimum spanning tree from a connected graph. This article mainly introduces the principle and implementation of the Prime algorithm in Java. If you are interested, you can learn about it.

## Recommended study: "

java video tutorial"

Introduction to Prim algorithm

1. The finishing touch

In the process of generating a tree, the nodes already in the spanning tree are regarded as a set, the remaining nodes are regarded as another set, and the edge with the smallest weight is selected from the edges connecting the two sets. Can.

2. Algorithm introduction

First select a node, such as node 1, and put it in the set U, U={1}, then The remaining nodes are V-U={2,3,4,5,6,7}, and the set V is the set of all nodes of the graph.

Now we only need to see which edge has the smallest weight among the edges connecting the two sets (U and V-U), and associate the node with the smallest edge Join the set U. As can be seen from the above figure, among the 3 edges connecting the two sets, edge 1-2 has the smallest weight. Select it and add node 2 to the set U, U={1,2}, V - U={ 3,4,5,6}, as shown in the figure below.

Then select the edge with the smallest weight from the edges connecting the two sets (U and V-U). As can be seen from the above figure, among the four edges connecting the two sets, the edge weight from node 2 to node 7 is the smallest. Select this edge and add node 7 to the set U={1,2,7}, V-U ={3,4,5,6}.

This continues until U=V ends, and the graph composed of the selected edge and all nodes is the minimum spanning tree. This is Prim's algorithm.

Looking at the graph intuitively, it is easy to find out which edge from the set U to the set U-V has the smallest weight. However, it is time-consuming to exhaustively enumerate these edges in the program and then find the minimum value. The degree is too high. This problem can be solved cleverly by setting an array. Closet[j] represents the nearest neighbor point from node j in set V-U to set U. Lowcost[j] represents the edge value from node j in set V-U to the nearest neighbor point in set U. That is, the weight of edge (j, closest[j]).

For example, in the above figure, the nearest neighbor point from node 7 to set U is 2, cloeest[7]=2. The edge value from node 7 to the nearest neighbor point 2 is 1, which is the weight of edge (2,7), recorded as lowcost[7]=1, as shown in the figure below.

So just find lowcost[] the smallest node in the set V - U.

3. Algorithm steps

1. Initialization

Let the set U={u0}, u0 belong to V, and initialize the arrays closest[], lowcost[] and s[ ].

2. Find the node t with the smallest lowcost value in the set V-U, that is, lowcost[t]=min{lowcost[j]}, j belongs to V-U. The node t that satisfies this formula is the connection U in the set V-U the nearest point.

3. Add node t to the set U.

4. If the set V - U is empty, the algorithm ends, otherwise go to step 5.

5. Update lowcost[] and closest[] for all nodes j in the set V-U. if(C[t][j]Follow the above steps, and finally you can get a spanning tree with the smallest sum of weights.

4. Diagram

The graph G=(V,E) is an undirected connected weighted graph, as shown in the figure below.

1 Initialization. Assume u0=1, let the set U={1}, the set V-U={2,3,4,5,6,7}, s[1]=true, initialize the array closest[]: except node 1, all other nodes are is 1, which means that the nearest neighboring points from the nodes in the set V-U to the set U are all 1.lowcost[]: the edge value from node 1 to the node in the set V-U. closest[] and lowcost[] are shown in the figure below.

The picture after initialization is:

2 Find the node with the smallest lowcost, corresponding to t=2. The selected edges and nodes are as shown below.

3 Add to set U. Add node t to the set U, U={1,2}, and update V-U={3,4,5,6,7}

4 at the same time. For each adjacent point j of t in the set V-U, it can be updated with the help of t. The adjacent points of node 2 are node 3 and node 7.

C[2][3]=20

C[2][7]=1

Updated closest[] and lowcost[] as shown below.

The updated set is as shown below:

5 Find the node with the smallest lowcost, and the corresponding t= 7. The selected edges and nodes are as shown below.

6 Add to set U. Add node t to the set U, U={1,2,7}, and update V-U={3,4,5,6}

7 at the same time. For each adjacent point j of t in the set V-U, it can be updated with the help of t. The adjacent points of node 7 are nodes 3, 4, 5, and 6.

• C[7][3]=4
• C[7][4]=4
• C[7 ][5]=4
• C[7][6]=4< ;lowcost[6]=28, update nearest neighbor distance lowcost[3]=25, nearest neighbor closest[6]=7;

The updated closest[] and lowcost[] are as shown below shown.

The updated set is shown in the figure below:

##8 Find the node with the smallest lowcost, and the corresponding t= 3. The selected edges and nodes are as shown below.

9 Add to set U. Add node t to the set U, U={1,2,3,7}, and update V-U={4,5,6}

10 at the same time. For each adjacent point j of t in the set V-U, it can be updated with the help of t. The neighbor of node 3 is node 4.

C[3][4]=15>lowcost[4]=9, no update

closest[] and lowcost[] arrays do not change.

The updated set is as shown below:

#11 Find the node with the smallest lowcost, corresponding to t=4, and the selected edges and nodes are as shown below .

12 Add to set U. Add node t to the set U, U={1,2,3,4,7}, and update V-U={5,6}

13 at the same time. For each adjacent point j of t in the set V-U, it can be updated with the help of t. The neighbor of node 4 is node 5.

C[4][5]=3

The updated closest[] and lowcost[] are shown in the figure below.

The updated set is as shown below:

##14 Find the node with the smallest lowcost, and the corresponding t= 5. The selected edges and nodes are as shown below.

15 Add to set U. Add node t to the set U, U={1,2,3,4,5,7}, and update V-U={6}

16 at the same time. For each adjacent point j of t in the set V-U, it can be updated with the help of t. The neighbor of node 5 is node 6.

C[5][6]=17

Updated The set is as shown below:

17 Find the node with the smallest lowcost, corresponding to t=6, and the selected edges and nodes are as shown below.

18 Add to set U. Add node t to the set U, U={1,2,3,4,5,6,7}, and update V-U={}

19 at the same time. For each adjacent point j of t in the set V-U, it can be updated with the help of t. Node 6 has no adjacent points in the set V-U. No need to update closest[] and lowcost[].

20 The obtained minimum spanning tree is as follows. The sum of the weights of the minimum spanning tree is 57.

Prime algorithm implementation

1. The constructed graph

2. Code

package graph.prim;
 
import java.util.Scanner;
 
public class Prim {
    static final int INF = 0x3f3f3f3f;
    static final int N = 100;
    // 如果s[i]=true,说明顶点i已加入U
    static boolean s[] = new boolean[N];
    static int c[][] = new int[N][N];
    static int closest[] = new int[N];
    static int lowcost[] = new int[N];
 
    static void Prim(int n) {
        // 初始时，集合中 U 只有一个元素，即顶点 1
        s[1] = true;
        for (int i = 1; i <= n; i++) {
            if (i != 1) {
                lowcost[i] = c[1][i];
                closest[i] = 1;
                s[i] = false;
            } else
                lowcost[i] = 0;
        }
        for (int i = 1; i < n; i++) {
            int temp = INF;
            int t = 1;
            // 在集合中 V-u 中寻找距离集合U最近的顶点t
            for (int j = 1; j <= n; j++) {
                if (!s[j] && lowcost[j] < temp) {
                    t = j;
                    temp = lowcost[j];
                }
            }
            if (t == 1)
                break; // 找不到 t，跳出循环
            s[t] = true; // 否则，t 加入集合U
            for (int j = 1; j <= n; j++) { // 更新 lowcost 和 closest
                if (!s[j] && c[t][j] < lowcost[j]) {
                    lowcost[j] = c[t][j];
                    closest[j] = t;
                }
            }
        }
    }
 
    public static void main(String[] args) {
        int n, m, u, v, w;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        int sumcost = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                c[i][j] = INF;
        for (int i = 1; i <= m; i++) {
            u = scanner.nextInt();
            v = scanner.nextInt();
            w = scanner.nextInt();
            c[u][v] = c[v][u] = w;
        }
        Prim(n);
        System.out.println("数组lowcost:");
 
        for (int i = 1; i <= n; i++)
            System.out.print(lowcost[i] + " ");
 
        System.out.println();
        for (int i = 1; i <= n; i++)
            sumcost += lowcost[i];
        System.out.println("最小的花费：" + sumcost);
    }
}

3. Test

Recommended study: " java video tutorial》

The above is the detailed content of The principle and implementation of Prime algorithm in Java (summary sharing). For more information, please follow other related articles on the PHP Chinese website!