The problem is to find the minimum weight spanning tree (i.e., a connected acyclic subgraph) of an undirected weighted graph. Earlier, I described the Kruskal’s algorithm to find the MST in time O(E log V). Prim’s algorithm is another greedy algorithm that finds an MST in time O(E log V). The difference is that the Prim’s algorithm grows an MST, starting from a single vertex, always adding the least-cost edge from a tree vertex to a non-tree vertex to the current set of edges in the MST.

# Monthly Archives: May 2013

# Indexed Min-Priority Queue C++ implementation

A min-priority queue is an abstract data structure that supports efficient query of the minimum element in a list of elements, insertion of elements and deletion of the minimum element. It can be implemented as a min-heap, providing access to the minimum element in O(1), deletion of the minimum element in O(log N) and insertion in O(log N) where N is the number of elements in the heap.

# Kruskal’s Minimum Spanning Tree Algorithm

The problem is to find the minimum weight spanning tree (i.e., a connected acyclic subgraph) of an undirected weighted graph. Kruskal’s algorithm finds the MST in time O(E log V). It is a greedy algorithm that always tries to add the next least-cost edge to the current set of edges in the MST if its addition does not create a cycle in the MST.

# Counting inversions in an array

The problem is to count the number of inversions in an array. Two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.

For example, the sequence 1, 20, 6, 4, 5 has five inversions (20, 6), (20, 4), (20, 5), (6, 4) and (6, 5).

# Randomized selection algorithm

The problem is to find the i^{th} order statistic (i.e., i^{th} smallest element) in an input array. This algorithm is a modification of quicksort and takes time O(n), on average, on an input array of size n.

# Solving 2-SAT in linear time

2-Satisfiability (2-SAT) is the problem of determining whether a collection of boolean variables with constraints on pairs of variables can be assigned values satisfying all the constraints. Although 3-SAT is NP complete, 2-SAT can be solved in linear time.

# Strongly Connected Components in a Directed Graph C++ implementation

Here, I describe the Kosaraju-Sharir algorithm for finding the strongly connected components in a directed graph and provide its C++ implementation.