package Graph;
import java.util.ArrayList;
import java.util.HashMap ;
import java.util.LinkedList ;
class GraphClient{
public static void main(String[] args){
Graph graph =new Graph();
graph.addVertex(“A”);
graph.addVertex(“B”);
graph.addVertex(“C”);
graph.addVertex(“D”);
graph.addVertex(“E”);
graph.addVertex(“G”);
graph.addEdge("A","B",2);
graph.addEdge("A","D",3);
graph.addEdge("B","C",1);
graph.addEdge("C","D",8);
graph.addEdge("D","E",10);
graph.addEdge("E","F",45);
graph.addEdge("E","G",7);
graph.addEdge("F","G",8);
graph.display();
// System.out.println(graph.numVertex());
// System.out.println(graph.numEdges());
// System.out.println(graph.containsEdge("A","C") );
// System.out.println(graph.containsEdge("E","F") );
// graph.removeEdge("A","B");
// graph.display();
// graph.removeVertex("F") ;
// graph.display();
// graph.addVertex("F") ;
// graph.display();
// graph.addEdge("F","A",10) ;
// graph.display();
// print HashMap code
// System.out.println(graph.hashPath("A","F",new HashMap<>()));
//print BFS
System.out.println(graph.pfs("A","F"));
}
}
public class Graph
{
public boolean pfs(String a, String f) {
private class Vertex{
HashMap<String,Integer> nbrs =new HashMap<>() ;
}
HashMap <String,Vertex > vtces;
public Graph (){
vtces =new HashMap<>() ;
}
public int numVertex()
{
return this.vtces.size();
}
public boolean containsVertex(String vname){
return this.vtces.containsKey(vname) ;
}
public void addVertex(String vname){
Vertex vtx=new Vertex() ;
vtces.put(vname ,vtx );
}
public void removeVertex(String vname) {
Vertex vtx = vtces.get(vname);
ArrayList keys = new ArrayList<>(vtx.nbrs.keySet());
for (String key : keys) {
Vertex nbrVtx = vtces.get(key);
nbrVtx.nbrs.remove(vname);
}
vtces.remove(vname);
}
public int numEdges(){
int count =0;
ArrayList<String>keys= new ArrayList<>(vtces.keySet());
for(String key:keys) {
Vertex vtx = vtces.get(key);
count = count + vtx.nbrs.size();
}
return count/2;
}
public boolean containsEdge(String vname1,String vname2){
Vertex vtx1=vtces.get(vname1);
Vertex vtx2=vtces.get(vname2);
if(vtx1 ==null || vtx2 ==null ||!vtx1.nbrs.containsKey(vname2)){
return false;
}
return true;
}
public void addEdge(String vname1,String vname2,int cost){
Vertex vtx1=vtces.get(vname1); //2k
Vertex vtx2=vtces.get(vname2); //4k
if(vtx1 ==null || vtx2 ==null ||vtx1.nbrs.containsKey(vname2)){
return ;
}
vtx1.nbrs.put(vname2,cost); //2k nbrs put C with a given cost
vtx2.nbrs.put(vname1,cost); //4k nbrs put A with a given cost
}
public void removeEdge(String vname1,String vname2){
Vertex vtx1=vtces.get(vname1); //2k
Vertex vtx2=vtces.get(vname2); //4k
if(vtx1 ==null || vtx2 ==null ||!vtx1.nbrs.containsKey(vname2)){
return ;
}
vtx1.nbrs.remove(vname2); //2k nbrs remove C
vtx2.nbrs.remove(vname1); //4k nbrs remove A
}
public void display(){
System.out.println(“");
ArrayListkeys =new ArrayList<>(vtces.keySet());
for(String key :keys){
Vertex vtx =vtces.get(key);
System.out.println(key + “:” +vtx.nbrs);
}
System.out.println("”);
}
//part3
public boolean hashPath(String vname1,String vname2 ,HashMap<String,Boolean >processed){
processed.put(vname1,true);
//direct edge
if(containsEdge(vname1 ,vname2 )){
return true ;
}
Vertex vtx =vtces.get(vname1);
ArrayList<String> nbrs =new ArrayList<>(vtx.nbrs.keySet());
for(String nbr :nbrs){
if(!processed .containsKey(nbr) && hashPath(nbr,vname2 ,processed )){
return true;
}
}
return false;
}
//part4
//Graph BFS
private class Pair{
String vname;
String psf;
}
public boolean bsf(String src,String dst){
HashMap<String,Boolean > processed =new HashMap<>() ;
LinkedList<Pair> queue =new LinkedList<>() ;
//create a new pair
Pair sp= new Pair();
sp.vname =src;
sp.psf =src;
//put the new Pair in Queue
queue.addLast(sp);
//while queue is not empty keep on doing the work
while(!queue.isEmpty()){
// remove a pair from queue
Pair rp= queue.removeFirst() ;
if(processed.containsKey(rp.vname ) ){
continue;
}
// processed put
processed .put(rp.vname,true);
//de
if(containsEdge(rp.vname,dst)){
System.out.println(rp.psf+dst);
return true;
}
//nbrs
Vertex rpvtx =vtces.get(rp.vname);
ArrayList<String> nbrs =new ArrayList<>(rpvtx.nbrs.keySet());
//loop on nbrs
for(String nbr :nbrs){
// process only unprocessed nbrs
if(!processed.containsKey(nbr)){
//make a new pair of nbr and put in queue
Pair np= new Pair();
np.vname =nbr;
np.psf =rp.psf+nbr;
queue .addLast(np);
}
}
}
return false ;
}
}
BFS program not run please resolve my questions