Please enable JavaScript.
Coggle requires JavaScript to display documents.
Prim’s Algorithm, Disjoint Subsets and Union-Find Algorithms, Kruskal’s…
Prim’s Algorithm
After we have identified a vertex u∗ to be added to the tree, we need to perform two operations:
-
For each remaining vertex u in V − VT that is connected to u∗ by a shorter edge than the u’s current distance label, update its labels by u∗ and the weight of the edge between u∗ and u, respectively
-
-
-
-
Kruskal’s Algorithm
the algorithm constructs a minimum spanning tree as an expanding sequence of subgraphs that are always acyclic but are not necessarily connected on the intermediate stages of the algorithm.
The algorithm begins by sorting the graph’s edges in nondecreasing order of their weights. Then, starting with the empty subgraph, it scans this sorted list, adding the next edge on the list to the current subgraph if such an inclusion does not create a cycle and simply skipping the edge otherwise.
-