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 =>

Popular Posts

java:17: error: local variables referenced from a lambda expression must be final or effectively final count ++ ;

Family Tree Project in Java

Creating basic tic tac toe android app using java