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 warmup, 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, crossshaped, and treelike graphs that do not.
Create a method count
.
count
accepts two parameters: a UnweightedGraph<Int>
from cs1.graphs
, and an Int
.
You should return the count of the number of nodes in the graph where the number of 2hop neighbors of that node is
at least as large as the passed Int
.
If the passed Int
is less than or equal to zero, throw an IllegalArgumentException
.
What is a 2hop neighbor? Consider the node B in the following simple unweighted undirected graph:
F

A  B  C  D  E

H

J
B has 4 1hop neighbors: A, F, C, and H, nodes that are reachable in 1 hop from B. B has 6 2hop neighbors: A, F, C, H, J, and D, nodes that are reachable in 2 hops from B.
To solve this problem you'll need to write a recursive helper method that you can run starting at each node in the
graph, which you can enumerate using the nodes
properly of the graph as described below.
Your recursive method will need to keep track of two things as it explores the graph: a set of nodes that
have already been visited, to avoid backtracking, and the distance from the start node.
Your base case can be either reaching a node you have already visited, or reaching 2 hops from the start, at
which point you should stop exploring.
Note that your count will probably be off by one, since you'll probably end up including the start node in your calculation. Be sure to keep that in mind.
This problem is tricky to set up, so we've provided some starter code to get you going. Good luck, and have fun!
For reference, cs1.graphs.UnweightedGraph
is declared somewhat like this:
And cs1.graphs.GraphNode
is declared somewhat like this:
Create a method named isUndirected
.
isUndirected
accepts an UnweightedGraph<*>
from cs1.graphs
and should return true
if the graph is
undirected and false
otherwise.
Each node in the graph has a set of neighbors that you can retrieve representing links from that node to other nodes. If the graph is undirected, if there is a link from A to B then there is also a link from B to A. So if B is a neighbor of A, then A should also be a neighbor of B.
Note that you do not need to solve this problem recursively, since there is a concise iterative solution.
For reference, cs1.graphs.UnweightedGraph
is declared somewhat like this:
And cs1.graphs.GraphNode
is declared somewhat like this:
Need more practice? Head over to the practice page.