Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM13 - Coggle Diagram
MM13
Prim's Algorithm
Problem/motivation: Given n points, connect them the chapest possibler way so that there will be a path between every pair of points
spanning tree
-
minimum spanning tree: tree of the smallest weight, where the weight is defined as the sum of the weights on all its edges
-
-
the initial subtree 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 by simply attaching to it the nearest vertex not in that tree
Each vertex has two labels: the name of the nearest tree vertex and the length (the weight) of the corresponding edge
-
-
-
Kruskal's Algorithm
-
-
the initial forest consists of |V| trivial trees and the final forest consists of a single tree, which is the minimum spanning tree
Can be seen as a progression through a series of forests containing all the vertices of a given graph and some of its edges
Method
-
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
Union-find algorithms
partition a n element set into a collection of n one-element subsets, each contaning a different element of S
Alternatives for the ADT
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
each subset is implemented as a linked list whose header contains the pointers to the first and last elements of the list
-
-
Union by size: append the shorter of the two lists to the longer one, with ties broken arbitrarily
-
in union by size, the sequence of n-1 unions and m finds is O(n log n + m)
quick union
-
the nodes of the tree contain the subset's elements, with the root considered the representatives
-
-
-
the size can be measured either by the number of nodes (Union by size) or by its height (union by rank)
-
disjoint subset ADT
-
operations: makeset(x), union(x, y), find(x)