In this post we'll see how to write a Java program for breadth-first search (BFS) traversal of a graph.
Graph traversal
To traverse a graph, where you try to reach all the connected vertices from the starting vertex, can be done in following ways-
- Depth-first search (DFS)
- Breadth-first search (BFS)
Breadth-first search
Contrary to DFS traversal, where algorithm works by moving away from the starting point and trying to go deep, BFS traversal works by visiting all adjacent vertices from the start vertex. Once all the adjacent vertices are exhausted then only it goes to the next level so it tries to traverse the whole breadth of the level before moving to the next level.
For example, if we have the following graph and the starting vertex is "A".
From "A" you have to go to any unvisited vertex, adjacent to "A". Let's say in this case it goes to "B" then you need to visit the next adjacent vertex of current vertex "A", which will be "C" same way "D" and "E". With this order ABCDE the current level is exhausted (you have explored the full breadth of this branch) so you need to go to the next level.
You have to pick the next current vertex from the current level of "BCDE", if it is "B" then the next adjacent vertex from current vertex "B" is "F". Since there is no other adjacent vertex from "B" so you need to pick another vertex from the "BCDE" level. If it is "C" then the next adjacent vertex from current vertex "C" is "G".
That's the way you do the BFS traversal of the given graph getting the order as "ABCDEFGHIJ".
Breadth-First Search Java program
For implementing Breath-First Search graph traversal program in Java, queue data structure is used to store the vertices that are already visited. Graph may have cycles so you need to keep track of visited vertices by having an extra array of all vertices and you mark the vertices which are already visited.
Graph can be represented using adjacency matrix or by using adjacency list, which of these two ways is used to represent the graph has to be taken in account while writing Java program for BFS traversal of the graph.
Note that in this article undirected graph traversal is done.
Refer post Graph Adjacency Representation - Java Program to get better explanation of graph adjacency representation using adjacency matrix or adjacency list.
Process for Breadth-First Search traversal is as given below-
- From the current vertex, visit an adjacent vertex which is not yet visited, mark it as visited and add it to the queue.
- Keep repeating step 1 while there are still unvisited adjacent vertices from the current vertex. If there is no unvisited adjacent vertex left then remove a vertex from queue and make it the current vertex. Again, start step 1.
- Process is done when queue is empty.
Here is the complete BFS traversal Java program when adjacency matrix is used to represent graph.
import java.util.LinkedList;
import java.util.Queue;
public class GraphBFSAM{
private int numOfVertices;
private int[][] adjMatrix;
// to store all the vertex labels
Vertex[] vertices;
private int temp = 0;
// Vertex class as nested class
static class Vertex{
String label;
// to track the visited vertices
boolean visited;
Vertex(String label){
this.label = label;
}
public String getLabel() {
return label;
}
public void setLabel(String label) {
this.label = label;
}
public boolean isVisited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
}
GraphBFSAM(int numOfVertices){
this.numOfVertices = numOfVertices;
vertices = new Vertex[numOfVertices];
adjMatrix = new int[numOfVertices][numOfVertices];
}
//Method to add all the graph vertices
public void addVertex(String label) {
vertices[temp++] = new Vertex(label);
}
public void addEdge(int source, int destination) {
if((source < 0 || source > numOfVertices) || (destination < 0 || destination > numOfVertices)) {
System.out.println("Invalid edge addition");
return;
}
adjMatrix[source][destination] = 1;
// For undirected graph reverse setting also required
adjMatrix[destination][source] = 1;
}
public void printGraph() {
for(int i = 0; i < adjMatrix.length; i++) {
for(int j = 0; j < adjMatrix[0].length; j++) {
System.out.print(adjMatrix[i][j] + "\t");
}
System.out.println();
}
}
public void bfsTraversal(int startVertex) {
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(startVertex);
vertices[startVertex].setVisited(true);
while(!queue.isEmpty()) {
int currentVertex = queue.poll();
System.out.print(vertices[currentVertex].getLabel() + " ");
//Keep adding to the queue while there are still adjacent vertices
for(int i = 0; i < adjMatrix.length; i++) {
if(adjMatrix[currentVertex][i] == 1 && !vertices[i].isVisited()) {
queue.add(i);
vertices[i].setVisited(true);
}
}
}
}
public static void main(String[] args) {
GraphBFSAM graph = new GraphBFSAM(10);
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addVertex("F");
graph.addVertex("G");
graph.addVertex("H");
graph.addVertex("I");
graph.addVertex("J");
graph.addEdge(0, 1); //A-B
graph.addEdge(0, 2); //A-C
graph.addEdge(0, 3); //A-D
graph.addEdge(0, 4); //A-E
graph.addEdge(1, 5); //B-F
graph.addEdge(5, 8); //F-I
graph.addEdge(2, 6); //C-G
graph.addEdge(4, 7); //E-H
graph.addEdge(7, 9); //H-J
//graph.printGraph();
graph.bfsTraversal(0);
}
}
Output
A B C D E F G H I J
Important points about the program
- Uses a static inner class Vertex to encapsulate a vertex with fields as label to store the label of the vertex and Boolean field visited to keep track of the vertex which is already visited.
- Adjacency matrix is used here to represent a graph.
- Array named vertices is used to store the vertices of the graph and mark the vertices which are already visited.
Here is the complete Java program when adjacency list is used to represent the graph.
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
public class GraphBFSAL {
private Map<String, List<String>> adjList;
// To keep track of already visited vertices
private Set<String> visited;
GraphBFSAL(){
adjList = new HashMap<>();
visited = new HashSet<String>();
}
public void addVertex(String v) {
adjList.putIfAbsent(v, new ArrayList<String>());
}
public void addEdge(String source, String destination) {
if(!adjList.containsKey(source)) {
addVertex(source);
}
if(!adjList.containsKey(destination)) {
addVertex(destination);
}
adjList.get(source).add(destination);
// Reverse link also required for undirected graph
//adjList.get(destination).add(source);
}
// Method to display graph
public void printGraph() {
adjList.forEach((k, v) -> {
System.out.print("Vertex " + k+ " connects to ");
v.forEach(e -> System.out.print(e + " "));
System.out.println();
});
}
public void bfsTraversal(String startVertex) {
Queue<String> queue = new LinkedList<String>();
queue.add(startVertex);
visited.add(startVertex);
while(!queue.isEmpty()) {
String currentVertex = queue.poll();
System.out.print(currentVertex+ " ");
for (String s : adjList.getOrDefault(currentVertex, Collections.emptyList())) {
if (!visited.contains(s)) {
queue.add(s);
visited.add(s);
}
}
}
}
public static void main(String[] args) {
GraphBFSAL graph = new GraphBFSAL();
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("A", "D");
graph.addEdge("A", "E");
graph.addEdge("B", "F");
graph.addEdge("F", "I");
graph.addEdge("C", "G");
graph.addEdge("E", "H");
graph.addEdge("H", "J");
//graph.printGraph();
graph.bfsTraversal("A");
}
}
Output
A B C D E F G H I J
Important points about the program-
- In the Java program Map and List collections are used to represent adjacency list.
- A HashSet named visited is used to store the vertices of the graph and mark the vertices which are already visited.
Time and space complexity of BFS graph traversal
If total number of vertices in the graph are V and the total number of edges are E then the time complexity is O(V2) when graph is represented as an adjacency matrix.
In adjacency matrix we have a 2D array of VXV which means while checking for neighbours of any vertex we have to scan the whole row which is O(V) time, meaning O(V2) for V vertices.
With adjacency list only adjacent vertices are stored as a list for each vertex. For each vertex, the algorithm iterates over adjacency list of that vertex. In an adjacency list representation, every edge appears exactly once (directed graph) or twice (undirected graph). Since the total time = time for vertex processing + time for scanning adjacency list for each vertex = O(V) + O(E)
So, the time complexity is O(V + E).
Auxiliary space requirement is O(V) to store visited vertices in an array or set. Queue may also end up storing V vertices (in worst case) so the space requirement is O(V) for the Queue used in the method.
Thus, the total space requirement is O(V) + O(V), discarding the constants the space complexity is O(V).
Note that adjacency list also takes O(V + E) space and adjacency matrix O(V2) space.
That's all for this topic Java Program - Breadth First Search (BFS) Traversal For Graph. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Advanced Tutorial Page
Related Topics
You may also like-
No comments:
Post a Comment