[Graph Algo Series 2] Intermediate Knowledge

Often asked question type includes but not limits to:

1. Acyclic / cyclic
2. Connectivity, degrees of separation, reachability (digraph)
3. Bipartite / Colorability (can the vertices of a given graph be assigned multiple colors in such a way that no edge connects vertices of the same color)
4. Tree (including but not limited to Binary Search Tree (BST), Minimum Spanning Tree (MST), pre/in/post-order)…

Often used data structure:

1. Adjacency list. V by V array
2. An array of edges
3. An array of adjacency lists (for sparse graph): vertex-indexed array of lists of the vertices adjacent to each other.
4. Node class. This representation is primarily used in Tree problems. The Node class has ‘next’ and ‘val’ as class field.

Note that if it is a symbol graph (vertex names are strings), we can have a function int index(String key), implement it with a symbol table (Map<String, Integer>) to map the vertices.

Common Algorithms:

1. DFS:

• Time complexity: O(V+E). Marks all vertices connected to a given source in time proportional to the sum of their (out)degrees (2E if connected).
• Implementation: LIFO stack or recursion
• Example usage: path detection (are two vertices connected?), cycle detection, colorability.

2. BFS:

• Time complexity: O(V+E). Marks all vertices connected to a given source in time proportional to the sum of their (out)degrees (2E if connected).
• Implementation: FIFO queue
• Example usage: shortest path detection

3. Union-find

• Example usage: when determining connectivity is the only task + large number of queries intermixed with edge insertions.
• Advantages: no need to create a full graph representation.

Reference: The textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne