Learning Algorithms

Chapter 7. Graphs: Only Connect!

In this chapter, you will learn:

• The stack abstract data type.

• The indexed min priority queue data type, which is the final data type included in this book.

• How to model a graph using nodes and edges. In a directed graph, the edges have an orientation. In a weighted graph, edges have an associated numeric value.

• How Depth First Search uses a stack to organize searching in a graph.

• How Breadth First Search uses a queue to search through a graph. If a path exists between a source node and a target node, Breadth First Search will return the shortest path that exists.

• How to detect whether a directed graph contains a cycle: a sequence of edges starting from, and ending with, a specific node.

• How to use Topological Sort in a directed graph to produce a linear ordering of nodes compatible with all dependencies in the directed graph.

• How to determine the shortest accumulated path in a weighted graph from one node to all other nodes.

• How to determine the shortest accumulated path in a weighted graph between any two nodes.

Graphs Efficiently Store Useful Information

I’ve covered algorithms for solving common problems in information systems regarding storing and processing data. These algorithms can solve countless real-world problems if only we could properly model these problems. Here are three such problems that I will solve by using graphs:

• A maze consists of rooms with doorways leading to other rooms. Find the shortest path ...