The post shows you Graph Breadth First Search in Java. Breadth First Search or Breadth First Traversal is a recursive algorithm for visiting all the vertices of a graph or tree data structure. There is different a bit between searching for a graph and a tree. Let’s dive into it.
Graph Breadth First Search in Java
Breadth First Search (BFS) Algorithm
When visiting a graph from a vertex to another vertex, you maybe get loops so a vertex might be visited again. Here, we can fix it by using a flag of boolean type to mark a visited vertex. For simplicity, it is assumed that all vertices are reachable from the starting vertex and we put vertices that need to visit into a queue.
The Breadth First Search Algorithm works as follows:
- Putting a vertex of the graph at the back of a queue.
- Pop the front item of the queue and mark it as visited.
- Create a list of that vertex’s adjacent nodes. Then just add the ones which aren’t visited into the back of the queue.
- Keep repeating steps 2 and 3 until the queue is empty.
Breadth First Search Algorithm pseudocode
|
1 2 3 4 5 |
create a queue QUEUE mark v as visited and put v into QUEUE while QUEUE is non-empty remove the head uv of QUEUE mark and enqueue all (unvisited) adjacencies of uv in QUEUE |
Time and space complexity
The time complexity can be expressed as O(V + E), V is the number of vertices and E is the number of edges in the graph since every vertex and every edge will be explored in the worst case.
The space complexity can be expressed as O(V).
Implement of BFS
Now, you can implement a Graph Breadth First Search in Java looks like this program
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
// Simple program implements a Graph in adjacency list import java.util.*; class Graph { // We use Hashmap to store the edges in the graph // Hashmap keys are the vertices and values are the edges private Map<Node, List<Node>> map; // Store vertices that need to visit private Queue<Node> queue; static class Node{ int data; boolean visited; Node(int data){ this.data=data; } public int getData(){ return data; } } Graph(){ this.map = new HashMap<>(); this.queue = new LinkedList<Node>(); } // adds a new vertex to the graph public void addVertex(Node vertex) { map.put(vertex, new LinkedList<Node>()); } // adds the edge of source and destination vertexs public void addEdge(Node sVertex, Node dVertex) { if (!map.containsKey(sVertex)) addVertex(sVertex); if (!map.containsKey(dVertex)) addVertex(dVertex); map.get(sVertex).add(dVertex); } // get graph size public Integer size() { return map.keySet().size(); } // return the count of edges public Integer getEdgesCount() { int count = 0; for (Object v : map.keySet()) { count += map.get(v).size(); } return count; } // graph contains a vertex or not. public boolean containsVertex(Node vertex) { return map.containsKey(vertex)?true:false; } // an edge of two vertices is present or not. public boolean existEdge(Node sVertex, Node dVertex) { return map.get(sVertex).contains(dVertex)?true:false; } // Displays the adjancency list of each vertex. @Override public String toString() { StringBuilder builder = new StringBuilder(); for (Node vertex : map.keySet()) { builder.append(vertex.getData() + ": "); for (Node dVertex : map.get(vertex)) { builder.append(dVertex.getData()+ " "); } builder.append("\n"); } return (builder.toString()); } public void bFS(Node node){ queue.add(node); node.visited=true; while (!queue.isEmpty()){ Node adjacencyNode =queue.remove(); System.out.print(adjacencyNode.getData() + "\t"); List<Node> adjacencies = map.get(adjacencyNode); for (int i = 0; i < adjacencies.size(); i++) { Node n=adjacencies.get(i); if(n!=null && !n.visited) { queue.add(n); n.visited=true; } } } } public static void main(String args[]) { // create new graph instance Graph g = new Graph(); Node n10 = new Node(10); Node n20 = new Node(20); Node n30 = new Node(30); Node n40 = new Node(40); // edges are added. g.addEdge(n10, n20); g.addEdge(n10, n40); g.addEdge(n20, n10); g.addEdge(n20, n30); g.addEdge(n20, n40); g.addEdge(n30, n20); g.addEdge(n30, n40); g.addEdge(n40, n10); g.addEdge(n40, n20); g.addEdge(n40, n30); // print the graph. System.out.println("Here is the graph:\n" + g.toString()); // Breadth First Search System.out.println("Breadth First Search for Graph:"); g.bFS(n10); } } |
Here is output
That’s all about Graph Breadth First Search in Java.
References
Graph documentation
