Kruskal’s Algorithm & Quick Union

In my previous post I implemented Prim’s algorithm with pairing heap. Now, here’s another way to find the minimum spanning tree, using Kruskal’s algorithm (Wikipedia) with quick union. If you compare the code between posts, this is a whole lot simpler.

The gist:

  1. For each edge by weight ascending
  2. If nodes are in same component, forget/skip
  3. Else take edge and merge the two components

Here’s my implementation used in the solving of SPOJ 368. Cobbled Streets CSTREET, in git and below:
Continue reading

Kosaraju’s Algorithm

Kosaraju’s algorithm (Wikipedia) finds a graph’s strongly connected components in linear time.

The algorithm runs in two phases:

Phase 1:

  1. grab an unseen node and perform depth-first search.
  2. add node to stack after children processed.
  3. while unseen nodes exist…

Phase 2:

  1. pop node off stack.
  2. graph traversed against directed edges.
  3. all within traversal belong to one strongly-connected component.
  4. while stack is not empty…

This algorithm is used in my solving of SPOJ 13990. Web islands WEBISL; implementation is in git and below:
Continue reading