Depth First Search


Download jar file or use maven. psjava requires Java 1.6 (or above)


Example Code

// Let's prepare a simple graph.

MutableDirectedUnweightedGraph<String> graph = MutableDirectedUnweightedGraph.create();

graph.addEdge("A", "B");
graph.addEdge("B", "C");
graph.addEdge("C", "D");
graph.addEdge("C", "A");

// Use 'Visitor' for handling searching events.
// Here, we will find the back-edge in the graph.

SingleSourceDFS.traverse(graph, "A", new DFSVisitor<String, DirectedEdge<String>>() {
	public void onDiscovered(String vertex, int depth, VisitorStopper stopper) {

	public void onWalkDown(DirectedEdge<String> edge) {

	public void onBackEdgeFound(DirectedEdge<String> edge) {
		// Found! the edge:C->A is a back-edge.
		edge.from(); // must be "C"; // must be "A";

	public void onFinish(String vertex, int depth) {

	public void onWalkUp(DirectedEdge<String> downedEdge) {

// You can do DFS from multiple sources.

MultiSourceDFS.traverse(graph, VarargsIterable.create("A", "B"), new DFSVisitorBase<String, DirectedEdge<String>>());

// If you don't mind visiting order but want to visit all, do this.

AllSourceDFS.traverse(graph, new DFSVisitorBase<String, DirectedEdge<String>>());

See Also


Copyright 2014 psjava team. View on GitHub