Breadth First Search (BFS) Pseudocode and Program in Java

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

Solution Worked 0 UpvotesUpvote

        

Solution Didn't Worked 0 DownvotesDownvote



Comments



Search


Search Tags

    Breadth First Search Pseudocode in Java

    Breadth First Search Algorithm in Java

    BFS with example