Kruskals Algorithm
A friend studying mathematics requested an example of converting a written description to pseudo-code to code, this is that.
Pseudo-code F := ∅ /* Map of vertex to tree */
E /* List of edges */
for v ∈ G.V
F[v] = ∅
E := SORT_ASCENDING(G.E)
for (u, v) ∈ E
if F[v] ≠ F[u]
F[u] := F[v] := F[u] ∪ F[v] ∪ {(u,v)}
return F[0]
Javascript: function kruskal(graph) {
let forest = {} // Map of vertices to trees
let edges = [] // List of edges
graph.vertices.forEach((vertex) => {
forest[vertex] = {}
})
/* An ascending sort */
edges = graph.edges.sort((edgeA, edgeB) => {
return edgeA.cost - edgeB.cost
})
edges.forEach((edge) => {
if(forest[edge.start] != forest[edge.end]) {
forest[edge.start] = forest[edge.end] =
forest.edge[start].concat(forest.edge[end]).push(edge)
}
})
return Object.values(forest).shift()
}