Online-Academy
Look, Read, Understand, Apply

Data Structure

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);
    }
}