**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 int
vertives;

//Adjacency Lists - Edges

private
LinkedList<Integer> adj[];

GraphDFS(int vertices) {

vertives = vertices;

adj = new
LinkedList[vertices];

for (int
i=0; i<vertices; ++i) {

adj[i] = new
LinkedList<Integer>();

}

}

void addEdge(int
v,int w) {

adj[v].add(w);

}

private void
traverseDFS(int node) {

/** Mark true if vertices are visited. */

boolean visited[] = new
boolean[vertives];

/** Create a queue for DFS */

Stack<Integer> stack = new
Stack<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 = new
GraphDFS(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

## No comments:

## Post a Comment