Breaking
Graph

# Breathe First Search

## 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?

## Source Code

```package com.dsacode.DataStructre.graph;

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;

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);
```Values from the Graph: 2 3 5 4