Today let's get more practice working with graphs. We'll implement a few graph algorithms together, and get familiar with a few new patterns for writing recursive graph functions. Super cool!
As a warm-up, let's compute the maximum value of a graph containing integer values. First, let's do this using graph traversal:
Next, let's try a different approach that computes the maximum as it traverses the graph.
Next let's do something a bit trickier. We'll write a method to determine whether a graph contains a cycle, meaning a path between a node and itself where each edge is only used at most once.
First, let's examine what we mean by a cycle using a diagram, and discuss how the recursion needs to proceed.
Next, let's implement our recursive method! We'll test it on four kinds of undirected graphs—circular graphs that contain cycles; and linear, cross-shaped, and tree-like graphs that do not.