Graph Algorithms
Introduction
- Königsberg problem
- Graph theory
- Glossary of graph theory terms
- Undirected graph
- Directed graph
- Directed acyclic graphs (DAG)
Graph Representations and Data Structures
Graph Exploration and Vertex Ordering
- Depth-first search (DFS)
- Breadth-first search (BFS)
- Lexicographic breadth-first search
- Iterative deepening depth-first search
- Topological sorting
- Application: Dependency Graphs
Connectivity of Undirected Graphs
- Connected components
- Edge connectivity
- Vertex connectivity
- Menger's theorems on edge and vertex connectivity
- Ear decomposition
- Algorithms for 2-edge-connected components
- Algorithms for 2-vertex-connected components
- Algorithms for 3-vertex-connected components
- Karger's algorithm
Connectivity of Directed Graphs
- Strongly connected components
- Tarjan's strongly connected components algorithm
- Path-based strong component algorithm
- Kosaraju's strongly connected components algorithm
- Reachability
- Transitive closure
- Transitive reduction
- Application: 2-satisfiability (2-SAT)
Planar Graphs and Graph Drawing
Planar Graphs
- Planar graph
- Dual graph
- Fáry's theorem
- Steinitz's theorem
- Planarity testing
- Left-right planarity test
Graph Drawing
- Graph drawing
- Force-directed graph drawing
- Layered graph drawing
- Upward planar drawing
- Graph embedding
- Sociogram
- Concept map
Shortest Paths
- Shortest path problem
- Dijkstra's algorithm for single-source shortest paths with positive edge lengths
- Bellman–Ford algorithm for single-source shortest paths allowing negative edge lengths
- Johnson's algorithm for all-pairs shortest paths in sparse graphs
- Floyd–Warshall algorithm for all-pairs shortest paths in dense graphs
- Suurballe's algorithm for two shortest disjoint paths
- Bidirectional search
- A* search algorithm
- Longest path problem
- Widest path problem
- Canadian traveller problem
- K shortest path routing
- Application: Centrality analysis of social networks
- Application: Schulze voting system
Minimum Spanning Trees
- Minimum spanning tree
- Borůvka's algorithm
- Kruskal's algorithm
- Prim's algorithm
- Edmonds's algorithm for directed minimum spanning trees
- Degree-constrained spanning tree
- Maximum-leaf spanning tree
- K-minimum spanning tree
- Capacitated minimum spanning tree
- Application: Single-linkage clustering
- Application: Maze generation
Cliques, Independent Sets, and Coloring
- Clique problem
- Bron–Kerbosch algorithm for listing all maximal cliques
- Independent set problem
- Maximal independent set
- Graph coloring
- Bipartite graph
- Greedy coloring
- Ramsey's theorem
- Application: Register allocation
Covering and Domination
Tours
- Eulerian path
- Hamiltonian path
- Hamiltonian path problem
- Travelling salesman problem
- Bottleneck traveling salesman problem
- Christofides' heuristic for the TSP
- Route inspection problem
Matching
- Matching
- Hopcroft–Karp algorithm for maximum matching in bipartite graphs
- Edmonds's algorithm for maximum matching in non-bipartite graphs
- Assignment problem
- Hungarian algorithm for the assignment problem
- FKT algorithm for counting matchings in planar graphs
- Stable marriage problem
- Stable roommates problem
- Permanent
- Computing the permanent
Network Flow
- Maximum flow problem
- Max-flow min-cut theorem
- Ford–Fulkerson algorithm for maximum flows
- Edmonds–Karp algorithm for maximum flows
- Dinic's algorithm for maximum flows
- Push–relabel maximum flow algorithm
- Closure problem
- Minimum-cost flow problem
Special Classes of Graphs
- Interval graph
- Chordal graph
- Perfect graph
- Intersection graph
- Unit disk graph
- Line graph
- Claw-free graph
- Median graph
Graph Isomorphism
- Graph isomorphism
- Graph isomorphism problem
- Graph canonization
- Subgraph isomorphism problem
- Color-coding
- Induced subgraph isomorphism problem
- Maximum common induced subgraph
- Maximum common edge subgraph