> It’s a relatively simple algorithm, and useful for all
> sorts of things, including AI. There are three main ways I use it:
>
> * Mark all reachable nodes. This is useful if your map isn’t
> completely connected, and you want to know what’s reachable.
> That’s what we did above, with the visited field.
Throughout my career, my main two interests in software have been games and programming languages. Lately, I've been delighted how much overlap I see between them. Here, breadth-first search is both a bread-and-butter algorithm for pathfinding in games. It's also the exact same process you use in a mark-sweep garbage collector.
I used to not be that interested in many of the algorithms you learn in school. I thought they were a lot of CS navel gazing and rarely useful outside of publishing papers. I was more into software architecture at a high level and concrete APIs and algorithms that actually put interesting stuff on screen.
But, at least when it comes to graphs, over the past several years, I've been truly astonished at how many real-world programs I've had to write that have a core component that is best expressed as a graph and then solved using one of the well-known graph traversal algorithms.
I've done a version resolver for a package manager, a data processing pipeline, a roguelike, a couple of garbage collectors, and other stuff I'm forgetting, and they all use graphs. DFS, BFS, topological sorting, and transitive closures are my trusty secret weapons.
If you are interested in pathfinding and these kind of problems, I suggest to check out http://www.pathery.com/ - NP complete K-Most-Vital-Node problem.
I used to not be that interested in many of the algorithms you learn in school. I thought they were a lot of CS navel gazing and rarely useful outside of publishing papers. I was more into software architecture at a high level and concrete APIs and algorithms that actually put interesting stuff on screen.
But, at least when it comes to graphs, over the past several years, I've been truly astonished at how many real-world programs I've had to write that have a core component that is best expressed as a graph and then solved using one of the well-known graph traversal algorithms.
I've done a version resolver for a package manager, a data processing pipeline, a roguelike, a couple of garbage collectors, and other stuff I'm forgetting, and they all use graphs. DFS, BFS, topological sorting, and transitive closures are my trusty secret weapons.