资深网站,大连网络公司团队,泰安企业网站建设公司,怎么夸一个网站做的好看贪婪算法#xff1a;通过一系列步骤来构造问题的解#xff0c;每一步对目前构造的部分分解做一个拓展#xff0c;直到获得问题的完整解为止,而算法的核心思想就在于#xff0c;算法的每一步都必须满足以下条件#xff1a;可行#xff08;满足问题的约束条件#xff09;、…贪婪算法通过一系列步骤来构造问题的解每一步对目前构造的部分分解做一个拓展直到获得问题的完整解为止,而算法的核心思想就在于算法的每一步都必须满足以下条件可行满足问题的约束条件、局部最优当前步骤所有可行选择中的局部最优解、不可取消一旦选择在后续步骤中不可改变。
对于连通图来说生成树定义为包含图中所有顶点的连通无环子图
而在加权连通图中权重最小的生成树被称为最小生成树
Prim算法被又称为“加点法”,我们从图中的顶点集合中任意选择一个顶点作为序列的初始子树每次迭代的时候以贪婪的方式扩张生成树该算法每次只扩展一个点迭代的总次数为n-1。所以这就要求对于每个不在树中的顶点必须知道它连接树中顶点的最短边信息。我们可以给一个顶点附加两个标记树中最近顶点的名称以及对应边的长度。对于任意加入生成树中的顶点来说我们要做两步操作一将该顶点从集合V-Vt 移动带顶点集合Vt中操作二对V-Vt中的每个顶点更新。
我们以下面这个图为例子讲解Prim算法的过程Input:
6 101 2 31 5 61 6 52 6 52 3 13 6 43 4 64 6 54 5 8
5 6 2
Output:
15
完整代码如下
import java.util.Scanner;public class Main {static int[][] e new int[7][7];static int[] book new int[7];static int[] dis new int[7];static int count 0;static int sum 0;static int n, m;static int min, mark;static Scanner input new Scanner(System.in);public static void main(String[] args) {n input.nextInt();m input.nextInt();for (int i 1; i n; i) {for (int j 1; j n; j) {if (i j) {e[i][j] 0;} else {e[i][j] 99999999;}}}for (int i 1; i m; i) {int a input.nextInt();int b input.nextInt();int c input.nextInt();e[a][b] c;e[b][a] c;}for (int i 1; i n; i) {dis[i] e[1][i];}book[1] 1;prime();System.out.println(sum);}private static void prim() {count;while (count n) {min 99999999;for (int i 1; i n; i) {if (book[i] 0 dis[i] min) {min dis[i];mark i;}}book[mark] 1;count;sum dis[mark];for (int i 1; i n; i) {if (book[i] 0 dis[i] e[mark][i]) {dis[i] e[mark][i];}}}}
}时间复杂度O(n^2)如果采用堆来构造一个优先队列则会使算法的时间复杂度变为O(nlogn)
很感兴趣的读者可以参考图论算法四--最小生成树的Kruskal [ 加边 ] 、Prim [ 加点 ] 的解法JAVA这篇文章
