图算法

shinezejian · shinezejian · commit de4a8a7b4e48 · 2018-01-30T10:26:35.000+08:00
diff --git a/src/com/zejian/structures/Graph/WeightGraph/LazyPrimMST.java b/src/com/zejian/structures/Graph/WeightGraph/LazyPrimMST.java
@@ -16,7 +16,7 @@
 public class LazyPrimMST<Weight extends Number & Comparable<Weight>> {
     private boolean visited[]; //标记已被访问过的顶点
     private MinHeap<Edge<Weight>> minHeap; //存储权值的堆结构
-    private Weight mWeight; //最小生成树的总权值
+    private Number mWeight; //最小生成树的总权值
     private List<Edge<Weight>> mst;  //存放最小生成树的所有顶点
 
 
@@ -43,8 +43,14 @@ public LazyPrimMST(WeightGraph graph){
             }else if(!visited[e.w()]){
                 visit(graph,e.w());
             }
+        }
 
+        //计算最小生成树的权值
+        mWeight = mst.get(0).wt();
+        for (int i = 1; i <mst.size() ; i++) {
+            mWeight = mWeight.doubleValue() + mst.get(i).wt().doubleValue();
         }
+
     }
     private void visit(WeightGraph graph , int v){
         if(!visited[v]) {
@@ -58,4 +64,30 @@ private void visit(WeightGraph graph , int v){
             }
         }
     }
+
+    /**
+     * 最小生成树的总权值
+     * @return
+     */
+    public Number mstWeight(){
+        return mWeight;
+    }
+
+    public List<Edge<Weight>> getMstEdgeList(){
+        return mst;
+    }
+
+    public static void main(String[] args){
+        String filename = "weighttestG3.txt";
+
+        WeightSparseGraph<Double> weightSparseGraph = new WeightSparseGraph<>(8,false);
+        weightSparseGraph.readGraph(filename);
+        weightSparseGraph.show();
+
+        LazyPrimMST<Double> lazy = new LazyPrimMST<>(weightSparseGraph);
+        System.out.println("总权值是:"+lazy.mstWeight());
+        for (int i = 0; i <lazy.getMstEdgeList().size() ; i++) {
+            System.out.println("e:"+lazy.getMstEdgeList().get(i));
+        }
+    }
 }
diff --git a/src/com/zejian/structures/Graph/WeightGraph/PrimMST.java b/src/com/zejian/structures/Graph/WeightGraph/PrimMST.java
@@ -0,0 +1,22 @@
+package com.zejian.structures.Graph.WeightGraph;
+
+import com.zejian.structures.heap.IndexMinPQ;
+
+import java.util.List;
+
+/**
+ * Created by zejian on 2018/1/30.
+ * Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
+ * 优化版的最小生成树算法
+ * 利用最小索引堆
+ */
+public class PrimMST<Weight extends Number & Comparable<Weight>> {
+
+    private IndexMinPQ<Weight>  pq;//最小索引堆,只存储权值更小的边,不会存放所有边
+    private boolean marked[];//标记数组, 在算法运行过程中标记节点i是否被访问
+    private Edge edgeTo[];//访问的点所对应的边, 因为索引堆中没存放具体边信息
+    private List<Edge<Weight>> mst;     // 最小生成树所包含的所有边
+    private Number mWeight; //最小生成树的总权值
+
+
+}
diff --git a/src/com/zejian/structures/Graph/WeightGraph/WeightGraph.java b/src/com/zejian/structures/Graph/WeightGraph/WeightGraph.java
@@ -76,7 +76,7 @@ public void readGraph(String filename){
                 double weight = scanner.nextDouble();
                 assert v >= 0 && v < V;
                 assert w >= 0 && w < V;
-                this.addEdge((Edge<Weight>) new Edge<Double>(v,w,weight));
+                this.addEdge(new Edge(v,w,weight));
             }
         }
         catch (InputMismatchException e) {

Original file line number	Diff line number	Diff line change
`@@ -76,7 +76,7 @@ public void readGraph(String filename){`
`76`	`76`	`double weight = scanner.nextDouble();`
`77`	`77`	`assert v >= 0 && v < V;`
`78`	`78`	`assert w >= 0 && w < V;`
`79`		`- this.addEdge((Edge<Weight>) new Edge<Double>(v,w,weight));`
	`79`	`+ this.addEdge(new Edge(v,w,weight));`
`80`	`80`	`}`
`81`	`81`	`}`
`82`	`82`	`catch (InputMismatchException e) {`