Graph Implementation in java Bfs and Dfs
Graph Data Structure implementation in java
import java.util.*;
class Graph {
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
int V;
public Graph(int v){
this.V = v;
for(int i=0;i<V;i++)
list.add(new ArrayList<Integer>());
}
void add(int s , int d){
list.get(s).add(d);
list.get(d).add(s);
}
void display(){
for(int i=0;i<V;i++){
System.out.print(i+" : ");
for(int x : list.get(i))
System.out.print(" => "+x);
System.out.println("");
}
}
void dfs(int start){
boolean visited[] = new boolean[V];
_dfs(start,visited);
}
void _dfs(int node , boolean[] visited){
visited[node] = true;
System.out.print(node+" => ");
for(int x : list.get(node)){
if(!visited[x]){
_dfs(x,visited);
}
}
}
void bfs(int start){
boolean visited[] = new boolean[V];
Queue<Integer> q = new LinkedList<Integer>();
q.add(start);
visited[start] = true;
while(!q.isEmpty()){
int node = q.poll();
System.out.print( node+" => ");
for(int neigh : list.get(node)){
if(!visited[neigh]){
visited[neigh] = true;
q.add(neigh);
}
}
} //while
} //bfs
} //clas sGraph
class cf
{
static Scanner input = new Scanner(System.in);
public static void main(String[] args) {
Graph g = new Graph(7);
g.add(0,1);
g.add(0,2);
g.add(0,3);
g.add(1,4);
g.add(1,5);
g.add(1,6);
g.add(2,4);
g.add(4,5);
g.display();
System.out.println("Bfs : ");
g.bfs(6);
System.out.println("\nDfs : ");
g.dfs(6);
}
}
Output :
0 : => 1 => 2 => 3
1 : => 0 => 4 => 5 => 6
2 : => 0 => 4
3 : => 0
4 : => 1 => 2 => 5
5 : => 1 => 4
6 : => 1
Bfs :
6 => 1 => 0 => 4 => 5 => 2 => 3 =>
Dfs :
6 => 1 => 0 => 2 => 4 => 5 => 3 =>



