package com.merrytech;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BreadthFirstPaths<E> {
    private final HashMap<E, Boolean> marked; // Is the shortest path to this vertex known?
    private final HashMap<E, E> edgeTo;  // last vertex on known path to this vertex
    private final E s;  // source

    public BreadthFirstPaths(Graph<E> g, E s) {
        this.marked = new HashMap<>();
        for (E k : g.getVertices()) {
            this.marked.put(k, false);
        }
        this.edgeTo = new HashMap<>();
        this.s = s;
        bfs(g, s);
    }

    private void bfs(Graph<E> g, E s) {
        Queue<E> queue = new LinkedList<E>();
        this.marked.put(s, true); // Mark the source
        queue.add(s);  // enqueue, put it on the queue
        while (!queue.isEmpty()) {
            E v = queue.poll(); // Dequeue. Remove next vertex from the queue
            for (E w : g.getAdjList(v)) {
                if (this.marked.get(w)) {
                    continue;
                }
                // For every unmarked adjacent vertex,
                this.edgeTo.put(w, v); // save last edge on a shortest path
                this.marked.put(w, true); // mark it because path is known
                queue.add(w); // and add to the queue
            }
        }
    }
    public boolean hasPathTo(E v) { return this.marked.get(v); }

    public Stack<E> pathTo(E v) {
        if (!this.hasPathTo(v)) {return null;}
        Stack<E> path = new Stack<>();
        for (E x = v; !x.equals(this.s); x = this.edgeTo.get(x)) {
            path.push(x);
        }
        path.push(this.s);
        return path;
    }
}

* Graph.java

package com.merrytech;

import java.util.*;

public class Graph<E> {
    private final int v; // number of vertices
    private int e; // number of edges
    private final HashMap<E, LinkedList<E>> adj; // adjacency lists

    public Graph(int v) {
        this.v = v;
        this.e = 0;
        this.adj = new HashMap<>(v);
    }

    public int countV() { return this.v; }
    public int countE() { return this.e; }

    public void addEdge(E v, E w) {
        if (!this.adj.containsKey(v)) {
            this.adj.put(v, new LinkedList<E>());
        }
        if (!this.adj.containsKey(w)) {
            this.adj.put(w, new LinkedList<E>());
        }
        this.adj.get(v).add(w);
        this.adj.get(w).add(v);
        this.e += 1;
    }

    public List<E> getAdjList(E v) { return this.adj.get(v); }
    public Set<E> getVertices() { return this.adj.keySet(); }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(this.v).append(" vertices, ").append(this.e).append(" edges\n");
        for (Map.Entry<E, LinkedList<E>> entry : this.adj.entrySet()) {
            sb.append(entry.getKey().toString()).append(": ");
            for (E w : entry.getValue()) {
                sb.append(w.toString()).append(" ");
            }
            sb.append("\n");
        }
        return sb.toString();
    }
}

package com.merrytech;

import java.util.Stack;

public class Main {

    public static void main(String[] args) {
        Graph<Integer> graph = new Graph<>(6);
        graph.addEdge(0, 2);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(3, 5);
        graph.addEdge(3, 4);
        graph.addEdge(3, 2);
        graph.addEdge(2, 4);
        graph.addEdge(5, 0);
        System.out.println(graph.toString());

        BreadthFirstPaths<Integer> bfs = new BreadthFirstPaths<>(graph, 0);
        for (Integer v : graph.getVertices()) {
            System.out.printf("0 to %d: ", v);
            Stack<Integer> path = bfs.pathTo(v);
            System.out.printf("%d", path.pop());
            while (!path.empty()) {
                System.out.printf("-%d", path.pop());
            }
            System.out.println();
        }
    }
}