#### Return to Index

#### MP3: Restaurant View Revisited : `12/01/2021`

#### MP3: Restaurant Graphs and Hashing : `11/30/2021`

#### MP3: Practical Sorting : `11/29/2021`

#### Implementing a Map : `11/19/2021`

#### Hashing : `11/18/2021`

#### Binary Search : `11/17/2021`

#### MP2: Related Restaurants : `11/16/2021`

#### MP2: Restaurant Activity : `11/15/2021`

#### Quicksort : `11/12/2021`

#### Merge Sort : `11/11/2021`

#### Sorting Algorithms : `11/10/2021`

#### MP2: Client-Server Communication : `11/09/2021`

#### MP2: CSV to JSON : `11/08/2021`

#### Graph Algorithms : `11/05/2021`

#### Graphs : `11/04/2021`

#### Practice with Recursion : `11/03/2021`

#### MP1: Search and Callbacks : `11/02/2021`

#### MP1: Views and UI : `11/01/2021`

#### Trees and Recursion : `10/29/2021`

#### Trees : `10/28/2021`

#### Recursion : `10/27/2021`

#### MP1: Serialization and Searching : `10/26/2021`

#### MP1: Serialization and Sorting : `10/25/2021`

#### Lists Review and Performance : `10/22/2021`

#### Linked Lists : `10/21/2021`

#### Algorithms and Lists : `10/20/2021`

#### Continuing MP0 : `10/19/2021`

#### Getting Started with MP0 : `10/18/2021`

#### Lambda Expressions : `10/15/2021`

#### Anonymous Classes : `10/14/2021`

#### Practice with Interfaces : `10/13/2021`

#### Implementing Interfaces : `10/12/2021`

#### Using Interfaces : `10/11/2021`

#### Working with Exceptions : `10/08/2021`

#### Throwing Exceptions : `10/07/2021`

#### Catching Exceptions : `10/06/2021`

#### References and Polymorphism : `10/05/2021`

#### References : `10/04/2021`

#### Data Modeling 2 : `10/01/2021`

#### Equality and Object Copying : `09/30/2021`

#### Polymorphism : `09/29/2021`

#### Inheritance : `09/28/2021`

#### Data Modeling 1 : `09/27/2021`

#### Static : `09/24/2021`

#### Encapsulation : `09/23/2021`

#### Constructors : `09/22/2021`

#### Objects, Continued : `09/21/2021`

#### Introduction to Objects : `09/20/2021`

#### Compilation and Type Inference : `09/17/2021`

#### Maps and Sets : `09/16/2021`

#### Lists and Type Parameters : `09/15/2021`

#### Imports and Libraries : `09/14/2021`

#### Multidimensional Arrays : `09/13/2021`

#### null : `09/10/2021`

#### Algorithms and Strings : `09/09/2021`

#### Strings : `09/08/2021`

#### More About Functions : `09/07/2021`

#### Errors and Debugging : `09/03/2021`

#### Functions : `09/02/2021`

#### Algorithms I : `09/01/2021`

#### Loops : `08/31/2021`

#### Arrays : `08/30/2021`

#### Compound Conditionals : `08/27/2021`

#### Conditional Expressions and Statements : `08/26/2021`

#### Operations on Variables : `08/25/2021`

#### Variables and Types : `08/24/2021`

#### Welcome to CS 124 : `08/23/2021`

# Graph Algorithms

Java

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.

Interactive Walkthrough

Click on an icon below to start!

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.

Interactive Walkthrough

Click on an icon below to start!

## 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.

Interactive Walkthrough

Click on an icon below to start!

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

### Solution Walkthrough

Interactive Walkthrough

Click on an icon below to start!

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

### Solution Walkthrough

Interactive Walkthrough

Click on an icon below to start!