| 6 | * @return {Graph} |
| 7 | */ |
| 8 | export default function prim(graph) { |
| 9 | // It should fire error if graph is directed since the algorithm works only |
| 10 | // for undirected graphs. |
| 11 | if (graph.isDirected) { |
| 12 | throw new Error('Prim\'s algorithms works only for undirected graphs'); |
| 13 | } |
| 14 | |
| 15 | // Init new graph that will contain minimum spanning tree of original graph. |
| 16 | const minimumSpanningTree = new Graph(); |
| 17 | |
| 18 | // This priority queue will contain all the edges that are starting from |
| 19 | // visited nodes and they will be ranked by edge weight - so that on each step |
| 20 | // we would always pick the edge with minimal edge weight. |
| 21 | const edgesQueue = new PriorityQueue(); |
| 22 | |
| 23 | // Set of vertices that has been already visited. |
| 24 | const visitedVertices = {}; |
| 25 | |
| 26 | // Vertex from which we will start graph traversal. |
| 27 | const startVertex = graph.getAllVertices()[0]; |
| 28 | |
| 29 | // Add start vertex to the set of visited ones. |
| 30 | visitedVertices[startVertex.getKey()] = startVertex; |
| 31 | |
| 32 | // Add all edges of start vertex to the queue. |
| 33 | startVertex.getEdges().forEach((graphEdge) => { |
| 34 | edgesQueue.add(graphEdge, graphEdge.weight); |
| 35 | }); |
| 36 | |
| 37 | // Now let's explore all queued edges. |
| 38 | while (!edgesQueue.isEmpty()) { |
| 39 | // Fetch next queued edge with minimal weight. |
| 40 | /** @var {GraphEdge} currentEdge */ |
| 41 | const currentMinEdge = edgesQueue.poll(); |
| 42 | |
| 43 | // Find out the next unvisited minimal vertex to traverse. |
| 44 | let nextMinVertex = null; |
| 45 | if (!visitedVertices[currentMinEdge.startVertex.getKey()]) { |
| 46 | nextMinVertex = currentMinEdge.startVertex; |
| 47 | } else if (!visitedVertices[currentMinEdge.endVertex.getKey()]) { |
| 48 | nextMinVertex = currentMinEdge.endVertex; |
| 49 | } |
| 50 | |
| 51 | // If all vertices of current edge has been already visited then skip this round. |
| 52 | if (nextMinVertex) { |
| 53 | // Add current min edge to MST. |
| 54 | minimumSpanningTree.addEdge(currentMinEdge); |
| 55 | |
| 56 | // Add vertex to the set of visited ones. |
| 57 | visitedVertices[nextMinVertex.getKey()] = nextMinVertex; |
| 58 | |
| 59 | // Add all current vertex's edges to the queue. |
| 60 | nextMinVertex.getEdges().forEach((graphEdge) => { |
| 61 | // Add only vertices that link to unvisited nodes. |
| 62 | if ( |
| 63 | !visitedVertices[graphEdge.startVertex.getKey()] |
| 64 | || !visitedVertices[graphEdge.endVertex.getKey()] |
| 65 | ) { |