1
                import java.util.*;
 2 3//This class represents a directed graph using adjacency list 
 4//representation  5class Graph1 {
 6privatestaticint V; // No. of vertices 7private LinkedList<Integer> adj[]; // Adjacency Lists
 8 9// Constructor10     Graph1(int v) {
11         V = v;
12         adj = new LinkedList[v];
13for (int i = 0; i < v; ++i)
14             adj[i] = new LinkedList();
15    }
1617// Function to add an edge into the graph18void addEdge(int v, int w) {
19        adj[v].add(w);
20    }
2122// prints BFS traversal from a given source s23publicvoid BFS() {
24// Mark all the vertices as not visited(By default
25// set as false)26boolean visited[] = newboolean[V];
27// Create a queue for BFS28         LinkedList<Integer> queue = new LinkedList<Integer>();
2930for (int i = 0; i < V; i++) {
31if (!visited[i]) {
32                BFSUtil(i, visited, queue);
33            }
34        }
35    }
3637publicvoid BFSUtil(int s, boolean visited[], LinkedList<Integer> queue) {
38// Mark the current node as visited and enqueue it39         visited[s] = true;
40        queue.add(s);
4142while (queue.size() != 0) {
43// Dequeue a vertex from queue and print it44             s = queue.poll();
45             System.out.print(s + " ");
4647// Get all adjacent vertices of the dequeued vertex s
48// If a adjacent has not been visited, then mark it
49// visited and enqueue it50             Iterator<Integer> i = adj[s].listIterator();
51while (i.hasNext()) {
52int n = i.next();
53if (!visited[n]) {
54                     visited[n] = true;
55                    queue.add(n);
56                }
57            }
58        }
59    }
6061// Driver method to62publicstaticvoid main(String args[]) {
63         Graph1 g = new Graph1(4);
6465         g.addEdge(0, 1);
66         g.addEdge(0, 2);
67         g.addEdge(1, 2);
68         g.addEdge(2, 0);
69         g.addEdge(2, 3);
70         g.addEdge(3, 3);
7172         System.out.println("Following is Breadth First Traversal " + "(starting from vertex 2)");
73        g.BFS();
74    }
75 }