Graph - cocoder39/coco39_LC GitHub Wiki

Graph problem breakdown

• directed vs undirected
• weighted vs unweighted
• cyclic vs acyclic

Approach

• unweighted graph -> BFS
• weighted graph -> Dijkstra
• negative weight and negative weighted cycles -> Bellman Ford

Topolog

• Topological sorting
  • 269. Alien Dictionary
  • 207. Course Schedule
  • 210. Course Schedule II
• 1153. String Transforms Into Another String

Dijkstra's (wiki pq implementation)

• 743. Network Delay Time
• 1631. Path With Minimum Effort
• 1514. Path with Maximum Probability
• 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance
• 787. Cheapest Flights Within K Stops (limited node count shorted path) (bellman-ford) (dp)
• 505. The Maze II
• 499. The Maze III
• 542. 01 Matrix

multiple sources bfs

• 1162. As Far from Land as Possible

dfs/bfs

• Bipartite
  • 785. Is Graph Bipartite?
  • 886. Possible Bipartition
• can also be solved by union find
  • 261. Graph Valid Tree
  • 399. Evaluate Division
  • 323. Number of Connected Components in an Undirected Graph
• cycle
  • 1192. Critical Connections in a Network
  • Cycle detection in directed graph (can be applied to solve LC 207)
• 797. All Paths From Source to Target
• 133. Clone Graph
• 959. Regions Cut By Slashes (upscale grid to convert the problem to number of islands)
• 863. All Nodes Distance K in Binary Tree