forked from algorithm-visualizer/algorithm-visualizer
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcode.js
More file actions
31 lines (30 loc) · 1.08 KB
/
code.js
File metadata and controls
31 lines (30 loc) · 1.08 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function prim(){
// Finds a tree so that there exists a path between
// every two nodes while keeping the cost minimal
var minD, minI, minJ, sum=0, D=[];
for(var i = 0; i < G.length; i++) D.push(0);
D[0] = 1; // First node is visited
for(var k = 0; k < G.length-1; k++){ // Searching for k edges
minD = Infinity;
for(i = 0; i< G.length; i++)
if(D[i]) // First node in an edge must be visited
for(var j = 0; j < G.length; j++)
if(!D[j] && G[i][j]){
tracer._visit(i, j);
// Second node must not be visited and must be connected to first node
if(G[i][j] < minD){
// Searching for cheapest edge which satisfies requirements
minD = G[i][j];
minI = i;
minJ = j;
}
tracer._leave(i, j);
}
tracer._visit(minI, minJ);
D[minJ] = 1; // Visit second node and insert it into or tree
sum += G[minI][minJ];
}
tracer._print("The sum of all edges is: " + sum);
}
tracer._print("nodes that belong to minimum spanning tree are: ");
prim();