Breadth First Search (BFS) Pseudocode and Program in Java

[7134 views]



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.


Breadth First Search Pseudocode or Algorithm

Image Reference: Wikipedia


Breadth First Search Pseudocode

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

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); } }
        




Getting any Errors while coding? Ask us on our new Forum:




Liked Article? Please Buy Author a Coffee


Comments



Search
For Sponsored Advertisement OR Freelance Programming Article Submission, Contact us at atechdailyweb@gmail.com
Recommended Deal Ends in











Quizzes:
Online Games
Play 2048 Game Online and Relax.
Play 2048 Game Online

Why does everyone hate Java?
How much JavaScript to learn for Web Development
How to Convert EPOCH to Date in Java
Search Tags

    Breadth First Search Pseudocode in Java

    Breadth First Search Algorithm in Java

    BFS with example