Breadth First Search

Implementation

Find a path between two vertices

BFS can be used to return a path from one vertex to another.

If all of the edge weights are non-negative and equal then BFS will return the shortest path.

// Use same vertex class as defined in the above example.

List<Vertex> BFS(Vertex start, Vertex end) {
    List<Vertex> pathToEnd = null;
    boolean foundEnd = false;

    // Queue to hold vertex and paths while processing
    Queue<QueueEntry> unfinishedVertexQueue = new LinkedList<>();

    // List to hold visited vertices
    Set<Vertex> visitedVertexSet = new HashSet<>();

    processingQueue.offer(new QueueEntry(new ArrayList<>(), start);
    visitedVertices.add(start);

    while(processingQueue.peek() != null) {
        QueueEntry entry = processingQueue.poll();
        Vertex vertex = entry.vertex;

        // Loop through all adjacent vertices
        for(Vertex neighbor : vertex.adjacencyList) {
            // Skip if the neighbor has already been visited
            if(!visitedVertices.contains(neighbor)) {
                visitedVertices.add(neighbor);

                // A path to the end has been found.  Add end and return.
                if(neighbor == end) {
                    entry.path.add(neighbor);
                    pathToEnd = entry.path;
                    foundEnd = true;
                    break;
                }
                else {
                    // Copy the path for each neighbor
                    List<Vertex> newPath = new ArrayList<>(entry.path);
                    newPath.add(neighbor);

                    processingQueue.offer(new QueueEntry(newPath, neighbor));
                }
            }
        }
        if(foundEnd) {
            break;
        }
    }
    return pathToEnd;
}

public class QueueEntry {
    public List<Vertex> path;
    public Vertex vertex;

    public QueueEntry(List<Vertex> path, Vertex vertex) {
        this.path = path;
        this.vertex = vertex;
    }
}

public class Vertex {
    public List<Vertex> adjacencyList;
}

Runtime and Space considerations