Prim's algorithm Java

2025年5月3日 | 阅读4分钟

Java 中的Prim算法是用于最小生成树最常用的算法之一。Prim 算法从一个不包含任何顶点的生成树开始。在 Prim 算法中，我们维护两个顶点集合，第一个包含已包含在 MSP 中的顶点，第二个包含未包含在 MSP 中的顶点。

在每一步，它会考虑连接这两个集合的所有边，并从这些边中选择权重最小的边。选择一条边后，它将该边的另一端（包含 MST 的那一端）添加到 MST 中。

Prim 算法

创建一个包含唯一元素的集合，用于跟踪已包含在 MST 中的顶点。
对于输入图的所有顶点，为其分配一个键值对，并将值初始化为无穷大。为了选择第一个顶点，我们将它的键值设置为 0。
选择一个不在 setOfMST 中的顶点 u，且其键值最小。
将顶点 u 添加到 setOfMST。
更改 u 的所有相邻顶点的键值。

注意：为了更新相邻顶点 v 的键值，如果边 u-v 的权重小于 v 的先前键值，则将键值更改为 u-v 的权重。

重复步骤 3、4 和 5，直到 setOfMST 包含所有顶点为止。

让我们在 Java 中实现 Prim 算法的代码。

MinimumSpanningTreeExample.java

//import required classes and packages
import java.lang.*; 
import java.util.*; 
import java.io.*; 

//creating MinimumSpanningTreeExample class to implement Prim's algorithm in Java   
class MinimumSpanningTreeExample { 
    // Define the count of vertices available in the graph
    private static final int countOfVertices = 9; 
  
    // create findMinKeyVertex() method for finding the vertex v that has minimum key-value and that is not added MST yet
    int findMinKeyVertex(int keys[], Boolean setOfMST[]) 
    { 
        // Initialize min value and its index
        int minimum_index = -1; 
        int minimum_value = Integer.MAX_VALUE;
		
        //iterate over all vertices to find minimum key-value vertex
        for (int vertex = 0; vertex < countOfVertices; vertex++) 
            if (setOfMST[vertex] == false && keys[vertex] < minimum_value) { 
                minimum_value = keys[vertex]; 
                minimum_index = vertex; 
            } 
  
        return minimum_index; 
    } 
  
    // create showMinimumSpanningTree for printing the constructed MST stored in mstArray[] 
    void showMinimumSpanningTree(int mstArray[], int graphArray[][]) 
    { 
        System.out.println("Edge \t\t Weight"); 
        for (int j = 1; j < countOfVertices; j++) 
            System.out.println(mstArray[j] + " <-> " + j + "\t \t" + graphArray[j][mstArray[j]]); 
    } 
  
    // create designMST() method for constructing and printing the MST. The graphArray[][] is an adjacency matrix that defines the graph for MST.
    void designMST(int graphArray[][]) 
    { 
        // create array of size total number of vertices, i.e., countOfVertices for storing the MST
        int mstArray[] = new int[countOfVertices]; 
  
        // create keys[] array for selecting an edge having minimum weight in cut 
        int keys[] = new int[countOfVertices]; 
  
        // create setOfMST array of type boolean for representing the set of vertices included in MST 
        Boolean setOfMST[] = new Boolean[countOfVertices]; 
  
        // set the value of the keys to infinite 
        for (int j = 0; j < countOfVertices; j++) { 
            keys[j] = Integer.MAX_VALUE; 
            setOfMST[j] = false; 
        } 
  
        // set value 0 to the 1st vertex because first vertes always include in MST. 
        keys[0] = 0; // it select as first vertex 
        mstArray[0] = -1; // set first value of mstArray to -1 to make it root of MST 
  
        // The vertices in the MST will be equal to the countOfVertices 
        for (int i = 0; i < countOfVertices - 1; i++) { 
            // select the vertex having minimum key and that is not added in the MST yet from the set of vertices 
            int edge = findMinKeyVertex(keys, setOfMST); 
  
            // Add the selected minimum key vertex to the setOfMST 
            setOfMST[edge] = true; 
  
            // change the key value and the parent index of all the adjacent vertices of the selected vertex. The vertices that are not yet included in Minimum Spanning Tree are only considered. 
            for (int vertex = 0; vertex < countOfVertices; vertex++) 
  
                // The value of the graphArray[edge][vertex] is non zero only for adjacent vertices of m setOfMST[vertex] is false for vertices not yet included in Minimum Spanning Tree 
                // when the value of the graphArray[edge][vertex] is smaller than key[vertex], we update the key
                if (graphArray[edge][vertex] != 0 && setOfMST[vertex] == false && graphArray[edge][vertex] < keys[vertex]) { 
                    mstArray[vertex] = edge; 
                    keys[vertex] = graphArray[edge][vertex]; 
                } 
        } 
  
        // print the constructed Minimum Spanning Tree 
        showMinimumSpanningTree(mstArray, graphArray); 
    } 
	//main() method start
    public static void main(String[] args) 
    { 
        
        MinimumSpanningTreeExample mst = new MinimumSpanningTreeExample(); 
        int graphArray[][] = new int[][]{{ 0, 4, 0, 0, 0, 0, 0, 8, 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, 0, 0, 9, 0, 10, 0,	0, 0 },
					{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
					{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
					{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
					{ 0, 0, 2, 0, 0, 0, 6, 7, 0 }}; 
  
        // Print the Minimum Spanning Tree solution 
        mst.designMST(graphArray); 
    } 
}

输出

下一个主题Balanced-tree-check-in-java

Prim's algorithm Java

Prim 算法

注意：为了更新相邻顶点 v 的键值，如果边 u-v 的权重小于 v 的先前键值，则将键值更改为 u-v 的权重。

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Prim's algorithm Java

Prim 算法

注意：为了更新相邻顶点 v 的键值，如果边 u-v 的权重小于 v 的先前键值，则将键值更改为 u-v 的权重。

相关帖子

Java 中的自描述数

LinkedHashMap vs HashMap

Java 中向方法传递对象

Java 中将数据从一个文件复制到另一个文件

Java 中 String、StringBuffer 和 StringBuilder 的区别

ArrayList vs HashMap

Abstract Method in Java

Java 中的 Atomic Boolean

How to Create Object in Java

Practical Number in Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器