Breadth first search(BFS), Depth first Search(DFS) both iterative and recursive in Java

Graph can be represented in two ways:

 1)adjacency matrix

  2) adjancency list

Note here we create array of linkedlist. Array are of size length vertices.

Each array has all its childrens so each array is linkedlist  of size vertices V.

	import java.util.*;
	/** * Created by laxmikadariya on 6/10/18. */public class Graph {
	int V;
	LinkedList<Integer> adj[];
	Graph(int v)
	{
	V=v;
	adj = new LinkedList[V];
	for(int i = 0;i<V;i++)
	{
	adj[i] = new LinkedList();
	}
	}
	void add_edge(int parent ,int child)
	{
	this.adj[parent].add(child);
	}
	void call_DFS_recursive(int start, boolean[] visited)
	{
	visited[start] = true;
	System.out.println(start);
	Iterator<Integer> it = adj[start].listIterator();
	while(it.hasNext() )
	{
	int element = it.next();
	if(!visited[element])
	{
	call_DFS_recursive(element,visited);
	}
	}
	}
	void DFS_iterative(int start)
	{
	boolean visited[] = new boolean[V];
	Stack<Integer> stack = new Stack();
	stack.push(start);
	visited[start] = true;
	while(!stack.empty())
	{
	int element = stack.pop();
	System.out.println(element);
	Iterator<Integer> it = adj[element].listIterator();
	while(it.hasNext())
	{
	int value = it.next();
	if(!visited[value]) {
	stack.push(value);
	visited[value] = true;
	}
	}
	}
	}
	void DFS(int start)
	{
	boolean [] visited = new boolean[V];
	call_DFS_recursive(start,visited);
	}
	void BFS(int start)
	{
	boolean visited[] = new boolean[V];
	Queue<Integer> queue = new LinkedList<Integer>();
	queue.add(start);
	visited[start]=true;
	while(queue.size() !=0)
	{
	int element = queue.remove();
	System.out.println(element);
	Iterator<Integer> it = adj[element].listIterator();
	while(it.hasNext())
	{
	int top = it.next();
	if(!visited[top] )
	{
	queue.add(top);
	visited[top] =true;
	}
	}
	}
	}
	public static void main(String []args)
	{
	Graph g = new Graph(6);
	g.add_edge(0,1);
	g.add_edge(0,2);
	g.add_edge(1,3);
	g.add_edge(1,4);
	g.add_edge(1,0);
	g.add_edge(2,4);
	g.add_edge(2,0);
	g.add_edge(3,4);
	g.add_edge(3,5);
	g.add_edge(3,1);
	g.add_edge(4,2);
	g.add_edge(4,3);
	g.add_edge(4,5);
	g.add_edge(5,4);
	g.add_edge(5,3);
	// g.DFS(0);// g.DFS_iterative(0); g.BFS(0);
	}
	}

view raw BFS_DFS_JAVA.java hosted with ❤ by GitHub