Thursday, January 18, 2018

Kruskal's algorithm Wiki article

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