Undirected Graph Size
Geoffrey Challen // 2021.10.0
Create a public class named GraphSize that provides a single static method size.
size receives an unweighted graph containing Integer values using cs1.graphs.UnweightedGraph, so an
UnweightedGraph<Integer>.
To complete this problem you'll need to implement graph traversal.
From a given node, you want to visit all of its neighbors except any nodes that you've already visited.
If you use a Set to track the nodes that you've visited, then you can simply return the size of that Set when
you are finished.
We've provided some starter code to get you off on the right track.
For reference, cs1.graphs.UnweightedGraph has the following public properties:
And cs1.graphs.GraphNode has the following public properties:
import cs1.graphs.GraphNode;
import cs1.graphs.UnweightedGraph;
import java.util.HashSet;
import java.util.Set;
public class GraphSize {
public static int size(UnweightedGraph<Integer> graph) {
// Handle null
Set<GraphNode<Integer>> nodes = new HashSet<>();
traverse(graph.getNode(), nodes);
return 0;
}
private static void traverse(GraphNode<Integer> node, Set<GraphNode<Integer>> nodes) {
// Add this node to the set
// Iterate through all the neighbors
// If the neighbor hasn't been visited, call traverse on it and pass it the visited set
}
}