What is Breadth First Search(BFS)?
It is an algorithm technique for traversing a tree, it is opposite of DFS, in BFS all the nodes at the next depth level are traversed at the same time it is similar to flood fill techniques or wave motion, where the motion is parallel and at the same speed.
Image Reference: Wikipedia
Breadth First Search Pseudocode
<![CDATA[Void Bfs(LinkedList<Integer> arr[], int source )
Initialize Queue Q;
Q.add(source);
Initialize Boolean array v to keep track of visited nodes
Mark source as visited
While(Q is not empty)
{
Source = Q.remove
Print source
While(iterate over arr[])
{
int k = iterated element
If k is not marked , mark k and add to queue}
}
]]>
Breadth First Search Implementation in Java
<![CDATA[import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class graph
{
public void initalize(LinkedList<Integer> arr[], int size)
{
for (int i = 0; i < size; i++)
{
arr[i] = new LinkedList<Integer>();
}
}
protected void add(int src, int dest, LinkedList<Integer> arr[])
{
arr[src].add(dest);
}
void display(LinkedList<Integer> arr[])
{
for (int i = 0; i < 6; i++)
{
Iterator<Integer> it = arr[i].iterator();
System.out.print(i + "-->");
while (it.hasNext())
{
System.out.print(it.next() + " ");
}
System.out.println();
}
}
void bfs(LinkedList<Integer> arr[], int n)
{
Queue<Integer> q = new LinkedList<Integer>();
boolean v[] = new boolean[6];
q.add(n);
v[n] = true;
while (!q.isEmpty())
{
n = q.poll();
System.out.println(n);
Iterator<Integer> it = arr[n].iterator();
while (it.hasNext())
{
int k = it.next();
if (!v[k])
{
q.add(k);
v[k] = true;
}
}
}
}
public static void main(String args[])
{
LinkedList<Integer> arr[] = new LinkedList[6];
graph s = new graph();
s.initalize(arr, 6);
s.add(0, 2, arr);
s.add(2, 0, arr);
s.add(0, 1, arr);
s.add(1, 2, arr);
s.add(2, 3, arr);
s.add(3, 3, arr);
s.bfs(arr, 1);
}
}
]]>
0 Upvotes
0 Downvotes
