Skip to main content

BREADTH FIRST SEARCH IN JAVA

BREADTH FIRST SEARCH IN JAVA:-


package com.problems.graph;

import java.awt.DisplayMode;
import java.util.Iterator;
import java.util.LinkedList;




public class BFSGraph {

 int maxsize;
 Vertex vertexlist[];
 int matrixlist[][];
 int vertexcount;
 @SuppressWarnings({ "rawtypes", "unused" })
 LinkedList queue;
 
 public BFSGraph()
 {
  maxsize=20;
  matrixlist=new int[maxsize][maxsize];
  vertexlist=new Vertex[maxsize];
  for(int i=0;i<maxsize;i++)
  {
   for(int j=0;j<maxsize;j++)
   {
    matrixlist[i][j]=0;
   }
  }
  queue= new LinkedList();
  
 }
 
 public void addVertex(char label)
 {
  vertexlist[vertexcount++]=new Vertex(label);
 }
 public void addEdge(int i,int j)
 {
  matrixlist[i][j]=1;
  matrixlist[j][i]=1;
 }
 
 public void displayVertex(int v)
 {
  System.out.println(vertexlist[v].label);
 }
 
 public int adjVertex(int v)
 {
  for(int i=0;i<maxsize;i++)
  {
   if(matrixlist[v][i]==1 && vertexlist[i].visited==false )
    return i;
  }
  return -1;
 }
 
 public void bfs()
 {
  System.out.println("in bfs");
  vertexlist[0].visited=true;
  displayVertex(0);
  queue.add(0);
  int v2;
  while(!queue.isEmpty())
  {
   int v1=(Integer) queue.remove();
   System.out.println("removed"+v1);
   while( (v2=adjVertex(v1))!=-1)
   {
   vertexlist[v2].visited=true;
   displayVertex(v2);
   queue.add(v2);
   }
  }
  for(int j=0;j<vertexcount;j++)
  {
   vertexlist[j].visited=false;
  }
 }
}

Comments

.

Popular posts from this blog

How to design a Node in Tree?

How to design a Node in Tree?

There are three main components of a tree in a node.

 1) Integer holding data.
2) Left pointer holding node in a left subtree.
3) Right pointer holding node in a right subtree.

The following design is having data of int type and left,right pointers of a node to the subtrees.


package com.BST;publicclassNode{int data; Node left; Node right;/** * @return the data */publicNode(int data){this.left=null;this.right=null;this.data=data;}publicintgetData(){return data;}/** * @param data the data to set */publicvoidsetData(int data){this.data= data;}/** * @return the left */public Node getLeft(){return left;}/** * @param left the left to set */publicvoidsetLeft(Node left){this.left= left;}/** * @return the right */public Node getRight(){return right;}/** * @param right the right to set */publicvoidsetRight(Node right){this.right= right;}/* (non-Javadoc) * @see java.lang.Object#toString() */@Overridepublic String toString(){return"Node [data=&quo…

Heap implementation in JAVA

In this tutorial we will see all the functionalities of heaps implemented through java language.



package com.problems.heap;publicclassHeapFunctions{//Function to generate maxheapify where root is max than childspublicvoidmaxHeapify(int Arr[],int i,int N){int largest;int left =2*i+1;//left childint right =2*i +2;//right child System.out.println("left"+" "+left); System.out.println("right"+" "+right); System.out.println("Max size"+" "+N);if(left< N && Arr[left]> Arr[i]){ largest = left; System.out.println("largest left"+largest);}else{ largest = i; System.out.println("largest i"+largest);}if(right < N && Arr[right]> Arr[largest]){ largest = right; System.out.println("largest right"+largest);}if(largest != i ){ System.out.println("No largest"+largest); Arr=swap (A…