Dfs.java

package graph;

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

/**
 * @author Bazlur Rahman Rokon
 * @since 12/27/16.
 */
public class Dfs {
	private Graph graph;
	private int source;
	private boolean[] marked;
	private int[] edgeTo;

	public Dfs(Graph graph, int source) {
		this.graph = graph;
		this.source = source;

		this.marked = new boolean[graph.getVertices()];
		this.edgeTo = new int[graph.getVertices()];
	}


	private void dfs() {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(source);
		marked[source] = true;

		while (!queue.isEmpty()) {
			Integer v = queue.poll();
			List<Integer> items = graph.getAdj(v);
			for (int w : items) {
				if (!marked[w]) {
					marked[w] = true;
					edgeTo[w] = v;
					queue.offer(w);
				}
			}
		}
	}


	public Stack<Integer> pathTo(int v) {
		if (!marked[v]) return null;

		Stack<Integer> stack = new Stack<>();

		int x = v;
		while (x != source) {
			stack.push(x);
			x = edgeTo[x];
		}
		stack.push(source);

		return stack;
	}


	public static void main(String[] args) {
		Graph graph = new Graph(6);
		graph.addEdge(0,1);
		graph.addEdge(0,3);
		graph.addEdge(0,4);
		graph.addEdge(1,2);
		graph.addEdge(2,5);
		graph.addEdge(3,4);
		graph.addEdge(3,5);

		graph.printGraph();

		Dfs dfs = new Dfs(graph, 0);
		dfs.dfs();
		Stack<Integer> integers = dfs.pathTo(5);
		System.out.println(integers);

	}
}

Graph.java

package graph;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Bazlur Rahman Rokon
 * @since 12/27/16.
 */
public class Graph {
	private int v;
	private List<Integer> adj[];
	private int e;

	public Graph(int v) {
		this.v = v;
		adj = new List[v];
		for (int i = 0; i < adj.length; i++) {
			adj[i] = new ArrayList<>();
		}
	}

	public void addEdge(int v, int w) {
		adj[v].add(w);
		adj[w].add(v);
	}

	public void printGraph() {
		for (int i = 0; i < adj.length; i++) {
			System.out.print(i + ": ");
			List<Integer> list = adj[i];
			for (Integer item : list) {
				System.out.print(item + " ");
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {

	}

	public int getVertices() {
		return v;
	}

	public List<Integer> getAdj(Integer v) {
		return adj[v];
	}
}