Please enable JavaScript.
Coggle requires JavaScript to display documents.
(M14) CHAPTER 9 (9.1 AND 9.2) - Coggle Diagram
(M14) CHAPTER 9 (9.1 AND 9.2)
PRIM'S ALGORITHM
GIVEN N POINTS, CONNECT THEM ALL IN THE CHEAPEST WAY
IDENTIFIES CLUSTERS OF POINTS IN DATA SETS
ALSO USED
PURPOSES IN ARCHEOLOGY
BIOLOGY
SOCIOLOGY
SOLUTIONS FOR DIFFICULT COMPUTER PROBLEMS
TWO SETS
FRINGE
UNSEEN
IMPLEMENTED WITH MIN-HEAP
TEMPORAL EFFICIENCY
UNORDERED ARRAY
Θ(|V|²)
ADJACENCY LIST
O(|E| log |V|)
KRUSKAL'S ALGORITHM
CREATE MINIMUM SPANNING TREE
SORT GRAPH'S EDGES IN NONDECREASING ORDER
SCAN THE LIST AND ADD NEXT EDGE
EACH CONNECTED COMPONENT OF A SUBGRAPH IS A TREE
THERE IS NO CYCLE
TEMPORAL EFFICIENCY
O(|E| log |E|)
REQUIRES
DISJOINT SUBSETS
A DYNAMIC PARTITION OF SOME N ELEMENTS
SUBSET'S REPRESENTATIVE
MAIN FUNCS
MAKESET
FIND
UNION
BY SIZE
BY RANK
VARIATIONS
QUICK-FIND
OPTIMIZES TIME EFFICIENCY OF FIND OPERATIONS
QUICK-UNION
OPTIMIZES TIME EFFICIENCY OF UNION OPERATIONS
IMPLEMENTATION OF DISJOINT SUBSETS
PATH COMPRESSION
BETTER EFFICIENCY
APPENDS THE SMALLER LIST TO THE LONGER ONE