Read more
Enter the wonderful world of graph algorithms, where you’ll learn when and how to apply these highly useful data structures to solve a wide range of fascinating (and fantastical) computational problems.
This book provides a fun and accessible introduction to graph algorithms, commonly used to solve a wide range of computational and mathematical problems. Full of humorous analogies, detailed diagrams, and real-world examples using the Python programming language,
It starts with the structure of graphs, demonstrating the ways they can represent connections between nodes, such as the best route through a city or how rumors spread in a social network. Each subsequent chapter introduces new graph algorithms along with their underlying concepts and applications — from basic searches to more advanced methods of exploring graphs. You’ll have a blast solving brain-teasers including the 15-square puzzle, matching adopted pets with homes, calculating the maximum flow of a sewage network, traversing magical labyrinths, sorting recipe steps to craft the perfect cookies, and more. You’ll also learn how to:
Guided by the bestselling author of
List of contents
Introduction
Part I: Graph Basics
Chapter 1: Representing Graphs
Chapter 2: Neighbors and Neighborhoods
Chapter 3: Paths Through Graphs
Part II: Search and Shortest Paths
Chapter 4: Depth-First Search
Chapter 5: Breadth-First Search
Chapter 6: Solving Puzzles
Chapter 7: Shortest Paths
Chapter 8: Heuristic Guided Searches
Part III: Connectivity and Ordering
Chapter 9: Topological Sort
Chapter 10: Minimum Spanning Tree
Chapter 11: Bridges and Articulation Points
Chapter 12: Strongly Connected Components
Chapter 13: Random Walks
Part IV: Max-Flow and Bipartite Matching
Chapter 14: Max-Flow Algorithms
Chapter 15: Bipartite Graphs and Bipartite Matching
Part V: Hard Graph Problems
Chapter 16: Graph Coloring
Chapter 17: Independent Sets and Cliques
Chapter 18: Tours Through Graphs
Appendix A: Constructing Graphs
Appendix B: Priority Queue
Appendix C: Union-Find
Conclusion
