Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.
The non-recursive implementation is similar to breadth-first search but differs from it in two ways: it uses a stack instead of a queue, and it delays checking whether a vertex has been discovered until the vertex is popped from the stack rather than making this check before pushing the vertex.
Input: A graph G and a vertex v of G
Output: All vertices reachable from v labeled as discovered
A recursive implementation of DFS:
procedure DFS(G,v):
label v as discovered
for all edges from v to w in G.adjacentEdges(v) do
if vertex w is not labeled as discovered then
recursively call DFS(G,w)
A non-recursive implementation of DFS:
procedure DFS-iterative(G,v):
let S be a stack
S.push(v)
while S is not empty
v = S.pop()
if v is not labeled as discovered:
label v as discovered
for all edges from v to w in G.adjacentEdges(v) do
S.push(w)
Non recursive implementation of DFS:
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Stack;
public class GraphDFS {
// No. of vertices
private intvertives;
//Adjacency Lists - Edges
privateLinkedList<Integer> adj[];
GraphDFS(int vertices) {
vertives = vertices;
adj = newLinkedList[vertices];
for (inti=0; i<vertices; ++i) {
adj[i] = newLinkedList<Integer>();
}
}
void addEdge(intv,int w) {
adj[v].add(w);
}
private voidtraverseDFS(int node) {
/** Mark true if vertices are visited. */
boolean visited[] = newboolean[vertives];
/** Create a queue for DFS */
Stack<Integer> stack = newStack<Integer>();
/** mark start node as visited by default. */
visited[node] = true;
stack.add(node);
while(!stack.isEmpty()) {
/** poll the first element of queue. */
node = stack.pop();
System.out.print(node+" ");
/** add all the nearest node of processing node. */
Iterator<Integer> iter = adj[node].listIterator();
while (iter.hasNext()) {
int next = iter.next();
if (!visited[next]) {
visited[next] = true;
stack.push(next);
}
}
}
}
public static void main(String args[]) {
/** Create a graph of size . */
GraphDFS graph = newGraphDFS(4);
/** Add edges in the graph.*/
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(2, 3);
graph.addEdge(3, 2);
graph.addEdge(3, 1);
System.out.println("DFS Traversal : ");
/** start BS from any given node.*/
graph.traverseDFS(1);
}
}
Output:
DFS Traversal :
1 2 3 0
