Graph Theory-Part 3 Breadth First Search
In Our Previous Post we learn different Reperesntation of Graph Now In this Post we Would talk about how to traverse Graph..........
TRAVERSING A GRAPH Many application of graph requires a structured system to examine the vertices and edges of a graph G. That is a graph traversal, which means visiting all the nodes of the graph. There are two graph traversal methods. (a) Breadth First Search (BFS) (b) Depth First Search (DFS)
BREADTH FIRST SEARCH Given an input graph G = (V, E) and a source vertex S, from where the searching starts. The breadth first search systematically traverse the edges of G to explore every vertex that is reachable from S. Then we examine all the
vertices neighbor to source vertex S. Then we traverse all the neighbors of the neighbors of source vertex S and so on. A queue is used to keep track of the progress of traversing the neighbor nodes. BFS can be further discussed with an example. Considering the graph G in Fig.
So A, B, C, D, E, F, G, H is the BFS traversal of the graph in Fig.
ALGORITHM 1. Input the vertices of the graph and its edges G = (V, E)
2.Maintain an array which hold count of Vertices visited or not(visited =1 and not visited=1) 3. Input the source vertex and assign it to the variable S. 4. Add or push the source vertex to the queue. 5. Repeat the steps 5 and 6 until the queue is empty (i.e., front > rear) 6. Pop the front element of the queue and display it as visited. 7. Push the vertices, which is neighbor to just, popped element, if it is not in the queue and displayed (i.e., not visited). 8. Exit.
We Now Implement it in Java how to achieve BFS
public class Vertices { //class vertices has two field first is its element and second status //i.e Visited Veritices or Not public char ele; public boolean visited; public Vertices(char ele) { this.ele=ele; this.visited=false; } }
import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Graph { //Graph class hold public int maxVertices=8; //1.max verices count Vertices verticeslist[]; //2.an array of class Vertices int adjmatri[][]; //an matrix to hold info of visted and unvisited vertices int verticescount; //count of vertices Queue<Integer>q=new LinkedList<>();//queue for dfs operation public Graph() { //intialize the Graph verticeslist=new Vertices[maxVertices]; adjmatri=new int[maxVertices][maxVertices]; this.verticescount=0; for (int i = 0; i < adjmatri.length; i++) { for (int j = 0; j < adjmatri.length; j++) adjmatri[i][j]=0; } } public void addVertices(char ele) { //add verices verticeslist[verticescount]=new Vertices(ele); verticescount++; } public void addEdges(int i,int j) { //add edges adjmatri[i][j]=1; } public void bfs() { //start with source and mark it has visited verticeslist[0].visited=true; display(0); //display it q.add(0);//add it in stack int v2=0; while(!q.isEmpty()) { int v1=q.poll(); //pop out veritces //find connected nodes while((v2=getAdjUnvisitedVertex(v1))!=-1) { //insert its connected node in queue verticeslist[v2].visited=true; display(v2); q.add(v2); } } } private Integer getAdjUnvisitedVertex(int v) { // return connected node if present otherwise -1 for (int i = 0; i < verticescount; i++) { if(adjmatri[v][i]==1&&verticeslist[i].visited==false) { return i; } } return -1; } public void display(int v) { //display the vertices System.out.print(" "+verticeslist[v].ele); } public void print(int v, Graph g) { System.out.print(" "); for (int i = 0; i < g.maxVertices; i++) { g.display(i); System.out.print(" "); } System.out.println(""); for (int i = 0; i < g.maxVertices; i++) System.out.print("----"); System.out.println(); for (int i = 0; i < v; i++) { g.display(i); System.out.print("|"); for (int j = 0; j < v; j++) System.out.print(" "+g.getEdges(i, j) + " "); System.out.println(); } } private int getEdges(int i, int j) { return adjmatri[i][j]; } public static void main(String[] args) { Scanner sc=new Scanner(System.in); Graph g=new Graph(); System.out.println("add verices"); // Here We're adding Verices of any Type........ for (int i = 0; i < g.maxVertices; i++) { System.out.print("enter V->>"); g.addVertices(sc.next().charAt(0)); } //add edges to vertices.......... g.addEdges(0, 1); g.addEdges(1, 2); g.addEdges(1, 7); g.addEdges(2, 3); g.addEdges(2, 4); g.addEdges(3, 2); g.addEdges(4, 5); g.addEdges(4, 7); g.addEdges(5, 4); g.addEdges(6, 4); g.addEdges(7, 6); g.addEdges(7, 3); g.print(8, g); System.out.println("BFS REPRESNTATION"); System.out.println(); g.bfs(); } }
OUTPUT
