Please enable JavaScript.
Coggle requires JavaScript to display documents.
Prim’s Algorithm, Disjoint Subsets and Union-Find Algorithms, Kruskal’s…
Prim’s Algorithm
The following problem arises naturally in many practical situations, if we represent the points given by vertices of a graph, the question can be posed as the minimum spanning tree problem
a spanning tree of an undirected connected graph is its connected acyclic subgraph that contains all the vertices of the graph
the minimum spanning tree problem is the problem of finding a minimum spanning tree for a given weighted connected graph
-
-
Kruskal’s Algorithm
Kruskal's algorithm is a greedy algorithm for finding the minimum spanning tree in a weighted connected graph.
The algorithm sorts the edges in non-decreasing order of their weights and scans the sorted list to add edges to the current subgraph without creating cycles.
Unlike Prim's algorithm, Kruskal's algorithm generates an acyclic subgraph but not necessarily a connected tree at each stage.
Kruskal's algorithm can be interpreted as a series of operations on disjoint sets using union-find algorithms.