1616public class LazyPrimMST <Weight extends Number & Comparable <Weight >> {
1717 private boolean visited []; //标记已被访问过的顶点
1818 private MinHeap <Edge <Weight >> minHeap ; //存储权值的堆结构
19- private Weight mWeight ; //最小生成树的总权值
19+ private Number mWeight ; //最小生成树的总权值
2020 private List <Edge <Weight >> mst ; //存放最小生成树的所有顶点
2121
2222
@@ -43,8 +43,14 @@ public LazyPrimMST(WeightGraph graph){
4343 }else if (!visited [e .w ()]){
4444 visit (graph ,e .w ());
4545 }
46+ }
4647
48+ //计算最小生成树的权值
49+ mWeight = mst .get (0 ).wt ();
50+ for (int i = 1 ; i <mst .size () ; i ++) {
51+ mWeight = mWeight .doubleValue () + mst .get (i ).wt ().doubleValue ();
4752 }
53+
4854 }
4955 private void visit (WeightGraph graph , int v ){
5056 if (!visited [v ]) {
@@ -58,4 +64,30 @@ private void visit(WeightGraph graph , int v){
5864 }
5965 }
6066 }
67+
68+ /**
69+ * 最小生成树的总权值
70+ * @return
71+ */
72+ public Number mstWeight (){
73+ return mWeight ;
74+ }
75+
76+ public List <Edge <Weight >> getMstEdgeList (){
77+ return mst ;
78+ }
79+
80+ public static void main (String [] args ){
81+ String filename = "weighttestG3.txt" ;
82+
83+ WeightSparseGraph <Double > weightSparseGraph = new WeightSparseGraph <>(8 ,false );
84+ weightSparseGraph .readGraph (filename );
85+ weightSparseGraph .show ();
86+
87+ LazyPrimMST <Double > lazy = new LazyPrimMST <>(weightSparseGraph );
88+ System .out .println ("总权值是:" +lazy .mstWeight ());
89+ for (int i = 0 ; i <lazy .getMstEdgeList ().size () ; i ++) {
90+ System .out .println ("e:" +lazy .getMstEdgeList ().get (i ));
91+ }
92+ }
6193}
0 commit comments