alcoranpaul
commented
6 days ago References: Primary
- https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/
- https://en.wikipedia.org/wiki/Prim%27s_algorithm
Secondary
- https://www.freecodecamp.org/news/prims-algorithm-explained-with-pseudocode/
- https://www.programmingalgorithms.com/algorithm/prim's-algorithm/
- https://github.com/vazgriz/DungeonGenerator/blob/master/Assets/Prim.cs
Idea is that given paths (blue color) there should be a path from room to room , without having to visit a room that has already been visited.
so:
- Pick a random roomto start from
- Add that room to the visited rooms list
- Add the nearby rooms of the selected room
- Calculate the distance that should be taken from the nearby rooms of the selected room 5.find the shorted distance/path from a room into a list called mst
- put the remaining paths into a list called unused paths
- add the new room from the selected shortened path into visited rooms list
- calculate and add the new room's nearby rooms, excluding the already visited rooms
- Repeat step 4 - 8 until the number of paths in mst is the same as the number of rooms
used Prim’s algorithm
@ https://en.wikipedia.org/wiki/Prim%27s_algorithm The algorithm may informally be described as performing the following steps:
Initialize a tree with a single vertex, chosen arbitrarily from the graph. Grow the tree by one edge: Of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree. Repeat step 2 (until all vertices are in the tree). In more detail, it may be implemented following the pseudocode below.
Associate with each vertex v of the graph a number C[v] (the cheapest cost of a connection to v) and an edge E[v] (the edge providing that cheapest connection). To initialize these values, set all values of C[v] to +∞ (or to any number larger than the maximum edge weight) and set each E[v] to a special flag value indicating that there is no edge connecting v to earlier vertices. Initialize an empty forest F and a set Q of vertices that have not yet been included in F (initially, all vertices). Repeat the following steps until Q is empty: Find and remove a vertex v from Q having the minimum possible value of C[v] Add v to F Loop over the edges vw connecting v to other vertices w. For each such edge, if w still belongs to Q and vw has smaller weight than C[w], perform the following steps: Set C[w] to the cost of edge vw Set E[w] to point to edge vw. Return F, which specifically includes the corresponding edges in E As described above, the starting vertex for the algorithm will be chosen arbitrarily, because the first iteration of the main loop of the algorithm will have a set of vertices in Q that all have equal weights, and the algorithm will automatically start a new tree in F when it completes a spanning tree of each connected component of the input graph. The algorithm may be modified to start with any particular vertex s by setting C[s] to be a number smaller than the other values of C (for instance, zero), and it may be modified to only find a single spanning tree rather than an entire spanning forest (matching more closely the informal description) by stopping whenever it encounters another vertex flagged as having no associated edge.
Different variations of the algorithm differ from each other in how the set Q is implemented: as a simple linked list or array of vertices, or as a more complicated priority queue data structure. This choice leads to differences in the time complexity of the algorithm. In general, a priority queue will be quicker at finding the vertex v with minimum cost, but will entail more expensive updates when the value of C[w] changes.