Graph Problems - Study Group - 11/28/17

Graph.java

class Graph {
    Neighbor[] adjList; // Vertices represented as integers
    public boolean hasPath(int u, int v) { // assume u, v are in range
    }
    public ArrayList < Integer > getPath(int u, int v) { // assume u, v are in range
    }
}
class Neighbor {
    int vertex;
    Neighbor next;
}

Graph_Solution.java

class Graph {
    Neighbor[] adjList; // Vertices represented as integers
    public boolean hasPath(int u, int v) { // assume u, v are in range
        boolean[] visited = new boolean[adjList.length];
        Queue < Integer > q = new Queue < > ();
        q.enqueue(u);
        visited[u] = true;
        while (!q.isEmpty()) {
            for (Neighbor n = adjList[q.dequeue()]; n != null; n = n.next) {
                if (n.vertex == v)
                    return true;
                if (!visited[n.vertex]) {
                    q.enqueue(n.vertex)
                    visited[n.vertex] = true;
                }
            }
        }
        return false;
    }
    public ArrayList < Integer > getPath(int u, int v) { // assume u, v are in range
        Stack s = new Stack();
        boolean[] visited;
        s = getPath(u, v, s, visited);
        ArrayList < Integer > l = new ArrayList < > ();
        while (!s.isEmpty()) {
            l.add(0, s.pop())
        }
        return l
    }
    public Stack getPath(int u, int v, Stack spath, boolean[] visited) {
        visited[u] = true;
        spath.push(u); // or v
        if (u == v) {
            return spath
        }
        for (Neighbor n = adjlist[u]; n != null; n = n.next) {
            if (!visited[n.vertex]) {
                spath = getPath(n.vertex, v, spath, visited);
                if (spath.peek() == v) {
                    return spath
                }
            }
        }
        spath.pop();
        return spath;
    }
}
class Neighbor {
    int vertex;
    Neighbor next;
}