Graph_BSF_Shortest_Cycle
import java.util.*;
class AdjacencyGraph{
int matrix[][] = new int[10][10];
public void createEdge(int s, int e, int w){
matrix[s][e] = w;
}
public void showGraph(){
System.out.println("Size of Graph: "+matrix.length) ;
for(int i=0;i<=5;i++){
for(int j=0;j<=5;j++){
System.out.print(matrix[i][j]+" ");
}
System.out.println();
}
}
public void BSF(int start){
int queue[] = new int[10];
boolean visited[] = new boolean[10];
visited[start] = true;
int rear = -1,front=0,i;
queue[++rear] = start;
for(front=0;front <=rear;front++){
for(i=0;i<matrix.length;i++){
if(matrix[queue[front]][i]!=0){
if(visited[i]!=true){
queue[++rear] = i;
visited[i] = true;
}else if(visited[i]== true){
for(int j=0;j<queue.length;j++){
if(queue[j]== i)
System.out.println("Cycle Found!!!");
}
}
}
}
}
for(i=0;i<=rear;i++){
System.out.println(" "+queue[i]);
}
}
public void dijkstra(){
int v = matrix.length;
boolean visited[] = new boolean[v];
int distance[] = new int[v];
distance[0] = 0;
for(int i=1;i<v;i++){
distance[i] = Integer.MAX_VALUE;
}
for(int i=0;i<v-1;i++){
int minVertex = minVertex(distance,visited);
System.out.println("Min Vertext: "+minVertex);
visited[minVertex] = true;
//explore neighbors
for(int j=0;j<v;j++){
if(matrix[minVertex][j]!=0 && !visited[j] && (distance[minVertex]!=Integer.MAX_VALUE)){
int newDist = distance[minVertex]+matrix[minVertex][j];
if(newDist < distance[j]){
distance[j] = newDist;
}
}
}
}
for(int i=0;i<v-1;i++){
System.out.println(i+" "+distance[i]);
}
}
public int minVertex(int[] distance,boolean[] visited){
int minVertex = -1;
for(int i=0;i<distance.length;i++){
if(!visited[i] &&(minVertex == -1 || distance[i] < distance[minVertex])){
minVertex = i;
}
}
return minVertex;
}
public void showAdjacent(int vertex){
for(int i=0;i<5;i++){
if(matrix[vertex][i]!=0)
System.out.println("Adjacents: "+i);
}
}
public void showInDegree(int vertex){
int count = 0;
for(int i=1;i<matrix.length;i++){
if(matrix[i][vertex]!=0){
++count;
}
}
System.out.println("In Degree of "+vertex+" is "+count);
}
}
class AdjacencyGraphDemo{
public static void main(String[] args){
AdjacencyGraph gg = new AdjacencyGraph();
gg.createEdge(0,1,3);
gg.createEdge(0,2,4);
gg.createEdge(0,3,5);
gg.createEdge(3,4,4);
gg.BSF(0);
AdjacencyGraph g = new AdjacencyGraph();
g.createEdge(0,1,4);
g.createEdge(1,0,4);
g.createEdge(0,2,8);
g.createEdge(2,0,8);
g.createEdge(1,3,5);
g.createEdge(3,1,5);
g.createEdge(1,2,2);
g.createEdge(2,1,2);
g.createEdge(2,4,9);
g.createEdge(4,2,9);
g.createEdge(2,3,5);
g.createEdge(3,2,5);
g.createEdge(4,3,4);
g.createEdge(3,4,4);
//System.out.println("Shortest path");
g.showGraph();
g.dijkstra();
g.showAdjacent(3);
//g.detectCycle(0);
System.out.println("BSF Traversal");
g.BSF(0);
AdjacencyGraph dg = new AdjacencyGraph();
dg.createEdge(1,2,5);
dg.createEdge(3,2,4);
dg.createEdge(3,4,3);
dg.createEdge(4,1,2);
dg.createEdge(5,2,2);
dg.createEdge(5,1,2);
dg.createEdge(4,1,2);
dg.showGraph();
dg.showInDegree(2);
AdjacencyGraph d1 = new AdjacencyGraph();
d1.createEdge(1,2,3);
d1.createEdge(1,3,3);
d1.createEdge(1,4,3);
d1.createEdge(4,5,3);
d1.createEdge(2,6,3);
d1.createEdge(3,6,3);
d1.BSF(1);
}
}