Kotlin
Java

Graph Algorithms
Kotlin

Created By: Geoffrey Challen
/ Updated: 2021-11-21

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!

Graph Max Value

As a warm-up, let's compute the maximum value of a graph containing integer values. First, let's do this using graph traversal:

Implement graph max value by simply creating the set of nodes and then iterating over it.

Next, let's try a different approach that computes the maximum as it traverses the graph.

Implement graph max value by having the recursive method compute the max as it explores the graph, rather than just building the node set.

Graph Contains Cycle

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.

Show what it means for a graph to have a cycle, and motivate the idea of using a path list rather than a set. This video should be language agnostic!

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.

Show how to complete the homework problem above. Feel free to cover multiple approaches!

Solution Walkthrough

Show how to complete the homework problem above. Feel free to cover multiple approaches!

Solution Walkthrough