Please enable JavaScript.
Coggle requires JavaScript to display documents.
minimum spanning tree problem - Coggle Diagram
minimum spanning tree problem
Problems
2º generating
all spanning trees for a given graph is not easy
1º the number of spanning trees grows
exponentially with the graph size
Prim's Algorithm
Connect the nearest vertex not in the tree
vertex's labels
the name of the nearest tree vertex
the length (the weight) of the
corresponding edge
After indentified a vertex u
*
Move u∗ from the set V − VT to the set of tree vertices VT.
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.
vertex not in the tree
set 1: the length (the weight) of the
corresponding edge
set 2: The unseen vertices are all the other vertices of the graph
Kruskal’s
Algorithm
The algorithm begins by sorting the graph’s edges in nondecreasing order of
their weights
Add 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
Disjoint Subsets and Union-Find Algorithms
Operations
ind(x) returns a subset containing x
makeset(x) creates a one-element set {x}. It is assumed that this operation can
be applied to each of the elements of set S only once
union(x, y) constructs the union of the disjoint subsets Sx and Sy containing x and y, respectively, and adds it to the collection to replace Sx and Sy, which are deleted from it
quick union
represents each subset by a rooted tree
quick find
Uses an array indexed by the elements of the underlying set S; the array’s values indicate the representatives of the subsets containing those elements