Graph

Graph Concepts | Graphs Tricks

leetcode study plan

• DFS | DFS Template I  |  DFS Template II | BFS | BFS Template
• Union Find | Quick Find | Quick Union | Union By Rank |
• Path Compression | Path Compression and Union by Rank

Islands/Matrix/Flood Fill:

• Number of Islands * | Number of Islands II | Max Area of Island ^ |
• Count Sub Islands | Battleships in a Board | Island Perimeter |
• Number of Distinct Islands | Number of Distinct Islands II
• Pacific Atlantic Water Flow *
• Flood Fill:
  • Flood Fill | Surrounded Regions ^ |
  • Number of Closed Islands | Number of Enclaves 

BFS:

• Walls and Gates ^ | Rotting Oranges ^ | Word Ladder ^ | Word Ladder II |
• 01 Matrix | As Far from Land as Possible | Shortest Cell Path |
• Shortest Path in Binary Matrix | N-ary Tree Level Order Traversal |
• Treasure Island | Is Possible | Open the Lock | Word Break *!
• Cut Off Trees for Golf Event | Shortest Path with Alternating Colors
• Shortest paths to every node in undirected unweighted graph

Other:  Clone Graph * | Graph Valid Tree * | Reconstruct Itinerary ^

Disjoint Set:

• Number of Connected Components in an Undirected Graph * |
• Redundant Connection ^ | Redundant Connection II |
• Number of Provinces | Friend Circles | Evaluate Division 
• The Earliest Moment When Everyone Become Friends |
• Smallest String With Swaps

Cycle:

• Undirected Graph Cycle | Directed Graph Cycle |
• All Paths from Source Lead to Destination

Bipartite:

• Is Graph Bipartite? | Possible Bipartition

Topological Sort:

• Reverse DFS Postorder | Kahn’s Algorithm (BFS) |
• Course Schedule * | Course Schedule II ^ |  Alien Dictionary * |
• Longest Increasing Path in a Matrix ^! | Find Eventual Safe States 
• Tasks Scheduling | Tasks Scheduling Order |  All Tasks Scheduling Orders |
• Sequence Reconstruction | Minimum Height Trees | Parallel Courses

Minimum Spanning Tree:

• Kruskal’s Minimum Spanning Tree | Prim’s Minimum Spanning Tree |
• Min Cost to Connect All Points ^ | Connecting Cities With Minimum Cost |
• Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree |
• Optimize Water Distribution in a Village |
• Checking Existence of Edge Length Limited Paths II

Single Source Shortest Path:

• Dijkstra’s Algorithm (Lazy & Eager & D-ary Heap) | Bellman−Ford Algorithm |
• Shortest Path in DAG | Longest Path in DAG (WilliamFiset)
• Network Delay Time ^ | Cheapest Flights Within K Stops ^ |
• Swim in Rising Water ^ | Course Schedule IV | Path With Minimum Effort
• Find the City With the Smallest Number of Neighbors at a Threshold Distance

Graph + Memoization:

• Longest Increasing Path in a Matrix ^! |

A* Search:  Shortest Path in Binary Matrix | Cut Off Trees for Golf Event

Strongly Connected Components

General : 

• Keys and Rooms | Employee Importance |
• Time Needed to Inform All Employees
• Find if Path Exists in Graph | All Paths From Source to Target
• Kill Process | Find the Town Judge
• Web Crawler | Web Crawler Multithreaded
• Route Between Nodes | Build Order | Word Chaining
• Find the Celebrity | Best Meeting Point
• REORDER ROUTES TO MAKE ALL PATHS LEAD TO THE CITY ZERO
• Snakes and Ladders | Open the Lock | Shortest Bridge