Wikipedia:Books/archive/Graph Algorithms
Introduction
- Graph theory
- Glossary of graph theory terms
- Undirected graph
- Directed graph
- Directed acyclic graphs
- Graph (abstract data type)
- Adjacency list
- Adjacency matrix
- Implicit graph
Graph exploration and vertex ordering
- Depth-first search
- Breadth-first search
- 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
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
- 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
- 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
Graph drawing and planar graphs
- Planar graph
- Dual graph
- Fáry's theorem
- Steinitz's theorem
- Planarity testing
- Left-right planarity test
- Graph drawing
- Force-directed graph drawing
- Layered graph drawing
- Upward planar drawing
- Graph embedding
- Sociogram
- Concept map
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
Graph decomposition and graph minors
Content Disclaimer
Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.
- The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
- There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
- It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
- Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
- Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.