Review: Graph Problems Posted on January 22, 2018April 13, 2020 by braindenny 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 Post Views: 7