Concepts of Computer Science

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 ; import java.util.HashMap ; abstract public class DirectedGraph { Vertex [] vertexlist = new Vertex [ 10 ]; HashMap < Character , HashMap < Character , Integer >> edgelist = new HashMap <>(); Vertex vertex ; //count of vertex and edge static int 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 */ int addVertex ( char label ) { vertex = new Vertex ( label ); vertexlist [ vertexcount ]= vertex ; System . out . println ( vertexlist [ vertexcount ]. label ); edgelist . put ( vertex . label , null ); vertexcount ++; return vertexcount ; } int addEdge ( char label , char ...

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 ...

Depth First Search Implementation in Graph -- Graph //This is a class to define the vertex in a graph public class Vertex { char label ; boolean visited ; public Vertex ( char label ){ this . label = label ; this . visited = false ; } package Graph ; import java.util.ArrayList ; import java.util.HashMap ; import java.util.Iterator ; import java.util.Map ; import java.util.Map.Entry ; // this class is abstract because we won't allow you make instance of it , it is of no use until not extended abstract public class GraphBase { //declaring instance of vertex Vertex vertex ; //declaring an array of vertex to hold all the vertex static Vertex [] vertexlist = new Vertex [ 10 ]; //declaring edgelist to hold all edges key is vertex value is neighbouring vertex static HashMap < Character , ArrayList < Character >> edgelist = new HashMap <>(); //count of vertex and edge static int ...

Driver program to perform operations in graph:- package com . problems . graph ; public class GraphDriver { public static void main ( 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 (); } }

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 ( vertexlis...

DEPTH FIRST SEARCH IN JAVA public void dfs () { vertex [ 0 ]. visited = true ; displyVertex ( 0 ); stackobj . push ( 0 ); while (! stackobj . isEmpty ()) { int v = adjVertex (( Integer ) stackobj . peek ()); if ( v ==- 1 ) { stackobj . pop (); } else { vertex [ v ]. visited = true ; displyVertex ( v ); stackobj . push ( v ); } } }

How to design a Graph in JAVA:- Vertex:- package com . problems . graph ; public class Vertex { char label ; boolean visited ; public Vertex ( char label ){ this . label = label ; this . visited = false ; } } Functions of Graphs public class Graph { int maxsize = 20 ; Vertex vertex []; int matrix [][]; int vertexcount ; Stack stackobj ; public Graph () { vertex = new Vertex [ maxsize ]; matrix = new int [ maxsize ][ maxsize ]; vertexcount = 0 ; for ( int i = 0 ; i < maxsize ; i ++) { for ( int j = 0 ; j < maxsize ; j ++) { matrix [ i ][ j ]= 0 ; } } stackobj = new Stack (); } public void addVertex ( char label ) { vertex [ vertexcount ++]= new Vertex ( label ); } public void addEdge ( int i , int j ) { matrix [ i ][ j ]= 1 ; matrix [ j ][ i ]= 1 ; } public void displyVertex ( int v ) { System . out . println ( vertex [ v ]....