Graph Algorithms the Fun Way Powerful Algorithms Decoded, Not Oversimplified

by Kubica, Jeremy

• ISBN13: 9781718503861
• ISBN10: 1718503865
• eBook ISBN(s): 9781718503878
• Format: Paperback
• Copyright: 2024-11-19
• Publisher: No Starch Press

Summary

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.

Graph Algorithms the Fun Way offers a refreshing approach to complex concepts by blending humor, imaginative examples, and practical Python implementations to reveal the power and versatility of graph based problem-solving in the real world. Through clear diagrams, engaging examples, and Python code, you’ll build a solid foundation for addressing graph problems in your own projects.

Explore a rich landscape of cleverly constructed scenarios where:

• Hedge mazes illuminate depth-first search
• Urban explorations demonstrate breadth-first search
• Intricate labyrinths reveal bridges and articulation points
• Strategic planning illustrates bipartite matching

From fundamental graph structures to advanced topics, you will:

• Implement powerful algorithms, including Dijkstra’s, A*, and Floyd-Warshall
• Tackle puzzles and optimize pathfinding with newfound confidence
• Uncover real-world applications in social networks  and transportation systems
• Develop robust intuition for when and why to apply specific graph techniques

Delve into topological sorting, minimum spanning trees, strongly connected components, and random walks. Confront challenges like graph coloring and the traveling salesperson problem.

Prepare to view the world through the lens of graphs—where connections reveal insights and algorithms unlock new possibilities.

Author Biography

Jeremy Kubica is an engineering director with a BS in computer science from Cornell University and a PhD in robotics from Carnegie Mellon University where his work focused on creating algorithms to detect killer asteroids. He is the author of The CS Detective and Data Structures the Fun Way (both from No Starch Press).

Table of Contents

Part 1: Graph Basics
   Chapter 1: Representing Graphs
   Chapter 2: Neighbors and Neighborhoods
   Chapter 3: Paths Through Graphs

Part 2: 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 Searches

Part 3: 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: Markov Systems

Part 4: Max-Flow and Bipartite Matching
   Chapter 14: Max-Flow Algorithms
   Chapter 15: Bipartite Graphs and Bipartite Matching

Part 5: 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 Data Structures