Fix the Prim's MST algorithm

mgechev · mgechev · commit 9d899933023b · 2014-11-24T13:47:18.000+02:00
diff --git a/src/graphs/spanning-trees/prim.js b/src/graphs/spanning-trees/prim.js
@@ -34,9 +34,10 @@ function Edge(e, v, distance) {
  * @constructor
  * @public
  */
-function Graph(edges) {
+function Graph(edges, nodesCount) {
   'use strict';
   this.edges = edges || [];
+  this.nodesCount = nodesCount || 0;
 }
 
 /**
@@ -57,9 +58,6 @@ Graph.prototype.prim = (function () {
    */
   function init() {
     queue = new Heap(compareEdges);
-    this.edges.forEach(function (e) {
-      queue.add(e);
-    });
   }
 
   /**
@@ -84,18 +82,57 @@ Graph.prototype.prim = (function () {
   return function () {
     init.call(this);
     var inTheTree = {},
-        current = queue.extract(),
-        spannigTree = [];
-    spannigTree.push(current);
-    inTheTree[current.e.id] = true;
-    while (queue.isEmpty()) {
-      current = queue.extract();
-      if (!inTheTree[current.v.id] ||
-        !inTheTree[current.e.id]) {
-        spannigTree.push(current);
-        inTheTree[current.e.id] = true;
-        inTheTree[current.v.id] = true;
-      }
+        startVertex = this.edges[0].e.id,
+        spannigTree = [],
+        parents = {},
+        distances = {},
+        current;
+    inTheTree[startVertex] = true;
+    queue.add({
+      node: startVertex,
+      distance: 0
+    });
+    for (var i = 0; i < this.nodesCount - 1; i += 1) {
+      current = queue.extract().node;
+      inTheTree[current] = true;
+      this.edges.forEach(function (e) {
+        if (inTheTree[e.v.id] && inTheTree[e.e.id]) {
+          return;
+        }
+        var collection = queue.getCollection(),
+            node;
+        if (e.e.id === current) {
+          node = e.v.id;
+        } else if (e.v.id === current) {
+          node = e.e.id;
+        } else {
+          return;
+        }
+        for (var i = 0; i < collection.length; i += 1) {
+          if (collection[i].node === node) {
+            if (collection[i].distance > e.distance) {
+              queue.changeKey(i, {
+                node: node,
+                distance: e.distance
+              });
+              parents[node] = current;
+              distances[node] = e.distance;
+            }
+            return;
+          }
+        }
+        queue.add({
+          node: node,
+          distance: e.distance
+        });
+        parents[node] = current;
+        distances[node] = e.distance;
+      });
+      console.log(queue._heap);
+      console.log();
+    }
+    for (var node in parents) {
+      spannigTree.push(new Edge(node, parents[node], distances[node]));
     }
     return new Graph(spannigTree);
   };
@@ -104,71 +141,29 @@ Graph.prototype.prim = (function () {
 
 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
  * * * * * * * * * * * * * *  Sample graph * * * * * * * * * * *
- * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
  
-var graph;
-
 (function () {
-    var edges = [];
-   
-    edges.push(new Edge(
-        new Vertex(0),
-        new Vertex(1),
-        7
-    )); 
-
-    edges.push(new Edge(
-        new Vertex(0),
-        new Vertex(2),
-        9
-    )); 
-
-    edges.push(new Edge(
-        new Vertex(0),
-        new Vertex(5),
-        16 
-    )); 
-
-    edges.push(new Edge(
-        new Vertex(1),
-        new Vertex(2),
-        10
-    )); 
-
-    edges.push(new Edge(
-        new Vertex(1),
-        new Vertex(3),
-        15
-    )); 
-
-    edges.push(new Edge(
-        new Vertex(2),
-        new Vertex(3),
-        11
-    )); 
-
-    edges.push(new Edge(
-        new Vertex(2),
-        new Vertex(5),
-        2
-    )); 
-
-    edges.push(new Edge(
-        new Vertex(3),
-        new Vertex(4),
-        6
-    )); 
-
-    edges.push(new Edge(
-        new Vertex(4),
-        new Vertex(5),
-        9
-    )); 
-
-    graph = new Graph(edges);
-
+  'use strict';
+  var graph, edges = [];
+  edges.push(new Edge(new Vertex(0), new Vertex(1), 4));
+  edges.push(new Edge(new Vertex(0), new Vertex(7), 8));
+  edges.push(new Edge(new Vertex(1), new Vertex(7), 11));
+  edges.push(new Edge(new Vertex(1), new Vertex(2), 8));
+  edges.push(new Edge(new Vertex(2), new Vertex(8), 2));
+  edges.push(new Edge(new Vertex(2), new Vertex(3), 7));
+  edges.push(new Edge(new Vertex(2), new Vertex(5), 4));
+  edges.push(new Edge(new Vertex(2), new Vertex(3), 7));
+  edges.push(new Edge(new Vertex(3), new Vertex(4), 9));
+  edges.push(new Edge(new Vertex(3), new Vertex(5), 14));
+  edges.push(new Edge(new Vertex(4), new Vertex(5), 10));
+  edges.push(new Edge(new Vertex(5), new Vertex(6), 2));
+  edges.push(new Edge(new Vertex(6), new Vertex(8), 6));
+  edges.push(new Edge(new Vertex(8), new Vertex(7), 7));
+  graph = new Graph(edges, 9);
+
+  console.log(graph.prim());
 }());
 
-console.log(graph.prim());
 
-* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
