#Graph - 0. Introduction

#Questions to Ask

Before any graph problems, ask yourself the following 4 questions:

  1. Directed or Undirected?
  2. Weighted or Unweighted?
  3. Sparse graph or Dense graph?
  4. Adjacency Matrix or Adjacency List?

#Graph Theory Problems with Cheat Sheet

  1. Search
  2. Topological Sort
  3. Cycle Detection
  4. Shortest Path Problem
    • Single Source Shortest Path Problem (SSSP)
      • Topological Sort (DAG)
      • Dijkstra (without negative edge)
        • Lazy Implementation
        • Eager Implementation with IndexHeap
      • Bellman-Ford (without negative cycle)
    • All Sources Shortest Path Problem
      • Floyd-Warshall
    • Longest Path Problem
  5. Connectivity
    • Union-Find
    • Strongly Connected Component
      • Tarjan’s Algorithm
      • Kosaraju’s Algorithm
    • Bridges (Cut Edges)
    • Articulation Points (Cut Vertex)
  6. Eulerian Path / Eulerian Cycle
  7. Hamiltonian Path / Hamiltonian Cycle
  8. Minimum Spanning Tree
    • Prim’s Algorithm
      • Lazy implementation
      • Eager implementation with IndexHeap
    • Kruskal’s Algorithm
  9. Traveling Salesman Problem
  10. Network Flow Problem
    • Ford-Fulkerson
    • Edmonds-Karp
    • Capacity Scaling
    • Dinic Algorithm
  11. Bipartite Problem
    • Maximum Cardinality Bipartite Matching (MCBM)

#Reference

Apply to all Graph related posts

Comments

01/03/2020