Graph

Breathe First Search

Pinterest LinkedIn Tumblr

Data structure Description

Breadth First Search is an algorithm for searching the nodes in tree or graph data structures. It starts from the root node and explores the neighbor nodes first, before moving to the next level neighbors. If the solution is not far from the root, we can choose breadth-first search solution. If the solutions are far, it takes a lot of time to find the solution.

If there is more than one solution then Breadth First Search can find the minimal one that requires less number of steps. The major drawback of Breadth-first search is its memory requirement. It saves all the information about the traversal details in the memory.

Write a program to implement breadth-first search using a graph data structure?

Algorithm Explanation

Build the graph. Pass root node to the utility function.
If the search value is equal to the root value, return the root value. Otherwise, add the root node to the newly created queue.
Iterate all the elements from the graph. If the node is not visited, mark as visited and add to the queue.
If the node is equal to the current node, return the node.

Source Code

package com.dsacode.DataStructre.graph;
 
import java.util.LinkedList;
import java.util.Queue;
 
class GraphNode {
    int val;
    GraphNode next;
    GraphNode[] neighbors;
    boolean visited;
  
    GraphNode(int x) {
        val = x;
    }
  
    GraphNode(int x, GraphNode[] n){
        val = x;
        neighbors = n;
    }
  
    public String toString(){
        return this.val +" ";
    }
}
 
public class BreatheFirstSearch {
 
    public static void main(String[] args) {
     
            GraphNode n1 = new GraphNode(1);
            GraphNode n2 = new GraphNode(2);
            GraphNode n3 = new GraphNode(3);
            GraphNode n4 = new GraphNode(4);
            GraphNode n5 = new GraphNode(5);
      
            n1.neighbors = new GraphNode[]{n2,n3,n5};
            n2.neighbors = new GraphNode[]{n1,n4};
            n3.neighbors = new GraphNode[]{n1,n4,n5};
            n4.neighbors = new GraphNode[]{n2,n3,n5};
            n5.neighbors = new GraphNode[]{n1,n3,n4};
      
            System.out.print("Values from the Graph: ");
            breathFirstSearch(n1, 4);
        }
      
        public static void breathFirstSearch(GraphNode root, int x){
            if(root.val == x)
                System.out.println("find in root");
      
            Queue < GraphNode > queue = new LinkedList < GraphNode > ();
            root.visited = true;
            queue.add(root);
      
            while(queue.peek() != null){
                GraphNode c = (GraphNode) queue.poll();
                for(GraphNode n: c.neighbors){
      
                    if(!n.visited){
                        System.out.print(n + " ");
                        n.visited = true;
                        if(n.val == x)
                            System.out.println("\nFind the graph node: "+n);
                        queue.add(n);
                    }
                }
            }
        }
}  

Output

Values from the Graph: 2 3 5 4 
Find the graph node: 4

Write A Comment