20. Problems on Graph - I

import java.util.ArrayList;

import java.util.Stack;

import java.util.PriorityQueue;

class Graph {

    private boolean isCycleInUndirected(ArrayList<Edge> graph[], boolean visited[], int root, int parent) {

        visited[root] = true;

        for (Edge edge : graph[root]) {

            if (!visited[edge.dest]) {

                if (isCycleInUndirected(graph, visited, edge.dest, root))

                    return true;

            } else if (parent != edge.dest)

                return true;

        }

        return false;

    }

    void isCycleUndirected(ArrayList<Edge> graph[]) {

        boolean visited[] = new boolean[graph.length];

        for (int i = 0; i < graph.length; i++)

            if (!visited[i])

                if (isCycleInUndirected(graph, visited, i, -1)) {

                    System.out.println("Cycle Detected...");

                    break;

                }

        System.out.println("Cycle Not Detected...");

    }

    private boolean isCycleInDirected(ArrayList<Edge> graph[], boolean visited[], int root, boolean stack[]) {

        visited[root] = true;

        stack[root] = true;

        for (Edge edge : graph[root]) {

            if (stack[edge.dest])

                return true;

            else if (!visited[edge.dest])

                return isCycleInDirected(graph, visited, edge.dest, stack);

        }

        stack[root] = false;

        return false;

    }

    void isCycleDirected(ArrayList<Edge> graph[]) {

        boolean visited[] = new boolean[graph.length];

        for (int i = 0; i < graph.length; i++)

            if (!visited[i])

                if (isCycleInDirected(graph, visited, i, new boolean[graph.length])) {

                    System.out.println("Cycle Detected...");

                    break;

                }

        System.out.println("Cycle Not Detected...");

    }

    void allPaths(ArrayList<Edge> graph[], boolean visited[], String path, int root, int tar) {

        if (root == tar) {

            System.out.println(path);

            return;

        }

        if (!visited[root]) {

            visited[root] = true;

            for (Edge edge : graph[root])

                allPaths(graph, visited, path + edge.dest, edge.dest, tar);

            visited[root] = false;

        }

    }

    private void topologicalSorting(ArrayList<Edge> graph[], boolean visited[], int root, Stack<Integer> stack) {

        visited[root] = true;

        for (Edge edge : graph[root])

            if (!visited[edge.dest])

                topologicalSorting(graph, visited, edge.dest, stack);

        stack.push(root);

    }

    Stack<Integer> topologicalSort(ArrayList<Edge> graph[]) {

        Stack<Integer> stack = new Stack<>();

        boolean visited[] = new boolean[graph.length];

        for (int i = 0; i < graph.length; i++)

            if (!visited[i])

                topologicalSorting(graph, visited, i, stack);

        return stack;

    }

    void dijkstraAlgo(ArrayList<Edge> graph[], int root) {

        PriorityQueue<Pair> priorityQueue = new PriorityQueue<>();

        priorityQueue.add(new Pair(root, root, 0));

        boolean visited[] = new boolean[graph.length];

        int dist[] = new int[graph.length];

        for (int i = 0; i < dist.length; i++)

            if (i != root)

                dist[i] = Integer.MAX_VALUE;

        while (!priorityQueue.isEmpty()) {

            Pair curr = priorityQueue.remove();

            visited[curr.dest] = true;

            for (Edge edge : graph[curr.dest])

                if (!visited[edge.dest])

                    if (dist[edge.dest] > dist[edge.src] + edge.wgt) {

                        dist[edge.dest] = dist[edge.src] + edge.wgt;

                        priorityQueue.add(new Pair(edge.src, edge.dest, dist[edge.dest]));

                    }

        }

        for (Integer distance : dist)

            System.out.print(distance + " ");

    }

    void bellmanFordAlgo(ArrayList<Edge> graph[], int root) {

        int dist[] = new int[graph.length];

        for (int i = 0; i < dist.length; i++)

            if (i != root)

                dist[i] = Integer.MAX_VALUE;

        for (int i = 0; i < graph.length - 1; i++)

            for (int j = 0; j < graph.length; j++)

                for (Edge edge : graph[j])

                    if (dist[edge.src] != Integer.MAX_VALUE && dist[edge.dest] > dist[edge.src] + edge.wgt)

                        dist[edge.dest] = dist[edge.src] + edge.wgt;

        for (Integer distance : dist)

            System.out.print(distance + " ");

    }

    void prismAlgo(ArrayList<Edge> graph[], int root) {

        PriorityQueue<Pair> queue = new PriorityQueue<>();

        boolean visited[] = new boolean[graph.length];

        ArrayList<Edge> mst = new ArrayList<>();

        queue.add(new Pair(root, root, 0));

        while (!queue.isEmpty()) {

            Pair curr = queue.remove();

            if (!visited[curr.dest]) {

                visited[curr.dest] = true;

                mst.add(new Edge(curr.src, curr.dest, curr.dist));

                for (Edge edge : graph[curr.dest])

                    queue.add(new Pair(edge.src, edge.dest, edge.wgt));

            }

        }

        mst.remove(0);

        System.out.println("Source\tDestination\tWeight");

        for (Edge edge : mst)

            System.out.println("  " + edge.src + "\t    " + edge.dest + "\t\t  " + edge.wgt);

    }

}