Graph in Java
Solving Graph in Java
import java.util.*;
class Graph {
LinkedList list[] ;
public Graph(int V){
list = new LinkedList[V];
for(int i=0;i V;i++)
list[i] = new LinkedList();
}
void addEdge(int source , int destination){
list[source].add(destination);
list[destination].add(source);
}
public int bfs(int source , int destination){
boolean visited[] = new boolean[list.length];
int parent[] = new int[list.length];
Queue q = new LinkedList<>();
q.add(source);
parent[source] = -1;
visited[source] = true;
while(!q.isEmpty()){
int curr = q.poll();
if(curr == destination) break;
for(int neighbor : list[curr]){
if(!visited[neighbor]){
visited[neighbor] = true;
q.add(neighbor);
parent[neighbor] = curr;
}
}
}
int cur = destination;
int distance = 0;
while(parent[cur] != -1) {
System.out.print(cur+" -> ");
cur = parent[cur];
distance++;
}
return distance;
}
}
class solution
{
static Scanner input = new Scanner(System.in);
public static void main(String[] args) {
System.out.println("Enter Number of vertices and edges : ");
int vertices = input.nextInt();
int edges = input.nextInt();
Graph g = new Graph(vertices);
System.out.println("Enter "+edges+" edges");
for(int i=0;i edges;i++){
int source = input.nextInt();
int destination = input.nextInt();
g.addEdge(source,destination);
}
System.out.println("Enter to source and destination to find distance");
int a = input.nextInt();
int b = input.nextInt();
int B = g.bfs(a,b);
}
}