Skip to main content

Breadth First Search Implementation in Java


Breadth First Search Implementation in Java

For Graph Class Design and DFS implementation please refer to below link:-

depth-first-search-implementation-in-java


 
/*

1. Pick a vertex.
2. Get Adjacent Vertex.
3. Insert in queue ( at tail)
4. Remove vertex from queue( head)
5. Do until no vertex left in a queue.

*/ 

void searchBFS()
 {
//this is how we define queue using LinkedList
  Queue<Character> queue=new LinkedList<Character>();
  
  queue.add(vertexlist[0].label);
  
  
 
  
  while(!queue.isEmpty())
  {
  
                 //element at head (Function in main graph class please use above link)
  ArrayList adjvertex=getNeighbours(queue.peek());
  System.out.println(queue.peek());
              //element removed at head
  queue.remove();
 
        if(adjvertex!=null)
  {
  for(int i=0;i<adjvertex.size();i++)
  {
               //element added at tail  
   queue.add((Character) adjvertex.get(i));
  }
  }
  }
  
  
 }

Comments

.

Popular posts from this blog

Driver program to perform operations in graph

Driver program to perform operations in graph:-



package com.problems.graph;publicclassGraphDriver{publicstaticvoidmain(String[] args){ BFSGraph g=new BFSGraph(); g.addVertex('A'); g.addVertex('B'); g.addVertex('C'); g.addVertex('D'); g.addVertex('E'); g.addVertex('F'); g.addVertex('G'); g.addVertex('H'); g.addEdge(0,1); g.addEdge(1,2); g.addEdge(1,7); g.addEdge(2,3); g.addEdge(2,4); g.addEdge(7,4); g.addEdge(4,5); g.addEdge(4,6); g.bfs();}}

Shortest Path from source to Vertex :- Dijkstra Algorithm

Shortest Path from source to Vertex :- Dijkstra Algorithm:-

Dijkstra Algorithms is an algorithm use to find the shortest path from source vertex to a given vertex.



package Graph;importjava.util.HashMap;abstractpublicclassDirectedGraph{ Vertex[] vertexlist=new Vertex[10]; HashMap<Character,HashMap<Character,Integer>> edgelist=new HashMap<>(); Vertex vertex;//count of vertex and edgestaticint vertexcount=0;int edgecount=0;/* * This function takes a label and insert in the vertex list as well as edge list since it is new vertex it will add * null to its adjoining vertices */intaddVertex(char label){ vertex=new Vertex(label); vertexlist[vertexcount]=vertex; System.out.println(vertexlist[vertexcount].label); edgelist.put(vertex.label,null); vertexcount++;return vertexcount;}intaddEdge(char label,char[] labels,int[] distances){ HashMap<Character,Integer> vertexlist=new HashMap<>();for(int i=0;i<labels.length;i++){ vertexlist.put(labels[i],…