Digital Library

Graph Algorithms the Fun Way (Jeremy Kubica)（Z-Library）

Share E-Book
Read Without Registration

Graph Algorithms the Fun Way (Jeremy Kubica)（Z-Library）

Author

Rating No ratings yet

Log in to rate

Programming
Language English

Powerful Algorithms Decoded, Not Oversimplified 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.

Format PDF
Size 45.8 MB
8
Views
(First 20 pages)

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

Page 1
(This page has no text content)
Page 2
CONTENTS IN DETAIL TITLE PAGE COPYRIGHT DEDICATION ABOUT THE AUTHOR AND TECHNICAL REVIEWER ACKNOWLEDGMENTS INTRODUCTION Who Is This Book For? Analogies and Examples Language and Coding Conventions Terminology and Definitions How to Use This Book PART I: GRAPH BASICS 1 REPRESENTING GRAPHS Graph Structure Weighted Edges Directed Edges Edges with Both Weight and Direction The Adjacency List Representation Edges Nodes The Graph Class The Adjacency Matrix Representation Why This Matters 2
Page 3
NEIGHBORS AND NEIGHBORHOODS Neighbors in Undirected Graphs Neighbors in Directed Graphs Self-Loops Degree Clustering Coefficient Computing the Average Clustering Coefficient Handling Limitations Generating Neighborhood Subgraphs The Code An Example Why This Matters 3 PATHS THROUGH GRAPHS Paths Path Representation Lists of Nodes Lists of Edges Lists of Previous Nodes Calculating Path Cost Reachability Why This Matters PART II: SEARCH AND SHORTEST PATHS 4 DEPTH-FIRST SEARCH Use Cases Exploring a Hedge Maze Learning a New Subject Checking Reachability Recursive Depth-First Search The Code An Example Depth-First Search with a Stack The Code An Example Finding Connected Components The Code An Example Depth-First Search Trees and Forests Iterative Deepening
Page 4
Why This Matters 5 BREADTH-FIRST SEARCH Use Cases Learning New Topics Exploring a New City The Breadth-First Search Algorithm The Code An Example Finding Shortest Paths Simple Path Planning Constructing a Graph from a Grid Adding Obstacles Running Breadth-First Search Why This Matters 6 SOLVING PUZZLES State Spaces and Graphs The Tower of Hanoi River-Crossing Puzzles Slider Puzzles Constructing a Graph with Search Representing the Puzzle’s States Generating the Graph Solving a Puzzle with Search Why This Matters 7 SHORTEST PATHS Lowest-Cost Paths Dijkstra’s Algorithm The Code An Example Disconnected Graphs Negative Edge Weights Bellman-Ford Algorithm The Code An Example All-Pairs Shortest Paths The Floyd-Warshall Algorithm The Code An Example Computing Graph Diameter Why This Matters
Page 5
8 HEURISTIC-GUIDED SEARCHES Choosing Appropriate Heuristics Euclidean Distance Admissible Heuristics Heuristic Design Challenges Greedy Best-First Search The Code An Example A* Search The Code An Example Why A* Finds the Optimal Path Applying A* to Puzzles Searching Unknown Graphs The Code An Example Why This Matters PART III: CONNECTIVITY AND ORDERING 9 TOPOLOGICAL SORT How Topological Sort Algorithms Work Use Cases Code Dependencies Task Lists Teaching and Learning Kahn’s Algorithm The Code An Example Depth-First Search The Code An Example Order of Starting Nodes Detecting Cycles Reordering Lists Why This Matters 10 MINIMUM SPANNING TREES The Structure of Minimum Spanning Trees
Page 6
Use Cases Physical Networks Social Networks Prim’s Algorithm The Code An Example Kruskal’s Algorithm Union-Find The Code An Example Maze Generation Representing Grid-Based Mazes Generating Mazes The Code An Example Single-Linkage Hierarchical Clustering The Code An Example Why This Matters 11 BRIDGES AND ARTICULATION POINTS Defining Bridges and Articulation Points Use Cases Designing Resilient Networks Preventing the Spread of Diseases Designing Magical Labyrinths A Bridge-Finding Algorithm The Code An Example An Algorithm for Finding Articulation Points The Code An Example Why This Matters 12 STRONGLY CONNECTED COMPONENTS Defining Strongly Connected Components Determining Which Nodes Are Mutually Reachable Determining Whether Nodes Are Strongly Connected Use Cases Modeling Computer Program States Understanding a Gossip Network Planning a Travel Network Kosaraju-Sharir’s Algorithm Transposed Graphs
Page 7
The Code An Example Why This Matters 13 RANDOM WALKS Introducing Random Walks Probabilities in Random Walks Random Walks as Markov Chains Transition Probabilities Matrix Formulation Use Cases Information Chains in Social Networks Exploration Games of Chance Simulating Random Walks Statistical Measures Hitting and Absorption Time Stationary Distribution Luck-Based Board Games Transition Probabilities Maximum Likelihood Estimations A Transition Matrix Estimation Algorithm Limitations of Working with Finite Data Random Starting Nodes Choosing a Random Starting Node Estimating the Probability Distribution for Starting Nodes Why This Matters PART IV: MAX FLOW AND BIPARTITE MATCHING 14 MAX-FLOW ALGORITHMS The Maximum-Flow Problem Use Cases Physical Pipelines Transportation Networks Communication Networks Extending the Data Structures Edges with Capacity Residual Graphs The Ford-Fulkerson Algorithm Defining Augmenting Paths
Page 8
Finding an Augmenting Path Updating a Path’s Capacity Putting It All Together An Example The Edmonds-Karp Algorithm The Code An Example Modeling Increasingly Complex Real-World Situations Multiple Sources Multiple Sinks Anti-parallel Edges Why This Matters 15 BIPARTITE GRAPH MATCHING Matching Bipartite Graphs Bipartite Labeling The Code An Example Use Cases Scheduling Jobs Assigning Office Space Planning Quest Battles Exhaustive Algorithms Matching Data Exhaustive Scoring The Code An Example Solving the Maximum-Cardinality Bipartite Problem The Code An Example Why This Matters PART V: HARD GRAPH PROBLEMS 16 GRAPH COLORING The Graph-Coloring Problem Use Cases Coloring Maps Organizing Seating Arrangements Assigning Parking Spaces Planning Magical Labyrinths Graph-Coloring Algorithms
Page 9
Exhaustive Search Backtracking Search Greedy Search Node Removal Why This Matters 17 CLIQUES, INDEPENDENT SETS, AND VERTEX COVERS Backtracking Search for Sets of Nodes Cliques Use Cases Greedy Search Backtracking Search Independent Sets Use Cases Greedy Search Backtracking Search Vertex Cover Use Cases Greedy Search Backtracking Search Randomized Algorithms Basic Randomized Search Weighted Randomized Search Why This Matters 18 TOURS THROUGH GRAPHS Hamiltonian Paths and Cycles Validating Hamiltonian Paths Finding Hamiltonian Paths with Depth-First Search The Traveling Salesperson Problem Depth-First Search The Code An Example Eulerian Paths and Cycles Validating Eulerian Paths Finding Eulerian Cycles with Hierholzer’s Algorithm Why This Matters CONCLUSION A CONSTRUCTING GRAPHS Constructing Graphs from Edges Inserting Edges from a List
Page 10
Loading Edge Lists from Files Saving Edge Lists to Files Inserting Nodes by Name Co-occurrences Spatial Points Preconditions B MODIFIABLE PRIORITY QUEUES Heaps Heap Items Array-Based Storage Element Swaps Modifiable Priority Queue The Data Structure Defining Helper Functions Adding Items Removing Items Modifying Priorities Peek Functions C UNION-FIND The Union-Find Data Structure UnionFind UnionFindNode UnionFind Class INDEX
Page 11
GRAPH ALGORITHMS THE FUN WAY Powerful Algorithms Decoded, Not Oversimplified by Jeremy Kubica San Francisco
Page 12
GRAPH ALGORITHMS THE FUN WAY. Copyright © 2025 by Jeremy Kubica. All rights reserved. No part of this work may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or by any information storage or retrieval system, without the prior written permission of the copyright owner and the publisher. First printing 28 27 26 25 24    1 2 3 4 5 ISBN-13: 978-1-7185-0386-1 (print) ISBN-13: 978-1-7185-0387-8 (ebook) Published by No Starch Press®, Inc. 245 8th Street, San Francisco, CA 94103 phone: +1.415.863.9900 www.nostarch.com; info@nostarch.com Publisher: William Pollock Managing Editor: Jill Franklin Production Manager: Sabrina Plomitallo-González Production Editor: Sydney Cromwell Developmental Editor: Abigail Schott-Rosenfield Cover Illustrator: James L. Barry Interior Design: Octopod Studios Technical Reviewer: Daniel Zingaro Copyeditor: Céline Parent Proofreader: Debbie Greenberg Library of Congress Cataloging-in-Publication Data Name: Kubica, Jeremy, author. Title: Graph algorithms the fun way / by Jeremy Kubica. Description: San Francisco, CA : No Starch Press, [2025] | Includes index. Identifiers: LCCN 2024017136 (print) | LCCN 2024017137 (ebook) | ISBN 9781718503861 (print) | ISBN 9781718503878 (ebook) Subjects: LCSH: Graph algorithms. | Python (Computer program language) Classification: LCC QA166.245 .K83 2025 (print) | LCC QA166.245 (ebook) | DDC 518/.1 —dc23/eng/20240628 LC record available at https://lccn.loc.gov/2024017136 LC ebook record available at https://lccn.loc.gov/2024017137 For customer service inquiries, please contact info@nostarch.com. For information on distribution, bulk sales, corporate sales, or translations: sales@nostarch.com. For permission to translate this work: rights@nostarch.com. To report counterfeit copies or piracy: counterfeit@nostarch.com. No Starch Press and the No Starch Press iron logo are registered trademarks of No Starch Press, Inc. Other product and company names mentioned herein may be the trademarks of their respective owners. Rather than use a trademark
Page 13
symbol with every occurrence of a trademarked name, we are using the names only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark. The information in this book is distributed on an “As Is” basis, without warranty. While every precaution has been taken in the preparation of this work, neither the author nor No Starch Press, Inc. shall have any liability to any person or entity with respect to any loss or damage caused or alleged to be caused directly or indirectly by the information contained in it. [E]
Page 14
To Nathan and Julie
Page 15
About the Author Jeremy Kubica is an engineering director. He received a PhD in robotics from Carnegie Mellon University and a BS in computer science from Cornell University. He spent his graduate school years creating algorithms to detect killer asteroids (actually stopping them was, of course, left as “future work”). He is the author of multiple books designed to introduce people to computer science, including Computational Fairy Tales (2012), The CS Detective (No Starch Press, 2016), and Data Structures the Fun Way (No Starch Press, 2022). About the Technical Reviewer Dr. Daniel Zingaro is an award-winning associate professor of computer science at the University of Toronto Mississauga. He is well known for his uniquely interactive approach to teaching and internationally recognized for his expertise in active learning. He is the author of Algorithmic Thinking, 2nd edition (No Starch Press, 2024), and Learn to Code by Solving Problems (No Starch Press, 2021), and co-author of Learn AI-Assisted Python Programming (2023) and Start Competitive Programming! (2024).
Page 16
ACKNOWLEDGMENTS I would like to start by thanking the whole team at No Starch Press who helped make this book a reality: Bill Pollock, Jill Franklin, Abigail Schott-Rosenfield, Sabrina Plomitallo-González, Sydney Cromwell, Céline Parent, and Debbie Greenberg. A particular thank-you to my amazing editor, Abigail Schott-Rosenfield, for their excellent help, guidance, and suggestions throughout the process. I would also like to thank Carlos Bueno, who originally pointed me to the team at No Starch. Thank you to Daniel Zingaro for his thorough and insightful technical review. His work was vital in improving both the accuracy and understandability of the material. A tremendous thanks goes out to all the people who provided early thoughts and comments: Andrew Moore, Theodore Kim, Eleanor Rieffel, and Justin Carlson. Their suggestions helped guide my approach and the direction of the book. I am grateful for the many great teachers, mentors, and colleagues who introduced me to the fascinating world of graph algorithms. Thank you to my parents for their support and encouragement. Thank you to Regan, Nathan, and Julie for their support, encouragement, and patience.
Page 17
INTRODUCTION This book is an introduction to graphs and their algorithms for programmers who want to understand and apply them. Graphs are a type of data structure used throughout mathematics, computer science, and numerous other fields to model and solve a wide range of real-world problems. The structure of a graph allows us to represent connections or associations between items. Understanding this structure is critical to harnessing the power of graphs and using them efficiently. Graph Algorithms the Fun Way grew out of the chapter on graphs in my previous book, Data Structures the Fun Way (No Starch Press, 2022), where I wrote, “We could devote an entire book to this single vastly impactful data structure.” Yet this book still only scratches the surface of the exciting and powerful world of graph algorithms, an area of study with a long history and ongoing research. A comprehensive coverage of all graph techniques and their
Page 18
relative advantages would require numerous volumes and be out of date the moment it was printed. Instead, this book is meant to serve as a foundation for people approaching this exciting field for the first time. The book starts by introducing the components of graphs, then dives into exploring a variety of graph algorithms and how they apply to real-world problems. It is more than a cookbook of common algorithms. Its goal is to help readers understand the ideas behind the algorithms and build the intuitions to adapt the concepts covered here to techniques beyond this book.
Page 19
Who Is This Book For? This book is for programmers who want to learn more about graphs, graph algorithms, and the computational thinking behind such techniques. I assume no prior knowledge of graphs or graph algorithms. However, readers should have the kind of basic familiarity with Python that can be expected after an introductory course, book, or boot camp. They should be familiar with fundamental Python programming concepts, including basic data structures such as lists and dictionaries. I hope this book will be useful to a wide range of audiences, not just programmers learning graph algorithms for the first time. The examples and metaphors used throughout the book are designed to provide an alternative way to view the topics from their standard mathematical definitions. Advanced students and experienced computer scientists may find a new perspective to understand particularly difficult or tricky topics. Analogies and Examples This book supplements formal descriptions and code with a range of real-world and absurd examples and analogies. The structure of graphs makes them perfect for illustrating algorithms with stories of adventurers searching labyrinths or planning vacations through unknown cities. The goal of these examples and analogies is twofold. First, they motivate the algorithms themselves and why we care about the problems they solve. Second, they provide an alternate approach to visualizing these problems that will help readers break free of technicalities and minutiae. Language and Coding Conventions I chose to present example code in Python due to the language’s wide use and readability. However, aficionados
Page 20
of other languages need not fear, as the concepts behind the code are language-agnostic. Graph algorithms have been implemented in a wide range of languages, and all code examples in this book can be adapted beyond Python. The code throughout the book uses common Python conventions. To make the code clearer, I use type hints, as in the following code block: def is_edge(self, from_node: int, to_node: int) -> bool: return self.get_edge(from_node, to_node) is not None The input arguments list the expected types, such as int, and the function definition describes the expected return type (bool). The code in this book uses multiple core Python libraries. Since functions throughout a file often use the same library, individual code snippets do not explicitly include the import statements. Users implementing the code will need to make sure to import the relevant libraries. Where ambiguous, I identify the needed libraries in the code’s text description. Standard Python libraries used in this book include: csv copy itertools math queue random typing (for Union) The typing library in particular is needed for a number of code snippets, in order to support type hints for functions with multiple return values.
The above is a preview of the first 20 pages. Register to read the complete e-book.

Recommended for You

Loading recommended books...
Failed to load, please try again later

Tip the Site

Scan the WeChat Pay or Alipay code to tip. No login required.

WeChat Pay
Alipay
← Back to List