Graph related questions mainly focus on depth first search and breath first search.

**Basic Abstractions**

Name | Summary |
---|---|

bfs and dfs relationship | LeetCode: Word Ladder II |

Common graph representations | Adjacent matrix, adjacent list, hashmap of hashmaps |

From BFS to Bidirectional BFS | Half of the time. LeetCode: Word Ladder |

3 cases: state is invalid/visited/unexamined | LeetCode: Word Ladder |

Bridge in graph | Bridge is an edge, when removed, will disconnect the graph |

Duplicate edge | |

Cycle in undirected graphs | |

Cycle in DAG | LeetCode: Redundant Connection II |

For matrix graph problems: rectangle vs square |

**Top 10 Graph Algorithm**

Num | Problem | Summary |
---|---|---|

1 | Dijkstra’s algorithm | Greedy. Shortest path for two nodes in a weighted grap. See #dijkstra |

2 | Bellman-Ford algorithm | Shortest path for two nodes in a weighted graph + negative edges. See #floyd |

3 | Floyd-Warshall algorithm | Find shortest paths in a weighted graph |

4 | Kruskal’s algorithm | Union find + Greedy. Minimum Spanning Tree(MST). |

5 | Prim’s algorithm | Greedy + Heap. Minimum Spanning Tree(MST). |

6 | Tarjan’s algorithm | Cut node |

7 | Cut edge | |

8 | Topological Sort | Node dependencies |

9 | #bipartite | Whether graph is a bipartite graph |

**Top Questions**

Num | Problem | Summary |
---|---|---|

1 | Graph Connectivity: Count islands in a 2D matrix | LeetCode: Number of Islands, LeetCode: Island Perimeter |

2 | Get the size of the largest island | LeetCode: Max Area of Island |

3 | Cycle detection in a directed graph | LeetCode: Redundant Connection II |

4 | Detect all cycles in a directed graph | LeetCode: Find Eventual Safe States |

5 | Whether a graph is a tree | LeetCode: Graph Valid Tree |

6 | Update a specific region | LeetCode: Flood Fill |

7 | Graph trasversal from boarders | Leetcode: Surrounded Regions |

8 | Number of Distinct Islands | LeetCode: Number of Distinct Islands |

9 | Mark levels | LeetCode: 01 Matrix |

10 | Diameter of a tree in graph theory | LeetCode: Tree Diameter |

11 | Duplicate edges | LeetCode: Reconstruct Itinerary |

12 | Find a certain node in a graph | LeetCode: Find the Celebrity |

13 | Graph with next steps by a trie | Leetcode: Word Search II |

14 | Coloring graph | LeetCode: Minesweeper |

15 | Find a certain path from source to destination in a graph | LeetCode: Path With Maximum Minimum Value |

16 | Find the shortest distance from point1 to point2 | LeetCode: Word Ladder, LeetCode: Sliding Puzzle |

17 | Find shortest distance in a weighted graph | LeetCode: Find the City With the Smallest Number of Neighbors |

18 | Find all minimum paths from point1 to point2 | LeetCode: Word Ladder II |

19 | All Paths from Source Lead to Destination | LeetCode: All Paths from Source Lead to Destination |

20 | Node connectivity problem for a sparse 2D matrix | LeetCode: Escape a Large Maze |

21 | Bricks Falling When Hit | LeetCode: Bricks Falling When Hit |

22 | Bridges in a connected graph – Tarjan’s algorithm | LeetCode: Critical Connections in a Network |

23 | Valid & Invalid moves | LeetCode: Alphabet Board Path |

24 | Move in different directions: 4 directions, 8 directions | LeetCode: Queens That Can Attack the King |

25 | String Transforms Into Another String | LeetCode: String Transforms Into Another String |

26 | Candidates are (i, j, r), instead of (i, j) | LeetCode: Shortest Path in a Grid with Obstacles Elimination |

27 | Clone Graph | Leetcode: Clone Graph |

28 | Array problem with hidden graph | LeetCode: Number of Squareful Arrays |

29 | Is Graph Bipartite | LeetCode: Is Graph Bipartite |

30 | Search an infinite graph | LeetCode: Escape a Large Maze |

31 | BFS with BFS | LeetCode: Minimum Moves to Move a Box to Their Target Location |