Part of list:
Minimum Spanning Tree (Prim's algorithm and Kruskal's algorithm)
Problem: Given an undirected weighted connected graph, a minimum spanning tree (MST) is a subset of the edges of the graph which forms a tree and has the minimum total edge weight.
Start with a arbitrary vertex as your tree. Grow your tree one vertex at a time by adding the minimum weight edge from a vertex in the current tree to a vertex not yet in the tree. If you so this using a min-heap, your algorithm run-time will be O(E log E). Since E <= V^2, this is also O(E log V).
Start with an empty tree. Iterate over the edges sorted by weight. If adding edge (u, v) to the current tree does not create a cycle, then add it, else discard it. If you use an adjacency list representation for the current tree, and a BFS / DFS to see if adding edge (u, v) forms a cycle, then your algorithm complexity is O(EV).
However, checking if adding (u, v) forms a cycle can be done in O(log V) using a disjoint-set data structure giving a complexity of O(E log V). The Wikipedia article on Disjoint-set data structure is quite good (you only need the Introduction and Disjoint-set forests sections).
Notes: Although we covered the algorithms, we didn't prove of understand why they work. We'll explore separately in a follow-up discussion.