Breadth First Search is an algorithm for traversing elements from a data structure or searching tree. Visiting each vertex and edge exactly in a well defined order is done in Graph travelers. Traversal of an element in graphically is well defined in searching algorithms.

The first traversal in BFS accomplished by inquiring each level of a tree. Traversal means visiting of the vertices in an order. The traversal may be in

Pre-order: Visit node before its child node

Post-order: visit node after its child node.

In-Order: visit from left sub tree to right sub tree including the node.

A visualization for Breadth first Search:

BFS applied, the vertices of the graph are divided into two categories. Vertices which are not visited as part of the search and which are visit as part of the search. In BFS start search at a vertex or source. Once the search is started from the source, the number of vertices that are visited as part of the search is 1 and all the remaining vertices need to be visited. Then search the vertices which are adjacent to the visited vertex from left. In this way all the graph is searched from source to end.

Demo of BFS with examples:

1

/ | \

2 3 4

/ \ \

5 6 7

| / | \

8 9 10 11

Example 2:

**Time and Complexity of BFS:**

The time complexity can be expressed as **O(|V|+|E|)O ( | V | + | E | )**, since every vertex and every edge will be explored in the worst case. | V | is the number of vertices and | E |is the number of edges in the graph. Note that O ( | E | ) may vary between O ( 1 ) and O(|V|^{2}), depending on how sparse the input graph is.

When the number of vertices in the graph is known ahead of time, and additional data structures are used to determine which vertices have already been added to the queue, the space complexity can be expressed as O(|V|), where | V |is the cardinality of the set of vertices. This is in addition to the space required for the graph itself, which may vary depending on the graph representation used by an implementation of the algorithm.

When working with graphs that are too large to store explicitly (or infinite), it is more practical to describe the complexity of breadth-first search in different terms: to find the nodes that are at distance *d* from the start node (measured in number of edge traversals), BFS takes ** O(b^{d}^{ + 1})** time and memory, where

*b*is the “branching factor” of the graph (the average out-degree)

Worst Case Performance: **O(|V|+|E|)O ( | V | + | E | ) {\displaystyle O(|V|+|E|)} = O(b ^{d})**

Worst Case complexity:** O(|V|)O ( | V | + | E | ) {\displaystyle O(|V|+|E|)} = O(b ^{d})**

**Algorithm flow of BFS**:

1 . Identify and un mark all vertices

2. choose some starting vertex x

mark x

list L = x

tree T = x

while L nonempty

choose some vertex v from front of list

3. visit v

for each unmarked neighbor w

mark w

4. add it to end of list

add edge vw to T.

**Applications of BFS:**

- Finding shortest paths between nodes.
- Minimum spanning tree for un-weighted graph.
- For garbage collection, Cheney’s algorithm
- Finding connected nodes in graph.
- Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be re-constructed in an efficient manner.

**Program in Java for Breadth First Java**

**package** Learnerschoice;

**import** java.util.LinkedList;

**import** java.util.Queue;

**public** **class** BFS {

**private** Node root;

**public** **boolean** isEmpty() {

**return** (**this**.root == **null**);

}

**public** **void** insert(Integer data) {

System.** out**.print(“[input: “+data+”]”);

**if**(root == **null**) {

**this**.root = **new** Node(data);

System.** out**.println(” -> inserted: “+data);

**return**;

}

insertNode(**this**.root, data);

System.** out**.print(” -> inserted: “+data);

System.** out**.println();

}

**private** Node insertNode(Node root, Integer data) {

Node tmpNode = **null**;

System.** out**.print(” ->”+root.getData());

**if**(root.getData() >= data) {

System.** out**.print(” [L]”);

**if**(root.getLeft() == **null**) {

root.setLeft(**new** Node(data));

**return** root.getLeft();

} **else** {

tmpNode = root.getLeft();

}

} **else** {

System.** out**.print(” [R]”);

**if**(root.getRight() == **null**) {

root.setRight(**new** Node(data));

**return** root.getRight();

} **else** {

tmpNode = root.getRight();

}

}

**return** insertNode(tmpNode, data);

}

**public** **void** levelOrderTraversal() {

Queue<Node> FindNode = **new** LinkedList<>();

**if**(**this**.root == **null**) {

System.** out**.println(“The tree is empty.”);

**return**;

}

FindNode.add(**this**.root);

**while** (!FindNode.isEmpty()) {

Node tmpNode = FindNode.remove();

**if**(tmpNode.getLeft() != **null**) { FindNode.add(tmpNode.getLeft()); }

**if**(tmpNode.getRight() != **null**) { FindNode.add(tmpNode.getRight()); }

System.** out**.print(tmpNode.getData()+” “);

}

}

**public** **static** **void** main(String a[]) {

BFS bst = **new** BFS();

bst.insert(7);

bst.insert(7);

bst.insert(3);

bst.insert(0);

bst.insert(8);

bst.insert(7);

bst.insert(5);

bst.insert(3);

bst.insert(2);

bst.insert(9);

System.** out**.println(“——————-“);

System.** out**.println(“order traversal by level wise”);

System.** out**.println(“——————-“);

bst.levelOrderTraversal();

}

**public** **class** Node {

**private** Node left;

**private** Node right;

**private** Integer data;

**public** Node(Integer data) {

**this**.data = data;

}

**public** Node getLeft() {

**return** left;

}

**public** **void** setLeft(Node left) {

**this**.left = left;

}

**public** Node getRight() {

**return** right;

}

**public** **void** setRight(Node right) {

**this**.right = right;

}

**public** Integer getData() {

**return** data;

}

}

}

Output as follows:

[input: 7] -> inserted: 7 [input: 7] ->7 [L] -> inserted: 7 [input: 3] ->7 [L] ->7 [L] -> inserted: 3 [input: 0] ->7 [L] ->7 [L] ->3 [L] -> inserted: 0 [input: 8] ->7 [R] -> inserted: 8 [input: 7] ->7 [L] ->7 [L] ->3 [R] -> inserted: 7 [input: 5] ->7 [L] ->7 [L] ->3 [R] ->7 [L] -> inserted: 5 [input: 3] ->7 [L] ->7 [L] ->3 [L] ->0 [R] -> inserted: 3 [input: 2] ->7 [L] ->7 [L] ->3 [L] ->0 [R] ->3 [L] -> inserted: 2 [input: 9] ->7 [R] ->8 [R] -> inserted: 9——————-

order traversal by level wise

——————-

7 7 8 3 9 0 7 3 5 2

You can download the document Here