Kotlinlearncs.online LogoJava

    ← Prev

    Index

    Next →

    Kotlin
    Java

    • JavaFX : 61

    • Graph Algorithms : 60

    • Graphs : 59

    • Streams : 58

    • Generics : 57

    • Implementing a Map : 56

    • Hashing : 55

    • Binary Search : 54

    • Quicksort : 53

    • Merge Sort : 52

    • Sorting Algorithms : 51

    • Practice with Recursion : 50

    • Trees and Recursion : 49

    • Trees : 48

    • Recursion : 47

    • Lists Review and Performance : 46

    • Linked Lists : 45

    • Algorithms and Lists : 44

    • Lambda Expressions : 43

    • Anonymous Classes : 42

    • Practice with Interfaces : 41

    • Implementing Interfaces : 40

    • Using Interfaces : 39

    • Working with Exceptions : 38

    • Throwing Exceptions : 37

    • Catching Exceptions : 36

    • References and Polymorphism : 35

    • References : 34

    • Data Modeling 2 : 33

    • Equality and Object Copying : 32

    • Polymorphism : 31

    • Inheritance : 30

    • Data Modeling 1 : 29

    • Static : 28

    • Encapsulation : 27

    • Constructors : 26

    • Objects, Continued : 25

    • Introduction to Objects : 24

    • Compilation and Type Inference : 23

    • Practice with Collections : 22

    • Maps and Sets : 21

    • Lists and Type Parameters : 20

    • Imports and Libraries : 19

    • Multidimensional Arrays : 18

    • Practice with Strings : 17

    • null : 16

    • Algorithms and Strings : 15

    • Strings : 14

    • Functions and Algorithms : 13

    • Practice with Functions : 12

    • More About Functions : 11

    • Errors and Debugging : 10

    • Functions : 9

    • Practice with Loops and Algorithms : 8

    • Algorithms I : 7

    • Loops : 6

    • Arrays : 5

    • Compound Conditionals : 4

    • Conditional Expressions and Statements : 3

    • Operations on Variables : 2

    • Variables and Types : 1

    • Hello, world! : 0

    Graph Algorithms

    import cs1.graphs.UnweightedGraph;
    import cs1.graphs.GraphNode;
    import java.util.Arrays;
    import java.util.Set;
    import java.util.HashSet;
    void traverse(UnweightedGraph<Integer> graph) {
    traverse(graph.getNode(), new HashSet<GraphNode<Integer>>());
    }
    void traverse(GraphNode<Integer> node, Set<GraphNode<Integer>> visited) {
    if (visited.contains(node)) {
    return;
    }
    visited.add(node);
    System.out.println(node);
    for (GraphNode<Integer> neighbor : node.getNeighbors()) {
    traverse(neighbor, visited);
    }
    }
    UnweightedGraph<Integer> graph =
    UnweightedGraph.randomUndirectedGraph(Arrays.asList(1, 2, 4, 8, 7, 5, 2, 1));
    traverse(graph);

    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
    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:

    import cs1.graphs.UnweightedGraph;
    import java.util.Arrays;
    int graphMax(UnweightedGraph<Integer> graph) {
    if (graph == null) {
    throw new IllegalArgumentException();
    }
    // Create set of nodes using traversal
    // Iterate over the set to determine the max
    return 0;
    }
    UnweightedGraph<Integer> graph =
    UnweightedGraph.randomUndirectedGraph(Arrays.asList(1, 2, 4, 8, 7, 5, 2, 1));
    assert graphMax(graph) == 8;

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

    import cs1.graphs.UnweightedGraph;
    import java.util.Arrays;
    int graphMax(UnweightedGraph<Integer> graph) {
    if (graph == null) {
    throw new IllegalArgumentException();
    }
    // Traverse the graph and compute the maximum at the same time
    return 0;
    }
    UnweightedGraph<Integer> graph =
    UnweightedGraph.randomUndirectedGraph(Arrays.asList(1, 2, 4, 8, 7, 5, 2, 1));
    assert graphMax(graph) == 8;

    Graph Contains Cycle
    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.

    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.

    import cs1.graphs.UnweightedGraph;
    import java.util.Arrays;
    boolean hasCycle(UnweightedGraph<Integer> graph) {
    return false;
    }
    UnweightedGraph<Integer> circle =
    UnweightedGraph.circleUndirectedGraph(Arrays.asList(1, 2, 4, 8, 7, 5, 2, 1));
    UnweightedGraph<Integer> linear =
    UnweightedGraph.linearUndirectedGraph(Arrays.asList(1, 2, 4, 8, 7, 5, 2, 1));
    UnweightedGraph<Integer> cross =
    UnweightedGraph.crossUndirectedGraph(Arrays.asList(1, 2, 4, 8), Arrays.asList(7, 5, 2, 1));
    UnweightedGraph<Integer> tree =
    UnweightedGraph.randomTreeUndirectedGraph(Arrays.asList(1, 2, 4, 8, 7, 5, 2, 1));
    assert hasCycle(circle);

    Solve: Undirected Graph Neighborhood Count (Practice)

    Created By: Geoffrey Challen
    / Version: 2021.10.0

    Create a public class GraphCount with a single class method count. count accepts two parameters: a UnweightedGraph<Integer> from cs1.graphs, and an int. You should return the count of the number of nodes in the graph where the number of 2-hop neighbors of that node is at least as large as the passed int. If the passed graph is null, or if the int is less than or equal to zero, throw an IllegalArgumentException.

    What is a 2-hop neighbor? Consider the node B in the following simple unweighted undirected graph:

        F
    |
A - B - C - D - E
    |
    H
    |
    J

    B has 4 1-hop neighbors: A, F, C, and H, nodes that are reachable in 1 hop from B. B has 6 2-hop 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 getNodes() 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 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 GraphCount {
    public static int count(UnweightedGraph<Integer> graph, int atLeast) {
    // Check arguments
    int total = 0;
    for (GraphNode<Integer> node : graph.getNodes()) {
    // Create a new visited set
    Set<GraphNode<Integer>> seen = new HashSet<>();
    count(node, seen, 2);
    // Check size of seen...
    }
    return total;
    }
    private static void count(GraphNode<Integer> node, Set<GraphNode<Integer>> seen, int distance) {
    // For you to complete...
    }
    }

    Solve: Unweighted Graph Is Undirected

    Created By: Geoffrey Challen
    / Version: 2021.10.0

    Create a public class GraphAnalysis that provides a single static method named isUndirected. isUndirected accepts an UnweightedGraph<?> from cs1.graphs and should return true if the graph is undirected and false otherwise. If the passed graph is null, throw an IllegalArgumentException.

    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 has the following public properties:

    And cs1.graphs.GraphNode has the following public properties:

    More Practice

    Need more practice? Head over to the practice page.