family_bfs.java

import java.util.*;

public class bfs {
    public static void main(String[] args) {
        // A hashmap is also called an "associative array." Think of it as an
        // array, but instead of being indexed with numbers 0 to n-1, it is
        // indexed based on the keys you supply. In this case, the hashmap has
        // keys that are strings, and values that are arrays of strings.
        HashMap<String, String[]> family = new HashMap<String, String[]>();

        // Java doesn't give us hashmap literals, so we have to build them up by
        // inserting key-value pairs one by one.
        family.put("belle", new String[] {"ethan", "madigan"});
        family.put("betty", new String[] {});
        family.put("ethan", new String[] {"steve", "judy"});
        family.put("jonathan", new String[] {"marshall", "betty"});
        family.put("judy", new String[] {});
        family.put("madigan", new String[] {"jonathan", "maggie"});
        family.put("maggie", new String[] {});
        family.put("marshall", new String[] {});
        family.put("milo", new String[] {"ethan", "madigan"});
        family.put("steve", new String[] {});

        // Method call to actually perform the breadth-first search.
        printResult(bfs(family, "belle", "marshall"));
        printResult(bfs(family, "milo", "steve"));
        printResult(bfs(family, "maggie", "steve"));
    }

    // The walk-through assumes the "belle" to "marshall" path
    public static LinkedList<String> bfs(HashMap<String, String[]> family, String beginNode, String endNode) {
        // A `LinkedList` is a last-in, first-out stack (like a stack of plates
        // in a cafeteria).

        //  Set `initalPath` to ["belle"]
        LinkedList<String> initialPath = new LinkedList<String>();
        initialPath.push(beginNode);

        // Set `paths` to [["belle"]]
        LinkedList<LinkedList<String>> paths = new LinkedList<LinkedList<String>>();
        paths.push(initialPath);

        // Loop until `paths` is empty. The first time through, `paths` = [["belle"]]
        while(paths.size() > 0) {
            // The `pop()` method takes removes and returns the item at the top of the stack.
            // Now `path` = ["belle"] and `paths` = []
            LinkedList<String> path = paths.pop();

            // The `peek()` method copies the top of a stack without popping it.
            // `node` now equals "belle"
            String node = path.peek();

            // The first time through, `node` is "belle", `endNode` is
            // "marshall", so this evaluates to `false`.
            if(node == endNode) {
                return path;
            }

            // This is where we build `paths` back up. `nextNode` is going to be
            // bound to each parent of "belle": "ethan", then "madigan" (the
            // `get()` method retrieves the value from the hashmap by key). So
            // by the time this `for` loop completes `paths` will equal
            //
            // [["belle", "ethan"], ["belle", "madigan"]].
            //
            // When the `while` loop above comes around again, the `for` loop
            // below will add the next generation:
            //
            // ["belle", "madigan", "maggie"], ["belle", "madigan", "jonathan"]]
            //
            // The final time through the `while` loop we'll get
            //
            // [["belle", "madigan", "jonathan", "marshall"]],
            //
            // The fact that we look up parents before adding to the stack means
            // we immediately prune branches that have dead-ended.
            //
            // You can see why it's called a breadth-first search: it branches
            // fully at each generation until short-circuiting after it
            // encounters the `endNode`
            for(String nextNode : family.get(node)) {
                // We have to copy `path` or else we would mutate the *original*
                // version of `path` defined above when we `push`ed on `nextNode`.
                // `pathCopy` now equals [["belle"]]
                LinkedList<String> pathCopy = new LinkedList<String>(path);

                // `pathCopy` will equal `[["belle", "ethan"]]` in one iteration
                // of the `for` loop and will equal [["belle", "madigan"]] in
                // the following iteration
                pathCopy.push(nextNode);

                // Uncomment me to see what happens on each iteration
                // printResult(pathCopy);


                // `paths` becomes [["belle", "ethan"]] the first time this
                // `for` loop iterates, and
                // [["belle", "ethan"], ["belle", "madigan"]]
                // the second time
                paths.push(pathCopy);
            }
        }

        return new LinkedList<String>();
    }

    // Helper method to print the results
    public static void printResult(LinkedList<String> result) {
        LinkedList<String> resultCopy = new LinkedList<String>(result);

        // We used a stack in the `bfs` method, which actually causes the
        // result to be backwards. So let's reverse the result.
        Collections.reverse(resultCopy);

        // We have to fiddle with types to get `println` to act the right way
        // (only the array class has a `toString`) method, but to use it, we
        // have to turn our `LinkedList` into an array.
        System.out.println(Arrays.toString(resultCopy.toArray()));
    }
}