IT2EDU Empowering Education Through Technology
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(bd + 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(bd)
Worst Case complexity: O(|V|)O ( | V | + | E | ) {\displaystyle O(|V|+|E|)} = O(bd)
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
