Chapter 3

A graph is a connection of nodes and edges, which may be either directed or undirected; this can model a variety of complexes and relationships, especially networks (whether physical or notional); trees are graphs that do not contain cycles. A typical operation on a graph is traversal between nodes along edges, and more generally the search for possible and optimal traversals.

Two common patterns to algorithms answering questions about graphs are breadth-first and depth-first search; the former is particularly useful for finding shortest roots and analyzing cycles, and the latter where backtracking is easier than arbitrary jumping; both are suited to finding connected components.

BFS and DFS have a relationship analogous to that between queues and stacks. Both can be implemented in two-parameter linear time, O(m+n) (assuming a graph represented as an adjacency list, the most efficient for most operations on sparse graphs). For BFS, at each layer, find all the not-yet discovered nodes connected to the layer under consideration, and make that layer the next. For DFS, when exploring a node, add all adjacent nodes to a stack, take nodes off the stack until reaching one not yet discovered, and explore it.

No insights.

I certainly see the stack aspect of DFS. But the relationship between BFS and queues eludes me, since both the layers and the nodes within each layer can be kept in lists or queues without algorithmic implications.

Reading this after going through the algorithms in class made it somewhat repetitious, but I cannot find fault. 7/10.