| Property | Bubble Sort | Insertion Sort | Selection Sort | Merge Sort | QuickSort (first element pivot) | QuickSort (random pivot) |
|---|---|---|---|---|---|---|
| Stablity | Yes | Yes | No | Yes | No | No |
| Running time | O(n^2), \Omega(n) | O(n^2), \Omega(n) | \Theta(n^2) | \Theta(nlogn) | O(n^2) | E[T(n)] = O(nlogn) |
| Worst case input | Reversed array | Reverse array | All inputs | All inputs are average-case | Sorted array | All inputs are average-case |
| Invariant | At the end of the i^{th} iteration, largest i elements are sorted in their correct positions. | At the end of the i^{th} iteration, the first i elements in the array are relatively sorted | At the end of the i^{th} iteration, the smallest i elements are correctly sorted in the first i positions of th array. | For every call to merge, both its arguments are always sorted. | After performing the partition, all elements smaller than the pivot occur before the pivot, and all elements larger than the pivot occur after the pivot | After performing the partition, all elements smaller than the pivot occur before the pivot, and all elements larger than the pivot occur after the pivot |
| Extra space | O(1) (In-place) | O(1) (In-place) | O(1) (In-place) | O(n) | O(1) (In-place) | O(1) (In-place) |
3. **Cycle property: For every cycle, the maximum weight edge is not in the MST.**
1. Proof (Cut and paste argument): Assume the heaviest edge is in the MST. Now, remove the maximum weight edge. This cuts the MST into 2 MSTs. Since there is a cycle, there is another edge (the one that we left out initially) that joins the 2 MSTs. Use this edge to join. The total weight is lower since you replaced a heavier edge with a lighter one. Moreover, you still get a spanning tree. Hence, it contradicts the fact that the initial ST was an MST.
2. In the proof above, we implicitly used the idea that for any cycle, an even number of edges are cut across a cut (for any line drawn, the cycle intersects the line at an even number of points)
3. It is important to note that the inverse of the cycle property is not true in general, i.e., the statement “For every cycle, the minimum weight edge is always in the MST” is false! In fact, a minimum weight edge of one cycle can be the maximum weight edge of another cycle and hence, by the cycle property itself, it cannot be in the MST. Hence, **for every cycle, the minimum weight edge may or may not be in the MST.**
4. **Cut property**: Let us define a **cut** of a graph $$G = (V,E)$$ as a partition of the vertices $$V$$ into 2 disjoint subsets. An edge is said to **cross a cut** if it has one vertex in each of the two disjoint subsets. Then, **for every partition of the nodes, the minimum weight edge across the cut is in the MST.**
1. Proof is similar to the cut and paste argument made as in the cycle property. Suppose not. Then another edge that crosses the cut must be in the MST (which has a weight higher than our minimum weight edge that crosses the cut). We can “cut and paste” this edge to get an MST of lower weight. So, our assumption was incorrect. Hence, proved.
2. A direct consequence of the cut property is that **for every vertex, the minimum outgoing edge is always part of the MST**. This follows necessarily because the cut property holds for **any** partition. In particular, we can create $$V$$ partitons - each of which divides the graph into 2 sets - one containing exactly one node, and the other containing the rest of the nodes.
3. The inverse of the cut property is not true in general, i.e., the statement “The maximum outgoing edge is never part of the MST” is false. It is easy to come up with some examples to prove this. (e.g. in the graph above, look at the rightmost node. Both its edges are in the MST. In particular, the maximum outgoing edge is in the MST. Hence, **for every node, the maximum outgoing edge may or may not be part of the MST.**
Can an MST be used to find the smallest maximum edge path between two nodes? That is, if we define the weight of a path to be the maximum weight of all the edges in the path, does the shortest path between two nodes lie on the MST?
Yes! At every step, we are trying to put the minimum weight edge into the MST. So, naturally, all the edges in the MST have low weight. This leads to the minimsation of the maximum edge path between any two nodes. (Note that an MST minimizes the maximum edge weight present in the path, but NOT the total sum of the weights along the path)
#### Generic MST Algorithm
Every MST algorithm relies fundamentally on the following two rules:
1. **Red rule: If C is a cycle with no red arcs, then colour the maximum weight edge in C red.**
2. **Blue rule: If D is a cut with no blue arcs across the cut, then colour the minimum weight edge in D blue.**
In the end, all the blue edges will form an MST. The above generic algorithm is just a direct cosequence of the cycle property and the cut property. So, we can greedily build the MST by repeatedly applying red rule or blue rule to an arbitrary edge.
## Prim’s Algorithm (Jarnik 1930, Dijkstra 1957, Prim 1959)
The algorithm itself is based on the cut property and quite simple to understand:
1. Pick an arbitrary node $$u$$
2. Add it to a set (which will store all the nodes already connected by the spanning tree) *`sptSet`*
3. Look (read: relax) at all the outgoing edges of $$u$$ (essentially, observe the edges that are across the cut $$V - sptSet$$ and $$sptSet$$) and update the distances of other nodes in the priority queue by setting the distance of each node to be the minimum of the current distance and the weight of this edge connecting $$u$$ and this node). Pick the minimum weight edge connecting a node in *`sptSet`* to one outside the *`sptSet`*. Say, the other node is $$v$$. Add $$v$$ to the *`sptSet`* and add the edge connecting $$(u,v)$$ to a set that stores the edges of the MST.
4. Then, look at all the outgoing edges of the newly added node $$v$$ and update the distances of other nodes in the priority queue.
5. Pick the minimum node in the priority queue (the least distance between this node and any node already in the *`sptSet`*).
6. Repeat steps 2-6 until the priority queue is empty (all nodes are in the *`sptSet`*)
Note: **The priority queue stores the nodes outside the *****sptSet***** prioritised by their minimum distance to any node inside the *****sptSet*****.**
A key invariant of Prim’s algorithm is that at every step, the edges being chosen form an MST for those set of nodes connected by the tree. That is, it greedily builds the MST. This is in contrast to Kruskal’s algorithm in which the edges at any arbitrary step need not form a tree (since they may be disconnected). So, if you stop runnning Prim’s algorithm midway, you still get an MST for a subset of the original graph, but this is not true for Kruskal’s as you get mulitple MSTs for multiple subsets of the graph.
Another observation is that every node in the graph is either in the priority queue or the *`sptSet`*. That is, the two form a partition of the set of nodes.
### Pseudocode
```java
while (!pq.isEmpty()) {
Node u = pq.deleteMin();
sptSet.put(u);
for each (Edge e: u.edgeList()) {
Node v = e.otherNode(u);
if (v not in sptSet && pq.getPriority(v) > e.getWeight()) // v is either in sptSet or in pq
pq.decreaseKey(v, e.getWeight());
parent.put(v,u); // mark that we visited v from u in the MST
```
Initially, other than the starting node, the priorities of all other nodes are `Integer.MAX_VALUE` since we don’t know the distances.
### Running time of Prim’s using AVL tree for PQ: $$O(ElogV)$$
`decreaseKey` operation takes $$O(logn)$$ when there are $$n$$ elements in the PQ implemented using AVL tree.
In this case, the size of the PQ is at most $$V$$ since it stores the vertices. We look at each vertex once (total cost $$V$$) when we delete it from the PQ (total cost $$O(VlogV)$$). We look at each edge once and perform at most one `decreaseKey` operation per edge (total cost $$O(ElogV)$$).
Adding all the costs together and assuming $$E \geq V - 1$$, **the running time of Prim’s is** $$O(ElogV)$$**.**
Notice how we analysed the algorithm above by assigning each cost of an operation to an edge or a vertex. So, rather than thinking in terms of each node and each edge, we think from a higher level and view the total cost of an operation as being dependent on the number of edges or vertices. This makes it much easier to analyse.
It is worthwhile to compare Prim’s algorithm to Dijkstra’s since they are quite similar (mostly because Dijkstra also came up with this algorithm for making an MST)
| Prim’s MST | Dijkstra’s Shortest Path |
| ---------------------------------------------------------------------- | ------------------------------------------------------------------------------- |
| Maintain a set of visited nodes (`sptSet`) | Maintain a set of visited nodes (not in the priority queue) |
| Greedily grow the set by adding a node connected via the lightest edge | Greedily grow the set by adding neighbouring node that is closest to the source |
| Use PQ to order nodes by edge weight | Use PQ to order nodes by distance from source. |
Greedily in this case means that every step of the algorithm, we consider the best decision that we can make with the current information. Greedy algorithms can solve optimisation problems. Both, shortest path and MST are optimisation (minimisation, in particular) problems.
## Kruskal’s Algorithm
Also a greedy algorithm - it adds the lowest weight edges to the MST. Skip the edges that connect 2 nodes already connected by a blue edge since otherwise it would form a cycle (and this edge in fact, would have the maximum weight in the cycle since you are looking at edges in increasing order of weight).
1. Sort edges by weight from smallest to biggest.
2. Consider edges in ascending order:
1. If both endpoints are already in the tree, skip this edge (colour it red) (perform a `Find` operation)
2. Otherwise, join the two nodes with a blue edge (colour it blue) (perform a `Union` operation)
We can use a Union-Find data structure to keep track of which nodes are in the same blue tree.
### Pseudocode
