Graph traversal with Loom
Traversal algorithms concern themselves with the ways of exploring the graph in a systematic way. Given the huge variety of phenomena that can be modeled with graphs, such algorithms could have a huge variety of uses.
The algorithms we'll consider in the next few sections concern some of the most common tasks such as:
- Determining whether a path exists that traces each edge exactly once
- Determining the shortest path between two vertices
- Determining the shortest tree that connects all the vertices
If the graph in question represented the road network covered by a delivery driver's round, the vertices could represent intersections. Finding a path that traces each edge exactly once would be the way a delivery driver would travel all the roads without doubling back or passing the same addresses twice. The shortest path between the two vertices would be the most efficient way to navigate from one address to the next delivery. Finally, the shortest tree connecting...
