Tuesday, November 25, 2014

Depth First Search (DFS) in a Graph in Java.

DFS is a way to traverse the graph. To traverse a graph means to visit the vertices of graph in some systematic order. In this algorithm we select a root node or starting node and traverse the graph in such a way that it tries to go far from the root node. For implementing DFS stack is used and knowledge of below 3 stack operations is required to understand dfs  program in this tutorial.
Stack operations:
1. push: add an item on the top of stack.
2. peek: return the value of topmost item on stack without removing it.
3. pop: remove topmost item and return its value

DFS starts from a vertex, marks it visited and push this vertex on stack. Then it keeps on doing following 2 steps until stack is empty.
1. Peek at top of stack to get a vertex and visit its adjacent unvisited vertex and push that vertex on stack.
2. If a vertex that is peeked does not have adjacent unvisited vertex then pop that vertex of stack and again peek at top of stack and find its adjacent unvisited vertex.

In below graph when dfs is applied vertices are visited in order ABCDEFGHIJ. Starting vertex is A and it is marked as visited and pushed on stack then we visit adjacent unvisited vertex of A which B and it is also pushed on stack. Then C is visited, which is adjacent to B and unvisited and pushed on stack and since C does not have any adjacent unvisited vertex it is popped off from stack. Now we have B on top of stack and we again check next adjacent unvisited vertex of B which is D and it is pushed on to stack. After we keep on following above 2 steps for dfs we get desired output.

Java code for dfs is given below. Above graph is represented in below code for dfs. I have used graph code from my previous post on representation of graph.



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public class DFS {
 private GraphAdjacencyMatrix graph;
 private Stack<Integer> stack;
 
 public DFS(){
  stack = new Stack<Integer>();
 }
 
 public void dfs(){
  graph.vertexList[0].isVisited = true;
  graph.display(0);
  stack.push(0);
  int vert;
  int idx;
  
  while(!stack.isEmpty()){
   vert = stack.peek();
   
   if((idx=getAdjUnvistedVertex(vert))!=-1){
    graph.vertexList[idx].isVisited = true;
    graph.display(idx);
    stack.push(idx);
   }else{
    stack.pop();
   }
  }
 }
 
 public int getAdjUnvistedVertex(int vert){
  for (int i = 0; i < graph.vertexList.length; i++) {
   if(graph.adjMatrix[vert][i] == 1 && !graph.vertexList[i].isVisited){
    return i;
   }
  }
  return -1;
 }
 
 public void setGraph(){
  graph = new GraphAdjacencyMatrix(10);
  graph.addVertex('A');
  graph.addVertex('B');
  graph.addVertex('C');
  graph.addVertex('D');
  graph.addVertex('E');
  graph.addVertex('F');
  graph.addVertex('G');
  graph.addVertex('H');
  graph.addVertex('I');
  graph.addVertex('J');
  
  graph.addEdge(0, 1);
  graph.addEdge(1, 2);
  graph.addEdge(1, 3);
  graph.addEdge(3, 4);
  graph.addEdge(0, 5);
  graph.addEdge(5, 6);
  graph.addEdge(0, 7);
  graph.addEdge(0, 8);
  graph.addEdge(8, 9);
 }
 
 public static void main(String[] args) {
  DFS dfsObj = new DFS();
  dfsObj.setGraph();
  dfsObj.dfs();
 }
}
Output:
ABCDEFGHIJ

In above program in while loop of method dfs() we keep on checking if stack is empty. If stack is not empty we peek on vertex present on top of stack and get its adjacent unvisited vertex using method getAdjUnvistedVertex. After that vertex isVisited variable is marked true so that program remember we have visited that vertex and it is printed on output and pushed on stack. If a vertex does not have any adjacent unvisited vertex we pop it from stack. For finding adjacent unvisited vertex inside method getAdjUnvistedVertex there is if condition inside for loop
if(graph.adjMatrix[vert][i] == 1 && !graph.vertexList[i].isVisited){
if graph.adjMatrix[vert][i] == 1  it means there is edge between vert and i, where vert is vertex currently on top of stack and vertex i is checked if it is visited or not using !graph.vertexList[i].isVisited if both conditions are true that vertex is returned as adjacent unvisted vertex.


Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)