In this task we will focus on the problem of finding a path between two given nodes in a graph.

Let \(s\) be the source node and \(t\) the destination node. We will keep which nodes have already been visited and which nodes still need to be processed in a queue. At each iteration we pick the node in front of the queue to be processed. Then we add all of its unvisited neighbours to the queue of nodes to process. If we continue in this way until there are no more nodes to process then we know that there is path from \(s\) to \(t\) if and only if \(t\) was visited.

Example:

The following figure shows an execution of this process with \(s = 0\).

Let's see what this looks like in Java. We will create a function that takes as input the graph \(g\), the source \(s\) and the destination \(t\). We start by adding the source to the queue and then process the nodes until no more nodes remain to be processed. To process a node, we loop over its neighbours and add all its unvisited neighbours to the queue so they are processed later. In the end, all nodes that are reachable from \(s\) will have been visited.

static boolean pathExists(LinkedList<Integer>[] g, int s, int t) {
    // initialize the queue and visited set
    Queue<Integer> Q = new LinkedList<>();
    Q.add(s);
    BitSet visited = new BitSet();
    visited.set(s);
    // loop while there are nodes in the queue to process
    // in practice you might want to stop as soon as end is visited
    while(!Q.isEmpty()) {
        int u = Q.poll();
        // we are now processing node u
        for(int v : g[u]) {
            // visit edge (u, v)
            if(!visited.get(v)) {
                // node v has not yet been visited, add  it
                Q.add(v);
                visited.set(v);
            }
        }
    }
    // return whether a path exists
    return visited.get(t);
}

Ok so now we have a function that checks whether a path exists. Now we are going to extend it so that we are able to compute an actual path between \(s\) and \(t\).

Doing this is quite simple. We just need to keep track, for each node, of who added it to the queue. If we have this then we can start from \(t\) and find who visited him, say \(u\). Then we check who put \(u\) in the queue and continue in this way until we reach the source \(s\). Note that we are guaranteed to reach \(s\) since this was the node on which we started the search.

Observe that by doing this we will build the path in reverse order because we start from \(t\) and trace back to \(s\). Therefore we need to reverse the list of nodes in the end.

static ArrayList<Integer> findPath(LinkedList<Integer>[] g, int s, int t) {
    // initialize the queue and visited set
    Queue<Integer> Q = new LinkedList<>();
    Q.add(s);
    BitSet visited = new BitSet();
    visited.set(s);
    // initialize the parent array
    Integer[] parent = new Integer[g.length];
    // loop while there are nodes in the queue to process
    // in practice you might want to stop as soon as end is visited
    while(!Q.isEmpty()) {
        int u = Q.poll();
        // we are now processing node u
        for(int v : g[u]) {
            // visit edge (u, v)
            if(!visited.get(v)) {
                // node v has not yet been visited, add it
                Q.add(v);
                visited.set(v);
                // set the parent of v to be u
                parent[v] = u;
            }
        }
    }
    // check whether a path exists
    if(!visited.get(t)) return null;
    // build the path by tracing back from t to s
    ArrayList<Integer> path = new ArrayList<>();
    Integer cur = t;
    // loop until we reach s (s is the only visited node with null parent)
    while(cur != null) {
        path.add(cur);
        cur = parent[cur];
    }
    // return the path
    Collections.reverse(path);
    return path;
}