Tuesday, November 25, 2014

Breadth First Search (BFS) in a Graph in Java.

BFS like DFS is a way to traverse the graph. In BFS algorithm the graph is traversed as close as possible to the root node. Queue is used in the implementation of the breadth first search.We visit all the vertices that are at the distance of one edge away from current vertex. Then for each of those vertices that are one edge away it explores their unvisited vertices that are one edge away.

In BFS starting vertex is visited and inserted at end of queue then we keep on doing below 2 steps until queue is empty.
1. Remove an item from head of queue and make it current vertex
2. Visit all adjacent unvisited vertices of current vertex one by one and add them to end of queue. When there is no unvisited vertex left we follow step 1.



In above graph for BFS we starts at vertex A and visit all unvisited vertices that are one edge away from A and insert them to queue. Vertices that are inserted in queue are BFHI. After that we remove vertex at head of queue i.e. B and make it current vertex and visit its adjacent vertices and add them to queue. Queue content after we visit all of B adjcaent unvisited vertices is FHICD. Then we remove F and make it current vertex and we keep on repeating above 2 steps for BFS. Final order in which vertices are visited is ABFHICDGJE.

Java Code For BFS:


 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
import java.util.LinkedList;
import java.util.Queue;

public class BFS {
 private GraphAdjacencyMatrix graph;
 private Queue<Integer> queue;

 public BFS(){
  queue = new LinkedList<Integer>();
 }
 
 public void bfs(){
  graph.vertexList[0].isVisited = true;
  graph.display(0);
  queue.add(0);
  
  while(!queue.isEmpty()){
   int vert = queue.remove();
   int idx;
   
   while((idx=getAdjUnvistedVertex(vert))!=-1){
    graph.vertexList[idx].isVisited = true;
    graph.display(idx);
    queue.add(idx);
   }
  }
 }
 
 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) {
  BFS bfsObj = new BFS();
  bfsObj.setGraph();
  bfsObj.bfs();
 }
} 
 
Output:
ABFHICDGJE
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)