n 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.
- For each edge by weight ascending
- If nodes are in same component, forget/skip
- 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:
he following is an implementation of Prim’s algorithm (Wikipedia
) using a pairing heap (Wikipedia
). This is a greedy algorithm used to find a weighted undirected graph’s minimum spanning tree (Wikipedia
My implementation is used to solve SPOJ 3188. Minimum Spanning Tree MST, and is in git and below:
osaraju’s algorithm (Wikipedia
) finds a graph’s strongly connected components in linear time.
The algorithm runs in two phases:
- grab an unseen node and perform depth-first search.
- add node to stack after children processed.
- while unseen nodes exist…
- pop node off stack.
- graph traversed against directed edges.
- all within traversal belong to one strongly-connected component.
- while stack is not empty…
This algorithm is used in my solving of SPOJ 13990. Web islands WEBISL; implementation is in git and below: