Please enable JavaScript.
Coggle requires JavaScript to display documents.
M14, ((//Kruskal’s algorithm for constructing a minimum spanning tree,…
M14
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. If such a graph has weights assigned to its edges, a minimum spanning tree is 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. The minimum spanning tree problem is the problem of finding a minimum spanning tree for a given weighted connected graph.
Prim’s algorithm
Prim’s algorithm constructs a minimum spanning tree through a sequence of expanding subtrees. The initial subtree in such a sequence consists of a single vertex selected arbitrarily from the set V of the graph’s vertices. On each iteration, the algorithm expands the current tree in the greedy manner by simply attaching to it the nearest vertex not in that tree.
If a graph is represented by its adjacency lists and the priority queue is implemented as a min-heapO(|E| log |V |)
-
//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
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. (It is not difficult to prove that such a subgraph must be a tree.) Consequently, 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.
-
//Input: A weighted connected graph G = V,E
//Output: ET , the set of edges composing a minimum spanning tree of G
-
-
-
-
-
-
-
-
-
-