Sem 4 (AOAD) : Graph traversal Techniques- Breadth First Search (BFS) & Depth First Search (DFS) Java program / code.

Given below are java codes for graph traversal techniques.

Breadth First Search Java Code

// Aim:To implement Breadth first search import java.util.*; class Graph { Scanner scr=new Scanner(System.in); static int a[][]; static int visit[]=new int[10]; void adjm(int v,int e) { a=new int[v+1][v+1]; for(int i=1;i<=v;++i) { for(int j=1;j<=v;++j) { a[i][j]=0; } } for(int i=1;i<=e;++i) { System.out.println("Enter vertices of edge"); int b=scr.nextInt(); int c=scr.nextInt(); a[b][c]=a[c][b]=1; } } void bft(int v,int e) { for(int i=1;i<=v;++i) { if(visit[i]==0) bfs(i,v); } } void bfs(int u,int v) { visit[u]=1; System.out.print(" "+u); for(int i=1;i<=v;++i) { if(a[u][i]==1) { if(visit[i]==0) { visit[i]=1; System.out.print(" "+i); } } } } void dft() { for(int i=1;i<=v;++i) { if(visit[i]==0) dfs(i); } } void dfs(int u) { System.out.print(" "+u); visit[u]=1; for(int i=1;i<=v;++i) { if(a[u][i]==1) { if(visit[i]==0) dfs(i); } } } } class GT { public static void main(String args[]) { Scanner scr=new Scanner(System.in); try { System.out.println("Enter v & e"); int v=scr.nextInt(); int e=scr.nextInt(); Graph g=new Graph(); g.adjm(v,e); g.bft(v,e); } catch(Exception e) {} } } /* output Enter v & e 4 4 Enter vertices of edge 1 2 Enter vertices of edge 2 3 Enter vertices of edge 3 4 Enter vertices of edge 1 4 1 2 4 3 */


Depth First Search Java code
// Aim:To implement Depth first search import java.util.*; class Graph { Scanner scr=new Scanner(System.in); static int a[][]; static int visit[]=new int[10]; static int v,e; void adjm(int v,int e) { a=new int[v+1][v+1]; this.v=v; this.e=e; for(int i=1;i<=v;++i) { for(int j=1;j<=v;++j) { a[i][j]=0; } } for(int i=1;i<=e;++i) { System.out.println("Enter vertices of edge"); int b=scr.nextInt(); int c=scr.nextInt(); a[b][c]=a[c][b]=1; } } void dft() { for(int i=1;i<=v;++i) { if(visit[i]==0) dfs(i); } } void dfs(int u) { System.out.print(" "+u); visit[u]=1; for(int i=1;i<=v;++i) { if(a[u][i]==1) { if(visit[i]==0) dfs(i); } } } } class GT1 { public static void main(String args[]) { Scanner scr=new Scanner(System.in); System.out.println("Enter v & e"); int v=scr.nextInt(); int e=scr.nextInt(); Graph g=new Graph(); g.adjm(v,e); g.dft(); } } /* output Enter v & e 7 10 Enter vertices of edge 1 4 Enter vertices of edge 4 7 Enter vertices of edge 4 6 Enter vertices of edge 1 2 Enter vertices of edge 2 3 Enter vertices of edge 2 5 Enter vertices of edge 3 5 Enter vertices of edge 1 5 Enter vertices of edge 1 6 Enter vertices of edge 5 6 1 2 3 5 6 4 7 */