Graph Algorithm Application Reference

Direct BFS Applications

• Bipartite Check

Direct DFS Applications

• Strongly Connected Components
  • Kosaraju’s Algortihm
  • Directed Acyclic Graph
    • Topological Sort

Minimum Spanning Tree

• Kruskal’s Algorithm
• Prim’s Algorithm
• Borůvka’s Algorithm

Single Source Shortest Path Algorithm

• Dijkstra’s algorithm
• Bellman-Ford

All Sources Shortest Path

• Floyd-Warshall

Stable Matching

• Gale-Shapley Algorithm

Max-Flow

• Ford-Fulkerson
  • Maximum Bipartite Matching