Untitled

mail@pastecode.io avatar
unknown
java
7 months ago
3.8 kB
59
Indexable
Never
import java.util.ArrayList;
import java.util.LinkedList;

import BSTPractice.TreeNode;
class Graph {
    public static void addEdge(int u, int v, ArrayList<Integer>[] graph){
        graph[u].add(v);
        graph[v].add(u);
    }

    public static void BFS(int src, ArrayList<Integer>[] graph){
        LinkedList<Integer> que = new LinkedList<>();

        boolean[] vis = new boolean[graph.length];
        que.addLast(src);
        System.out.print(src+" ");
        vis[src] = true;

        while(que.size()>0){
            int vtx = que.removeFirst();

            ArrayList<Integer> nbrs = graph[vtx];
            for(int i=0; i<nbrs.size(); i++){
                int nbr = nbrs.get(i);
                if(vis[nbr]==false){
                    que.addLast(nbr);
                    vis[nbr] = true;
                    System.out.print(nbr+" ");
                }
            }
        }
    }

    public static void BFS2(int src, ArrayList<Integer>[] graph){
        LinkedList<Integer> que = new LinkedList<>();

        int level = 0;
        boolean[] vis = new boolean[graph.length];

        que.addLast(src);
        vis[src] = true;

        while(que.size()>0){
            int size = que.size();
            System.out.print(level+" -> ");

            while(size-- > 0){
                int vtx = que.removeFirst();
                System.out.print(vtx+" ");

                for(int nbr:graph[vtx]){
                    if(vis[nbr]==false){
                        que.addLast(nbr);
                        vis[nbr] = true;
                    }
                }
            }
            level++;
            System.out.println();
        }
    }

    public static boolean isCycle(int src, ArrayList<Integer>[] graph){
        LinkedList<Integer> que = new LinkedList<>();

        int level = 0;
        boolean isCycle = false;
        boolean[] vis = new boolean[graph.length];

        que.addLast(src);
       

        while(que.size()>0){
            int size = que.size();

            while(size-- > 0){
                int vtx = que.removeFirst();

                if(vis[vtx] == true){
                    System.out.println("There is a cycle in this graph");
                    isCycle = true;
                    continue;
                }

                vis[vtx] = true;

                for(int nbr:graph[vtx]){
                    if(vis[nbr]==false){
                        que.addLast(nbr);
                    }
                }
            }
            level++;
            System.out.println();
        }

        return isCycle;
    }

    public static int minDepth(TreeNode root){
        int level = 0;
        LinkedList<TreeNode> que = new LinkedList<>();

        que.addLast(root);

        while(que.size()>0){
            int size = que.size();

            while(size-- > 0){
                TreeNode node = que.removeFirst();

                if(node.left == null && node.right == null){ // leaf node 
                    return level;
                }

                if(node.left!=null){
                    que.addLast(node.left);
                }
                if(node.right!=null){
                    que.addLast(node.right);
                }
            }
            level++;
        }
    }
    public static void main(String[] args) {
        ArrayList<Integer>[] graph = new ArrayList[8];

        for(int i=0; i<graph.length; i++){
            graph[i] = new ArrayList<>();
        }

        addEdge(0,1,graph);
        addEdge(0,7,graph);
        addEdge(0,3,graph);
        addEdge(1,2,graph);
        addEdge(3,2,graph);
        addEdge(3,4,graph);
        addEdge(4,6,graph);
        addEdge(4,5,graph);
        addEdge(5,6,graph);

        isCycle(0,graph);
    }
}