Prim’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. 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.

Continue reading

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.

Continue reading

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.

Continue reading

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.

Continue reading