Please enable JavaScript.
Coggle requires JavaScript to display documents.
Minimum Spanning Tree Problem, Disjoint Subsets and Union-Find Algorithms,…
-
-
-
Given n points, connect them in the cheapest possible way so that will be a path between every pair of points
A spaning tree of an undirected connected graph is its tree that contains all the vertices of the graph. If it has weights assigned to it s edges, a minimum spanning tree is its spanning tree of the smallest weight (sum of the weights on all its edges).
- constructs a minimum spanning tree through a sequence of expanding subtrees
- the inicial subtree consists of a single vertex selected arbitrarily
- on each iteration, the algorithm expands the current tree in the greedy manner by simply attaching to it nearest vertex in the tree by an edge go the smallest weight
- the algorithm stops after all the graph's vertices have been included in the tree being constructed
-
- Adjacency Matrix and no heap: Θ(|V ²|)
- Adjacency List and Heap: Θ((|V | + |E |) log |V |)
It's a greedy algorithm that 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
- Adjacency Matrix and no heap: Θ(|V ²|)
- Adjacency List and Heap: Θ((|V | + |E |) log |V |)
-
-
-
- it's an element from each disjoint that will represent the subset
- optimizes the find operation
- optimizes the union operation
- uses an array indexed by the elements of the underlying set S
- the array's values indicate the representatives of the subsets containing the pointers to the first and last elements of the list along with the number of elements in the list
-
-
- represents each subset by a rooted tree - the tree's edges are directed from children to their parents
- the nodes of the tree contain the subset's elements (one per node), with the root's element considered the subset's representative
-
-