最小生成树 : Prim 算法

发布时间:2014-10-22 12:20:40编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"最小生成树 : Prim 算法",主要涉及到最小生成树 : Prim 算法方面的内容,对于最小生成树 : Prim 算法感兴趣的同学可以参考一下。

public class Prim { static final int M = 10000; static int extractMin(int[] key, boolean[] visited) { int min = M; int idx = -1; for(int i = 0; i < key.length; i++) { if(!visited[i] && key[i] < min) { idx = i; min = key[i]; } } visited[idx] = true; return idx; } static int prim(int vertex, int[][] edges) { int[] key = new int[vertex]; boolean[] visited = new boolean [vertex]; int[] p = new int [vertex]; //init for(int i = 0; i < vertex; i++) { key[i] = M; p[i] = -1; } int r = 0; key[r] = 0; p[r] = -1; int cnt = vertex; while(cnt > 0) { cnt--; //EXTRACT-MIN int u = extractMin(key, visited); for(int v = 0; v < edges[u].length; v++) { //Adj[u] if(!visited[v] && edges[u][v] < key[v]) { p[v] = u; key[v] = edges[u][v]; } } } int cost = 0; for(int i = 0; i < p.length; i++) { if(i == r) continue; System.out.printf("%c - %c : %d\n", p[i] + 'A', i + 'A', key[i]); cost += key[i]; } return cost; } public static void main(String[] args) { int vertex = 7; int[][] edges = { {M, 7, M, 5, M, M, M}, {7, M, 8, 9, 7, M, M}, {M, 8, M, M, 5, M, M}, {5, 9, M, M, 15, 6, M}, {M, 7, 5, 15, M, 8, 9}, {M, M, M, 6, 8, M, 11}, {M, M, M, M, 9, 11, M} }; int mst = prim(vertex, edges); System.out.println("MST Prim cost:" + mst); } } 输出: A - B : 7 E - C : 5 A - D : 5 B - E : 7 D - F : 6 E - G : 9 MST Prim cost:39


上一篇:C++纯虚函数可以在类外实现
下一篇:(android功能代码) android文件上传服务器

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款