Please enable JavaScript.
Coggle requires JavaScript to display documents.
M13 - Coggle Diagram
M13
Prim's algorithm
If implemented as weight matrix + priority queue as unordered array, efficiency is in Θ(V²)
If implemented as adjacency list + minHeap, efficiency is on Ο(Ε log(V))
Greedy algorithm, for every iteration connects to the nearest unconnected vertex
-
The vertexes witch are not yet on the tree must be labeled with the nearest tree vertex, to ease the search
Given n points, connect them in the cheapest possible way so there will be a path between every pair of points
Kruskal's algorithm
-
Can be interpreted as a progression trough a series of forests containing all the vertices and some edges of the graph, until it reaches the final forest, which is a single tree, the minimum spanning tree of the graph
-
To check if two forests containing vertexes that have a connection are not the same, we use union-find algorithms
-
Disjoint subsets
-
Quick find
-
Uses an array which point to the value of the representative, which, by its turn, is inside a linked list containing all the elements in the subset indexed by the array
-
-
-
A data structure capable of making subsets of a given set, and implement union and find operations