# Graph

Graph algorithms are quite common and usually fall under the following algorithms. You will usually be required to modify these algorithms to fit the problem but it's good to know the fundamentals

## Time complexities

Algorithm | Time Complexity | Space Complexity | Remarks |
---|---|---|---|

BFS | $O(E + V)$ | $O(V)$ | |

DFS | $O(E + V)$ | $O(V)$ | Space accounting for stack frames used in recursion |

Topological Sorting | $O(E + V)$ | $O(V)$ for storing the edges and frontier | Note that when iterating over every node, we only decrease the edges at most $O(E)$ times |

Dijkstra | $O((V + E) \log V)$ | $O(E)$ for priority queue | |

Bellman-Ford | $O(EV)$ | For $O(V)$ vertices, we iterate through all $O(E)$ edges and compute the SSP | |

Prim’s Algorithm | $O(E \log V)$ or $O(V^2)$ | Time complexity achieved if using Fibonacci heap AND iterating over the entire priority queue | |

Kruskal’s Algorithm | $O(E \log V)$ |

## Frequency in interviews

Common: BFS, DFS

Uncommon: Topological sort, Dijkstra

Almost never: Bellman-Ford, Floyd Warshall, Prim’s, Kruskal’s

## BFS

Trees do not require a `visited`

set since there is only 1 path between nodes (property of trees)

## DFS

## Topological sorting

Used for job scheduling a sequence of jobs or tasks that have dependencies on other jobs/tasks

Jobs represent vertices and edges from X to Y (directed) if X depends on Y

## Dijkstra

Only works with non-negative edge weights. If the edges have a negative weight, use Bellman-Ford instead

### Optimizations

If target node known, once we process target node (i.e. pop is target node), we can early return

## Bellman-Ford

Works with negative weight edges but does not work if there are negative weight **cycles. **For those cases, we can detect that a cycle exists but cannot do anything about it

Loop for `v - 1`

times and for each loop, relax all edges

To detect negative weight edges, check if the cost of the same node decreases twice

### Optimizations

Track if any costs decreased, if none did, then we can early terminate since that means we found the lowest possible cost for all edges

## Prim’s algorithm

Finds the Minimum Spanning Tree of a graph and is easier to implement than Kruskal’s algorithm

The general intuition for Prim's algorithm is as such:
Given a node `i`

, go through all connected points and add the edge weights to a min heap `(weight, other point)`

. For every element in the min heap, if visited before, discard, otherwise, use the topmost point’s edge. Iterate at most `N - 1`

times as that is the maximum number of edges of a tree.

For this specific implementation, the time complexity is $O(EV \log V)$

### Fully-connected graphs

For fully connected graphs, instead of using a heap, use a `min_d`

array, tracking the minimum weight to reach each point in the graph.

The general intuition for this variation is:
For each node `node`

, we update the edge weight to all connected points. Then the point we choose to use would be the one that has not yet been visited and has the shortest edge weight.

Once a `node`

is visited, set the weight to reach to be `inf`

so no extra `visited`

is needed

## Kruskal’s algorithm

Use Union-Find Disjoint Set (UFDS) to determine which edges are redundant and use a min heap to store the weights of the edges. Redundant edges are those whose points already exist in the same set (meaning that there exists another path between these two points in the MST so far).

This implementation has a time complexity of $O(E \log E + E \log V)$ because we’re not sorting the entire graph at once. If we sorted, the time complexity would be similar but $O(\log E) = O(\log V^2) = O(2 \log V) = O(\log V)$ dominates the term so we take that instead

Last updated