Please enable JavaScript.
Coggle requires JavaScript to display documents.
M14 - Coggle Diagram
M14
Prims algorithm
book summary of the algorithm
A spanning tree of an undirected connected graph is its connected to an 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.
pseudo
//Prim’s algorithm for constructing a minimum spanning tree
//Input: A weighted connected graph G = V,E
//Output: ET , the set of edges composing a minimum spanning tree of G
VT ← {v0} //the set of tree vertices can be initialized with any vertex
ET ← ∅
for i ← 1 to |V | − 1 do
find a minimum-weight edge e∗ = (v∗, u∗) among all the edges (v, u)
such that v is in VT and u is in V − VT
VT ← VT ∪ {u∗}
ET ← ET ∪ {e∗}
return ET
Kruskal algorithm
book summary of the algorithm itself
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.
pseudocode
//Kruskal’s algorithm for constructing a minimum spanning tree
//Input: A weighted connected graph G = V,E
//Output: ET , the set of edges composing a minimum spanning tree of G
sort E in nondecreasing order of the edge weights w(ei1
) ≤ ... ≤ w(ei|E|
)
ET ← ∅; ecounter ← 0 //initialize the set of tree edges and its size
k ← 0 //initialize the number of processed edges
while ecounter < |V | − 1 do
k ← k + 1
if ET ∪ {eik
} is acyclic
ET ← ET ∪ {eik
}; ecounter ← ecounter + 1
return ET