Graphs

Quick comparison

Which one to pick?

flowchart TD
  A{"What do you need?"} -->|"visit everything"| T{"Need shortest paths in edges?"}
  T -->|yes| BFS["BFS"]
  T -->|no| DFS["DFS"]
  A -->|"shortest weighted paths"| S{"From one source or all pairs?"}
  S -->|"all pairs"| FW["Floyd-Warshall"]
  S -->|"one source"| N{"Any negative edge?"}
  N -->|no| DJ["Dijkstra"]
  N -->|yes| BF["Bellman-Ford"]
  A -->|"cheapest network connecting all"| M{"Dense graph?"}
  M -->|yes| PR["Prim"]
  M -->|no| KR["Kruskal"]
  A -->|"order tasks with dependencies"| TS["Topological sort"]
  A -->|"is there a loop?"| CD["Cycle detection"]
  A -->|"which items are connected?"| UF["Union-Find"]
      

Key points

• Adjacency lists make traversals $O(V + E)$ because they store only real edges.
• BFS gives shortest unweighted paths because it reaches vertices layer by layer.
• Dijkstra needs non-negative weights because it declares distances final as soon as they are the smallest.
• Bellman-Ford and Floyd-Warshall allow negative edges because they never finalise a distance early.
• Kruskal and Prim are both greedy because the cheapest edge across any cut is always safe for a minimum spanning tree.

External resources

• VisuAlgo: Graph traversal: BFS, DFS and topological sort.
• VisuAlgo: Shortest paths: Dijkstra and Bellman-Ford side by side.
• VisuAlgo: Minimum spanning tree: Kruskal and Prim on the same graph.
• MIT OCW 6.006: lectures on BFS, DFS and shortest paths.

Videos

• YouTube search: graph algorithms for beginners: an overview of the whole family.