首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

用Java实现Prim的MST

Prim's算法是一种用于解决最小生成树(Minimum Spanning Tree,MST)问题的贪心算法。它通过逐步选择边来构建最小生成树,从一个初始顶点开始,每次选择与当前生成树相连的最小权重边所连接的顶点,并将该边加入生成树中,直到生成树包含了所有顶点。

Java是一种广泛使用的编程语言,具有丰富的库和框架支持,适合用于实现Prim的MST算法。以下是用Java实现Prim的MST算法的示例代码:

代码语言:txt
复制
import java.util.*;

public class PrimMST {
    private static final int V = 5; // 图的顶点数

    // 找到与当前生成树相连的最小权重边所连接的顶点
    private int minKey(int[] key, boolean[] mstSet) {
        int min = Integer.MAX_VALUE;
        int minIndex = -1;

        for (int v = 0; v < V; v++) {
            if (!mstSet[v] && key[v] < min) {
                min = key[v];
                minIndex = v;
            }
        }

        return minIndex;
    }

    // 打印最小生成树
    private void printMST(int[] parent, int[][] graph) {
        System.out.println("边\t权重");
        for (int i = 1; i < V; i++) {
            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
        }
    }

    // 使用Prim的算法构建最小生成树
    public void primMST(int[][] graph) {
        int[] parent = new int[V]; // 存储最小生成树的父节点
        int[] key = new int[V]; // 存储顶点的权重
        boolean[] mstSet = new boolean[V]; // 记录顶点是否已经加入最小生成树

        // 初始化key数组为无穷大,mstSet数组为false
        for (int i = 0; i < V; i++) {
            key[i] = Integer.MAX_VALUE;
            mstSet[i] = false;
        }

        key[0] = 0; // 将第一个顶点作为起始顶点
        parent[0] = -1; // 第一个顶点没有父节点

        for (int count = 0; count < V - 1; count++) {
            int u = minKey(key, mstSet); // 找到与当前生成树相连的最小权重边所连接的顶点
            mstSet[u] = true; // 将该顶点加入最小生成树

            // 更新与u相邻的顶点的权重
            for (int v = 0; v < V; v++) {
                if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = graph[u][v];
                }
            }
        }

        printMST(parent, graph); // 打印最小生成树
    }

    public static void main(String[] args) {
        PrimMST mst = new PrimMST();
        int[][] graph = new int[][] {
            { 0, 2, 0, 6, 0 },
            { 2, 0, 3, 8, 5 },
            { 0, 3, 0, 0, 7 },
            { 6, 8, 0, 0, 9 },
            { 0, 5, 7, 9, 0 }
        };
        mst.primMST(graph);
    }
}

这段代码实现了Prim的MST算法,通过传入一个邻接矩阵表示的图,计算并打印出最小生成树的边及其权重。

在腾讯云的产品中,与云计算和Java开发相关的产品有云服务器(CVM)、云数据库MySQL版、云存储(COS)等。您可以通过访问腾讯云官网了解更多关于这些产品的详细信息和使用方式。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

6分50秒

168-尚硅谷-图解Java数据结构和算法-普利姆算法(Prim)和MST介绍

6分50秒

168-尚硅谷-图解Java数据结构和算法-普利姆算法(Prim)和MST介绍

25分6秒

171-尚硅谷-图解Java数据结构和算法-Prim算法解决修路问题代码实现

25分6秒

171-尚硅谷-图解Java数据结构和算法-Prim算法解决修路问题代码实现

13分19秒

Java零基础-274-序列化的实现

13分19秒

Java零基础-274-序列化的实现

3分0秒

Java零基础-275-反序列化的实现

3分0秒

Java零基础-275-反序列化的实现

13分46秒

Java教程 26 Spring核心-SpringAOP的XML实现 学习猿地

10分36秒

Java零基础-126-if根据成绩判断等级的代码实现

6分6秒

Java零基础-288-实现线程的第二种方式

15分1秒

Java零基础-328-实现线程的第三种方式

领券