January 18, 2018
Introduction
It is the very good investment of time to read the article of Kruskal's algorithm on the wiki page. What I do is to go over each word and each sentence slowly, write down some new terms I like to learn. Today I spent over 30 minutes to read the article.
Kruskal's algorithm
Plan to spend 20 minutes to read the article first.
Terms:
minimum-spanning-tree algorithm
greedy algorithm in graph theory
minimum spanning tree
a subset of edges that forms the tree that includes every vertex, where the total weight of all the edges in the tree is minimized.
How to read the algorithm Kruskal's algortihm
How to read the graph simulation of steps: b and e are added, but there is a cycle.
Average performance: O(|E|log|V|)
Worset-case space complexity:
Prim's algorithm, Reverse-delete algorithm, Boruvka's algorithm
comparison sort
disjoint-set data structure
union by rank
(counting sort or radix sort) Ackerman function
induction -
minimality
No comments:
Post a Comment