Skip to main content

Graph Algorithms

Essential algorithms for solving graph problems efficiently.

Shortest path (BFS, Dijkstra, Floyd-Warshall)​

  • BFS: Shortest path in unweighted graphs
  • Dijkstra's Algorithm: Shortest path in weighted graphs with non-negative weights
  • Floyd-Warshall: All-pairs shortest path algorithm
  • Bellman-Ford: Shortest path with negative weights

Minimum spanning tree (Kruskal, Prim)​

  • Kruskal's Algorithm: Greedy algorithm using union-find
  • Prim's Algorithm: Greedy algorithm starting from single vertex
  • Spanning Tree: Tree that connects all vertices
  • Minimum Weight: Spanning tree with minimum total weight

Topological sorting​

  • Definition: Linear ordering of vertices in directed acyclic graph
  • Kahn's Algorithm: Using in-degree counting
  • DFS-based: Using depth-first search
  • Applications: Task scheduling, dependency resolution

Cycle detection​

  • Undirected Graphs: Using DFS with parent tracking
  • Directed Graphs: Using DFS with color coding
  • Union-Find: For undirected graphs
  • Bellman-Ford: Detecting negative cycles

Strongly connected components​

  • Definition: Maximal set of vertices where each vertex is reachable from every other
  • Kosaraju's Algorithm: Two-pass DFS algorithm
  • Tarjan's Algorithm: Single-pass DFS algorithm
  • Applications: Social networks, web page analysis