最小生成树之Prim算法

2024-07-11 08:59| 来源: 网络整理| 查看: 265

Prim算法介绍：假设N = (V, {E})是连通网，TE是N上最小生成树中边的集合。算法U={u0}(u0ЄV)，TE={}开始，重复执行下述操作：在所有uЄU，vЄV-U的边(u,v)ЄE中找一条代价最小的边(u0,v0)并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V，{TE}）为N的最小生成树。 Prim算法构造最小生成树的过程如下：在这里插入图片描述代码如下：

import java.util.Arrays; import java.util.Scanner; public class prim { public static void main(String args[ ]){ Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); int[][] cost = new int[n+1][n+1]; for(int i = 1; i

【本文地址】

最小生成树之Prim算法

最小生成树之Prim算法

今日新闻

推荐新闻