Please enable JavaScript.
Coggle requires JavaScript to display documents.
Prim’s Algorithm, Kruskal’s Algorithm - Coggle Diagram
Prim’s Algorithm
given n points, connect them in the cheapest possible way so that there will be a path between every pair of points.
-
A spanning tree of an undirected connected graph is its connected
acyclic subgraph (i.e., a tree) that contains all the vertices of the graph.
Minimum spanning tree
it's its spanning tree of the smallest weight, where the weight of a tree is defined as the sum of the weights on all its edges.
-
-
Efficiency
depends on the data structures chosen for the graph itself and for the priority queue of the set V − VT whose vertex priorities are the distances to the nearest tree vertices.
-
-
//Input: A weighted connected graph G = V,E
//Output: ET , the set of edges composing a minimum spanning tree of G
-
-
-
find a minimum-weight edge e∗ = (v∗, u∗) among all the edges (v, u)
-
-
-
-
Kruskal’s Algorithm
-
-
//Input: A weighted connected graph G = V,E
//Output: ET , the set of edges composing a minimum spanning tree of G
-
-
-
-
-
-
-
-
-
-
-
-
-
Kruskal’s algorithm looks at a minimum spanning tree of a weighted connected graph G = V,E as an acyclic subgraph with |V | − 1 edges for which the sum of the edge weights is the smallest.
-
Kruskal's Algorithm is used to find the minimum spanning tree for a connected weighted graph. The main target of the algorithm is to find the subset of edges by using which we can traverse every vertex of the graph.