Jupyter at Bryn Mawr College
Public notebooks: /services/public/dblank / CS206 Data Structures / 2016-Spring / Notebooks

1. Graphs: Continued

Consider the following code:

public class LinkedList<T> {
    Node<T> head;

    public void append_front(T item) {
    // appends to front of list:
        Node<T> node = new Node<T>(item);
        node.next = head;
        head = node;
    }
    public void append_end(T item) {
        // appends to tail of list:
        Node<T> current = head;
        if (current == null) {
            Node<T> node = new Node<T>(item);
            head = node;
        } else {
            while (current.next != null) {
            current = current.next;
            }
            Node<T> node = new Node<T>(item);
            current.next = node;
        }
    }
    public boolean isEmpty() {
        return (head == null);
    }
    public T pop_front() {
        Node<T> temp = head;
        head = head.next;
        return temp.data;
    }
    public T pop_end() {
        Node<T> temp = head;
        Node<T> prev = head;
        while (temp.next != null) {
            prev = temp;
            temp = temp.next;
        }
        prev.next = null;
        return temp.data;
    }
}

What would be a better name for this class?

What is the Big O of appending?

What is the Big O of popping?

How could you make this class better?

1.1 Search

Consider the method search for the Game class:

public boolean search(String start, String end) {
        Place current = places.get(start);
        boolean found = false;
        HashSet<String> visited = new HashSet<String>();
        LinkedList<Place> queue = new LinkedList<Place>();
        queue.append(current);

        while (!queue.isEmpty()) {
            current = queue.pop_front();
            System.out.println("Visiting: " + current.name + "...");
            if (current.name.equals(end)) {
                System.out.println("Path exists!");
                found = true;
                break;
            }
            if (! visited.contains(current.name)) {
                System.out.println("   expanding: " + current.name + "...");
                visited.add(current.name);
                // expand:
                for (Action action: current.actions.values()) {
                    Place toplace = places.get(action.toplace);
                    queue.append_front(toplace);
                }
            }
        }
        if (!found) {
            System.out.println("ERROR: No path exists!");
        }
        return found;
    }

How is this code different from that given in chapter 10. How?

Which kind of search does this perform?

• depth-first
• breadth-first
• other

You could easily change it to the other. How?

This code doesn't give you the path. How could you fix that?

When the book talks about the "Graph ADT", what are they referring to?

You can also visit the nodes in a binary tree in either breadth-first or depth-first manner. How?

1.2 Dijkstra's Algorithm

https://www.youtube.com/watch?v=gdmfOwyQlcI