Graph

Directed vs UnDirected Graph

Directed Graph

• Degree = no. edges from a graph
• Sum of degrees = 2 x | no of edges |
• max number of edge = [ v * (v-1) ]/2

Undirected Graph

• Degree = in-degree + out-degree
• Sum of in-degree = | no of edges |
• Sum of out-degree = | no of edges |
• max number of edge = v * (v-1)

Concepts on graph

• Walk (sometimes path) : from going one edge to another via connected edges
• v1 -> v2 -> v4 -> v2
• if no edge exists between 2 vertices, you cannot walk directly
• Path (simple path) : a walk without repeated vertices allowed
• Degree : all edges to vertices
• in-degree : directed graph incoming edges
• out-degree : directed graph outgoing edges
• Cyclic : if the walk starts and ends on the same vertices
• they can directed and undirected
• Acyclic :
• Undirected acyclic graph (UDAG)
• Directed acyclic graph (DAG)
• Weighted graph : edges with some weight assigned to it
• unweighted graph : simple edges

Adjacency Matrix vs List

Adjacency Matrix

adjacency matrix : undirected graph

• If the diagonal of matrix is 0 and upper and lower triangle are symmetric, then it is a undirected graph
• size of matrix = |v|x|v|
• If graph is not symmetric , then it is a directed graph

adjacency matrix : directed graph

• space required : |v|x|v|
• check if u & v are adj : O(1)
• find all vertices : O(v) : simple matrix row traversal
• adding/removing edges : O(1)

Adjacency Matrix List

adjacency list undirected graph

adjacency list directed graph

• space required : O(V+E)
• undirected : V+2E
• directed : V+E
• check if there is a edge from u to v : O(v)
• find all adjacency of u : O(degree(u))
• Find degree of u : O(1)
• Add an edge : O(1)
• remove and edge : O(v)

Applications of DFS vs BFS

Applications of Breadth First Search

• Shortest Path in unweighted graph
• Crawler in Search Engine
• Peer to Peer network
• Social Networking Search
• In garbage collection (Cheney's Algorithm)
• Cycle Detection
• Ford Fulkerson Algorithm
• Broadcasting

Applications of Depth First Search

• Cycle Detection
• Topological Sorting
• Solving Maze and Puzzle Problems
• Path Finding

Adjacency List implementation in Java

import java.util.*;

class Graph {

    static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);
    }

    static void printGraph(ArrayList<ArrayList<Integer>> adj) {
        for (int i = 0; i < adj.size(); i++) {
            for (int j = 0; j < adj.get(i).size(); j++) {
                System.out.print(adj.get(i).get(j) + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int V = 4;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(V);

        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<Integer>());

        // Adding edges one by one
        addEdge(adj, 0, 1); addEdge(adj, 0, 2);
        addEdge(adj, 1, 2); addEdge(adj, 1, 3);

        printGraph(adj);
    }
}

Breadth First Search Graph Traversal

How it works

• create a queue to maintain elements for breadth first search
• to avoid repeating the visited nodes in cyclic graph, create a boolean array of size |v| to mark array[i] as true/false indicating visited status
• CODE FOR BFS disconnected graph is same

Disconnected Graph: How it works

• same as BFS, the algorithm is called for every node assuming it is the source vertice of the disconnected graph.
• we keep track of visited vertices in an boolean array just like BFS but this visited array is passed from source caller to BFS algorithm (in Java : array is pass by reference)
• this visited array will avoid calling BFS for nodes of island as they would have been visited

To count the number of island in graph

• keep track of island source with counter
• every islands nodes will be ignored as they will be marked as visited by BFS

import java.util.*;

class Graph {

    static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);
    }

    static void BFS(ArrayList<ArrayList<Integer>> adj, int s, boolean[] visited) {
        Queue<Integer> q = new LinkedList<>();

        visited[s] = true;
        q.add(s);

        while (q.isEmpty() == false) {
            int u = q.poll();
            System.out.print(u + " ");

            for (int v : adj.get(u)) {
                if (visited[v] == false) {
                    visited[v] = true;
                    q.add(v);
                }
            }
        }
    }

    static void BFSDin(ArrayList<ArrayList<Integer>> adj, int V) {
        boolean[] visited = new boolean[V];
        int count = 0;        // for counting number of islands
        for (int i = 0; i < V; i++)
            visited[i] = false;
        for (int i = 0; i < V; i++) {
            if (visited[i] == false) {
                BFS(adj, i, visited);
                count++;    // every islands source will be counted, as
                            // its nodes will be marked visited by BFS
            }
        }
    }

    public static void main(String[] args) {
        int V = 7;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(V);

        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<Integer>());

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

        System.out.println("Following is Breadth First Traversal: ");
        BFSDin(adj, V);
    }
}

Depth First Search

How it works

• Depth first search is achieved with recursion just like tree
• To avoid cyclic loops, a boolean array containing visited nodes is maintain and passed in the recursion

Disconnected Graph: How it works

• same as BFS, the algorithm is called for every node assuming it is the source vertice of the disconnected graph.
• we keep track of visited vertices in an boolean array just like DFS but this visited array is present in recursion call from source caller to DFS algorithm (in Java : array is pass by reference)
• this visited array will avoid calling DFS for nodes of island as they would have been visited

import java.util.*;

class Graph {

    static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);
    }

    static void DFSRec(ArrayList<ArrayList<Integer>> adj, int s, boolean[] visited) {
        visited[s] = true;
        System.out.print(s + " ");

        for (int u : adj.get(s)) {
            if (visited[u] == false)
                DFSRec(adj, u, visited);
        }
    }

    static void DFS(ArrayList<ArrayList<Integer>> adj, int V) {
        boolean[] visited = new boolean[V];
        int count = 0;

        for (int i = 0; i < V; i++)
            visited[i] = false;

        // for include disconnected graphs as well
        for (int i = 0; i < V; i++) {
            if (visited[i] == false) {
                DFSRec(adj, i, visited);
                count++;
            }
        }
    }

    public static void main(String[] args) {
        int V = 5;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(V);

        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<Integer>());

        addEdge(adj, 0, 1); addEdge(adj, 0, 2); addEdge(adj, 1, 2);
        addEdge(adj, 3, 4);

        System.out.println("Following is Depth First Traversal for disconnected graphs: ");
        DFS(adj, V);
    }
}

------------

BFS : Shortest Path in an Unweighted Graph

import java.util.*;

class Graph {

    static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);
    }

    static void BFS(ArrayList<ArrayList<Integer>> adj, int V, int s, int[] dist) {
        boolean[] visited = new boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        Queue<Integer> q = new LinkedList<>();

        visited[s] = true;
        q.add(s);

        while (q.isEmpty() == false) {
            int u = q.poll();

            for (int v : adj.get(u)) {
                if (visited[v] == false) {
                    dist[v] = dist[u] + 1;
                    visited[v] = true;
                    q.add(v);
                }
            }
        }
    }

    public static void main(String[] args) {
        int V = 4;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(V);

        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<Integer>());

        addEdge(adj, 0, 1);
        addEdge(adj, 1, 2);
        addEdge(adj, 2, 3);
        addEdge(adj, 0, 2);
        addEdge(adj, 1, 3);
        int[] dist = new int[V];
        for (int i = 0; i < V; i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        dist[0] = 0;
        BFS(adj, V, 0, dist);

        for (int i = 0; i < V; i++) {
            System.out.print(dist[i] + " ");
        }
    }
}

DFS : Detect Cycle in Undirected Graph

import java.util.*;

class Graph {

    static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);
    }

    static boolean DFSRec(ArrayList<ArrayList<Integer>> adj, int s, boolean[] visited, int parent) {
        visited[s] = true;

        for (int u : adj.get(s)) {
            if (visited[u] == false) {
                if (DFSRec(adj, u, visited, s) == true) {
                    return true;
                }
            } else if (u != parent) {
                return true;
            }
        }
        return false;
    }

    static boolean DFS(ArrayList<ArrayList<Integer>> adj, int V) {
        boolean[] visited = new boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        for (int i = 0; i < V; i++) {
            if (visited[i] == false)
                if (DFSRec(adj, i, visited, -1) == true)
                    return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int V = 6;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(V);

        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<Integer>());

        addEdge(adj, 0, 1);
        addEdge(adj, 1, 2);
        addEdge(adj, 2, 4);
        addEdge(adj, 4, 5);
        addEdge(adj, 1, 3);
        addEdge(adj, 2, 3);

        if (DFS(adj, V) == true)
            System.out.println("Cycle found");
        else
            System.out.println("No cycle found");
    }
}

DFS : Part 1 : Detect Cycle in a Directed Graph

import java.util.*;

class Graph {

    static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);
    }

    static boolean DFSRec(ArrayList<ArrayList<Integer>> adj, int s, boolean[] visited, boolean[] recSt) {
        visited[s] = true;
        recSt[s] = true;

        for (int u : adj.get(s)) {
            if (visited[u] == false && DFSRec(adj, u, visited, recSt) == true) {
                return true;
            } else if (recSt[u] == true) {
                return true;
            }
        }
        recSt[s] = false;
        return false;
    }

    static boolean DFS(ArrayList<ArrayList<Integer>> adj, int V) {
        boolean[] visited = new boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        boolean[] recSt = new boolean[V];
        for (int i = 0; i < V; i++)
            recSt[i] = false;

        for (int i = 0; i < V; i++) {
            if (visited[i] == false)
                if (DFSRec(adj, i, visited, recSt) == true)
                    return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int V = 6;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(V);

        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<Integer>());

        addEdge(adj, 0, 1);
        addEdge(adj, 2, 1);
        addEdge(adj, 2, 3);
        addEdge(adj, 3, 4);
        addEdge(adj, 4, 5);
        addEdge(adj, 5, 3);

        if (DFS(adj, V) == true)
            System.out.println("Cycle found");
        else
            System.out.println("No cycle found");
    }
}

Topological Sorting (Kahn's BFS Based Algortihm)

import java.util.*;

class Graph {

    static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v) {
        adj.get(u).add(v);
    }

    static void topologicalSort(ArrayList<ArrayList<Integer>> adj, int V) {
        int[] in_degree = new int[V];

        for (int u = 0; u < V; u++) {
            for (int x : adj.get(u))
                in_degree[x]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < V; i++)
            if (in_degree[i] == 0)
                q.add(i);

        while (q.isEmpty() == false) {
            int u = q.poll();
            System.out.print(u + " ");

            for (int x : adj.get(u))
                if (--in_degree[x] == 0)
                    q.add(x);
        }
    }

    public static void main(String[] args) {
        int V = 5;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(V);

        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<Integer>());

        addEdge(adj, 0, 2);
        addEdge(adj, 0, 3);
        addEdge(adj, 1, 3);
        addEdge(adj, 1, 4);
        addEdge(adj, 2, 3);

        System.out.println("Following is a Topological Sort of");
        topologicalSort(adj, V);
    }
}

Part 2 : Detect Cycle in a Directed Graph ( using kahn's Algorithm )

import java.util.*;

class Graph {

    static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v) {
        adj.get(u).add(v);
    }

    static void topologicalSort(ArrayList<ArrayList<Integer>> adj, int V) {
        int[] in_degree = new int[V];

        for (int u = 0; u < V; u++) {
            for (int x : adj.get(u))
                in_degree[x]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < V; i++)
            if (in_degree[i] == 0)
                q.add(i);

        int count = 0;
        while (q.isEmpty() == false) {
            int u = q.poll();

            for (int x : adj.get(u))
                if (--in_degree[x] == 0)
                    q.add(x);

            count++;
        }
        if (count != V) {
            System.out.println("There exists a cycle in the graph");
        } else {
            System.out.println("There exists no cycle in the graph");
        }
    }

    public static void main(String[] args) {
        int V = 5;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(V);

        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<Integer>());

        addEdge(adj, 0, 1);
        addEdge(adj, 4, 1);
        addEdge(adj, 1, 2);
        addEdge(adj, 2, 3);
        addEdge(adj, 3, 1);

        topologicalSort(adj, V);
    }
}

Topological Sorting (DFS Based Algorithm)

import java.util.*;

class Graph {

    static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v) {
        adj.get(u).add(v);
    }

    static void DFS(ArrayList<ArrayList<Integer>> adj, int u, Stack<Integer> st, boolean visited[]) {
        visited[u] = true;

        for (int v : adj.get(u)) {
            if (visited[v] == false)
                DFS(adj, v, st, visited);
        }
        st.push(new Integer(u));
    }

    static void topologicalSort(ArrayList<ArrayList<Integer>> adj, int V) {
        boolean[] visited = new boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;
        Stack<Integer> st = new Stack<Integer>();

        for (int u = 0; u < V; u++) {
            if (visited[u] == false) {
                DFS(adj, u, st, visited);
            }
        }

        while (st.empty() == false)
            System.out.print(st.pop() + " ");

    }

    public static void main(String[] args) {
        int V = 5;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(V);

        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<Integer>());

        addEdge(adj, 0, 1);
        addEdge(adj, 1, 3);
        addEdge(adj, 2, 3);
        addEdge(adj, 3, 4);
        addEdge(adj, 2, 4);

        System.out.println("Following is a Topological Sort of");
        topologicalSort(adj, V);
    }
}

Shortest Path in Directed Acyclic Graph

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Stack;

class AdjListNode {
    private int v;
    private int weight;

    AdjListNode(int _v, int _w) {
        v = _v;
        weight = _w;
    }

    int getV() {
        return v;
    }

    int getWeight() {
        return weight;
    }
}

class Graph {
    private int V;
    private LinkedList<AdjListNode> adj[];

    Graph(int v) {
        V = v;
        adj = new LinkedList[V];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList<AdjListNode>();
    }

    void addEdge(int u, int v, int weight) {
        AdjListNode node = new AdjListNode(v, weight);
        adj[u].add(node);
    }

    void topologicalSortUtil(int v, Boolean visited[], Stack stack) {

        visited[v] = true;
        Integer i;

        Iterator<AdjListNode> it = adj[v].iterator();
        while (it.hasNext()) {
            AdjListNode node = it.next();
            if (!visited[node.getV()])
                topologicalSortUtil(node.getV(), visited, stack);
        }

        stack.add(v);
    }

    void shortestPath(int s) {
        Stack stack = new Stack();
        int dist[] = new int[V];

        Boolean visited[] = new Boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                topologicalSortUtil(i, visited, stack);

        for (int i = 0; i < V; i++)
            dist[i] = Integer.MAX_VALUE;
        dist[s] = 0;

        while (stack.empty() == false) {
            int u = (int) stack.pop();

            Iterator<AdjListNode> it;
            if (dist[u] != Integer.MAX_VALUE) {
                it = adj[u].iterator();
                while (it.hasNext()) {
                    AdjListNode i = it.next();
                    if (dist[i.getV()] > dist[u] + i.getWeight())
                        dist[i.getV()] = dist[u] + i.getWeight();
                }
            }
        }

        for (int i = 0; i < V; i++) {
            if (dist[i] == Integer.MAX_VALUE)
                System.out.print("INF ");
            else
                System.out.print(dist[i] + " ");
        }
    }
}

class Main {
    public static void main(String args[]) {

        Graph g = new Graph(6);
        g.addEdge(0, 1, 2);
        g.addEdge(0, 4, 1);
        g.addEdge(1, 2, 3);
        g.addEdge(4, 2, 2);
        g.addEdge(4, 5, 4);
        g.addEdge(2, 3, 6);
        g.addEdge(5, 3, 1);

        int s = 0;
        System.out.println("Following are shortest distances " + "from source " + s);
        g.shortestPath(s);
    }
}

Prim's Algorithm / Minimum Spanning Tree

import java.util.*;
import java.lang.*;
import java.io.*;

class Gfg {

    static final int V = 4;

    public static int primMST(int graph[][]) {

        int[] key = new int[V];
        int res = 0;
        Arrays.fill(key, Integer.MAX_VALUE);
        boolean[] mSet = new boolean[V];
        key[0] = 0;

        for (int count = 0; count < V; count++) {
            int u = -1;

            for (int i = 0; i < V; i++)
                if (!mSet[i] && (u == -1 || key[i] < key[u]))
                    u = i;
            mSet[u] = true;
            res += key[u];

            for (int v = 0; v < V; v++)

                if (graph[u][v] != 0 && mSet[v] == false)
                    key[v] = Math.min(key[v], graph[u][v]);
        }
        return res;
    }

    public static void main(String[] args) {
        int graph[][] = new int[][] { { 0, 5, 8, 0 }, { 5, 0, 10, 15 }, { 8, 10, 0, 20 }, { 0, 15, 20, 0 }, };

        System.out.print(primMST(graph));
    }
}

Dijkstra's Shortest Path Algorithm

import java.util.*;
import java.lang.*;
import java.io.*;

class Gfg {

    static final int V = 4;

    public static int[] djikstra(int graph[][], int src) {

        int[] dist = new int[V];
        int res = 0;
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        boolean[] fin = new boolean[V];

        for (int count = 0; count < V - 1; count++) {
            int u = -1;

            for (int i = 0; i < V; i++)
                if (!fin[i] && (u == -1 || dist[i] < dist[u]))
                    u = i;
            fin[u] = true;

            for (int v = 0; v < V; v++)

                if (graph[u][v] != 0 && fin[v] == false)
                    dist[v] = Math.min(dist[v], dist[u] + graph[u][v]);
        }
        return dist;
    }

    public static void main(String[] args) {
        int graph[][] = new int[][] { { 0, 50, 100, 0 }, { 50, 0, 30, 200 }, { 100, 30, 0, 20 }, { 0, 200, 20, 0 }, };

        for (int x : djikstra(graph, 0)) {
            System.out.print(x + " ");
        }

    }
}

Kosaraju's Algorithm Part 1

import java.io.*;
import java.util.*;
import java.util.LinkedList;

class Graph {
    private int V;
    private LinkedList<Integer> adj[];

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void DFSUtil(int v, boolean visited[]) {

        visited[v] = true;
        System.out.print(v + " ");

        int n;

        Iterator<Integer> i = adj[v].iterator();
        while (i.hasNext()) {
            n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    Graph getTranspose() {
        Graph g = new Graph(V);
        for (int v = 0; v < V; v++) {
            Iterator<Integer> i = adj[v].listIterator();
            while (i.hasNext())
                g.adj[i.next()].add(v);
        }
        return g;
    }

    void fillOrder(int v, boolean visited[], Stack stack) {
        visited[v] = true;

        Iterator<Integer> i = adj[v].iterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                fillOrder(n, visited, stack);
        }

        stack.push(new Integer(v));
    }

    void printSCCs() {
        Stack stack = new Stack();

        boolean visited[] = new boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                fillOrder(i, visited, stack);

        Graph gr = getTranspose();

        for (int i = 0; i < V; i++)
            visited[i] = false;

        while (stack.empty() == false) {
            int v = (int) stack.pop();

            if (visited[v] == false) {
                gr.DFSUtil(v, visited);
                System.out.println();
            }
        }
    }

    public static void main(String args[]) {
        Graph g = new Graph(5);
        g.addEdge(1, 0);
        g.addEdge(0, 2);
        g.addEdge(2, 1);
        g.addEdge(0, 3);
        g.addEdge(3, 4);

        System.out.println("Following are strongly connected components " + "in given graph ");
        g.printSCCs();
    }
}

Bellman Ford Shortest Path Algorithm

import java.util.*;
import java.lang.*;
import java.io.*;

class Graph {

    class Edge {
        int src, dest, weight;

        Edge() {
            src = dest = weight = 0;
        }
    };

    int V, E;
    Edge edge[];

    Graph(int v, int e) {
        V = v;
        E = e;
        edge = new Edge[e];
        for (int i = 0; i < e; ++i)
            edge[i] = new Edge();
    }

    void BellmanFord(Graph graph, int src) {
        int V = graph.V, E = graph.E;
        int dist[] = new int[V];

        for (int i = 0; i < V; ++i)
            dist[i] = Integer.MAX_VALUE;
        dist[src] = 0;

        for (int i = 1; i < V; ++i) {
            for (int j = 0; j < E; ++j) {
                int u = graph.edge[j].src;
                int v = graph.edge[j].dest;
                int weight = graph.edge[j].weight;
                if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v])
                    dist[v] = dist[u] + weight;
            }
        }

        for (int j = 0; j < E; ++j) {
            int u = graph.edge[j].src;
            int v = graph.edge[j].dest;
            int weight = graph.edge[j].weight;
            if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                System.out.println("Graph contains negative weight cycle");
                return;
            }
        }
        printArr(dist, V);
    }

    void printArr(int dist[], int V) {
        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < V; ++i)
            System.out.println(i + "\t\t" + dist[i]);
    }

    public static void main(String[] args) {
        int V = 4;
        int E = 5;

        Graph graph = new Graph(V, E);

        // add edge 0-1 (or A-B)
        graph.edge[0].src = 0;
        graph.edge[0].dest = 1;
        graph.edge[0].weight = 1;

        // add edge 0-2 (or A-C)
        graph.edge[1].src = 0;
        graph.edge[1].dest = 2;
        graph.edge[1].weight = 4;

        // add edge 1-2 (or B-C)
        graph.edge[2].src = 1;
        graph.edge[2].dest = 2;
        graph.edge[2].weight = -3;

        // add edge 1-3 (or B-D)
        graph.edge[3].src = 1;
        graph.edge[3].dest = 3;
        graph.edge[3].weight = 2;

        // add edge 2-3 (or C-D)
        graph.edge[4].src = 2;
        graph.edge[4].dest = 3;
        graph.edge[4].weight = 3;

        graph.BellmanFord(graph, 0);
    }
}

Articulation Point

import java.io.*; 
import java.util.*; 
import java.util.LinkedList; 


class Graph 
{ 
    private int V; 

    private LinkedList<Integer> adj[]; 
    int time = 0; 
    static final int NIL = -1; 

    Graph(int v) 
    { 
        V = v; 
        adj = new LinkedList[v]; 
        for (int i=0; i<v; ++i) 
            adj[i] = new LinkedList(); 
    } 

    void addEdge(int v, int w) 
    { 
        adj[v].add(w);  
        adj[w].add(v);  
    } 

    void APUtil(int u, boolean visited[], int disc[], 
                int low[], int parent[], boolean ap[]) 
    { 

        int children = 0; 

        visited[u] = true; 

        disc[u] = low[u] = ++time; 

        Iterator<Integer> i = adj[u].iterator(); 
        while (i.hasNext()) 
        { 
            int v = i.next(); 
            if (!visited[v]) 
            { 
                children++; 
                parent[v] = u; 
                APUtil(v, visited, disc, low, parent, ap); 


                low[u] = Math.min(low[u], low[v]); 


                if (parent[u] == NIL && children > 1) 
                    ap[u] = true; 

                if (parent[u] != NIL && low[v] >= disc[u]) 
                    ap[u] = true; 
            } 

            else if (v != parent[u]) 
                low[u] = Math.min(low[u], disc[v]); 
        } 
    } 

    void AP() 
    { 

        boolean visited[] = new boolean[V]; 
        int disc[] = new int[V]; 
        int low[] = new int[V]; 
        int parent[] = new int[V]; 
        boolean ap[] = new boolean[V];


        for (int i = 0; i < V; i++) 
        { 
            parent[i] = NIL; 
            visited[i] = false; 
            ap[i] = false; 
        } 

        for (int i = 0; i < V; i++) 
            if (visited[i] == false) 
                APUtil(i, visited, disc, low, parent, ap); 

        for (int i = 0; i < V; i++) 
            if (ap[i] == true) 
                System.out.print(i+" "); 
    } 

    public static void main(String args[]) 
    { 
        System.out.println("Articulation points in first graph "); 
        Graph g = new Graph(5); 
        g.addEdge(1, 0); 
        g.addEdge(0, 2); 
        g.addEdge(2, 1); 
        g.addEdge(0, 3); 
        g.addEdge(3, 4); 
        g.AP(); 
        System.out.println(); 
    } 
}

Bridges in Graph

import java.io.*; 
import java.util.*; 
import java.util.LinkedList; 

class Graph 
{ 
    private int V; 

    private LinkedList<Integer> adj[]; 
    int time = 0; 
    static final int NIL = -1; 

    Graph(int v) 
    { 
        V = v; 
        adj = new LinkedList[v]; 
        for (int i=0; i<v; ++i) 
            adj[i] = new LinkedList(); 
    } 

    void addEdge(int v, int w) 
    { 
        adj[v].add(w);  
        adj[w].add(v); 
    } 


    void bridgeUtil(int u, boolean visited[], int disc[], int low[], int parent[]) 
    { 

        visited[u] = true; 

        disc[u] = low[u] = ++time; 

        Iterator<Integer> i = adj[u].iterator(); 
        while (i.hasNext()) 
        { 
            int v = i.next(); 

            if (!visited[v]) 
            { 
                parent[v] = u; 
                bridgeUtil(v, visited, disc, low, parent); 


                low[u] = Math.min(low[u], low[v]); 


                if (low[v] > disc[u]) 
                    System.out.println(u+" "+v); 
            } 


            else if (v != parent[u]) 
                low[u] = Math.min(low[u], disc[v]); 
        } 
    } 

    void bridge() 
    { 
        boolean visited[] = new boolean[V]; 
        int disc[] = new int[V]; 
        int low[] = new int[V]; 
        int parent[] = new int[V]; 


        for (int i = 0; i < V; i++) 
        { 
            parent[i] = NIL; 
            visited[i] = false; 
        } 


        for (int i = 0; i < V; i++) 
            if (visited[i] == false) 
                bridgeUtil(i, visited, disc, low, parent); 
    } 

    public static void main(String args[]) 
    { 
        System.out.println("Bridges in first graph "); 
        Graph g = new Graph(5); 
        g.addEdge(1, 0); 
        g.addEdge(0, 2); 
        g.addEdge(2, 1); 
        g.addEdge(0, 3); 
        g.addEdge(3, 4); 
        g.bridge(); 
    }

}

Tarjans Algorithm

import java.io.*; 
import java.util.*; 

class Graph{ 

private int V; 

private LinkedList<Integer> adj[]; 
private int Time; 

@SuppressWarnings("unchecked") 
Graph(int v) 
{ 
    V = v; 
    adj = new LinkedList[v]; 

    for(int i = 0; i < v; ++i) 
        adj[i] = new LinkedList(); 

    Time = 0; 
} 

void addEdge(int v,int w) 
{ 
    adj[v].add(w); 
} 

void SCCUtil(int u, int low[], int disc[], boolean stackMember[], Stack<Integer> st) 
{ 
    disc[u] = Time; 
    low[u] = Time; 
    Time += 1; 
    stackMember[u] = true; 
    st.push(u); 

    int n; 

    Iterator<Integer> i = adj[u].iterator(); 

    while (i.hasNext()) 
    { 
        n = i.next(); 

        if (disc[n] == -1) 
        { 
            SCCUtil(n, low, disc, stackMember, st); 


            low[u] = Math.min(low[u], low[n]); 
        } 
        else if (stackMember[n] == true) 
        { 

            low[u] = Math.min(low[u], disc[n]); 
        } 
    } 

    int w = -1; 
    if (low[u] == disc[u]) 
    { 
        while (w != u) 
        { 
            w = (int)st.pop(); 
            System.out.print(w + " "); 
            stackMember[w] = false; 
        } 
        System.out.println(); 
    } 
} 

void SCC() 
{ 

    int disc[] = new int[V]; 
    int low[] = new int[V]; 
    for(int i = 0;i < V; i++) 
    { 
        disc[i] = -1; 
        low[i] = -1; 
    } 

    boolean stackMember[] = new boolean[V]; 
    Stack<Integer> st = new Stack<Integer>(); 

    for(int i = 0; i < V; i++) 
    { 
        if (disc[i] == -1) 
            SCCUtil(i, low, disc, stackMember, st); 
    } 
} 

public static void main(String args[]) 
{ 
    Graph g = new Graph(5); 

    g.addEdge(1, 0); 
    g.addEdge(0, 2); 
    g.addEdge(2, 1); 
    g.addEdge(0, 3); 
    g.addEdge(3, 4); 
    System.out.println("SSC in the graph "); 
    g.SCC(); 

} 
}

Kruskal's Algorithm

// Java program for Kruskal's algorithm to find Minimum 
// Spanning Tree of a given connected, undirected and 
// weighted graph 
import java.util.*;
import java.lang.*;
import java.io.*;

class Graph {
    // A class to represent a graph edge
    class Edge implements Comparable<Edge> {
        int src, dest, weight;

        // Comparator function used for sorting edges
        // based on their weight
        public int compareTo(Edge compareEdge) {
            return this.weight - compareEdge.weight;
        }
    };

    // A class to represent a subset for union-find
    class subset {
        int parent, rank;
    };

    int V, E; // V-> no. of vertices & E->no.of edges
    Edge edge[]; // collection of all edges

    // Creates a graph with V vertices and E edges
    Graph(int v, int e) {
        V = v;
        E = e;
        edge = new Edge[E];
        for (int i = 0; i < e; ++i)
            edge[i] = new Edge();
    }

    // A utility function to find set of an element i
    // (uses path compression technique)
    int find(subset subsets[], int i) {
        // find root and make root as parent of i (path compression)
        if (subsets[i].parent != i)
            subsets[i].parent = find(subsets, subsets[i].parent);

        return subsets[i].parent;
    }

    // A function that does union of two sets of x and y
    // (uses union by rank)
    void Union(subset subsets[], int x, int y) {
        int xroot = find(subsets, x);
        int yroot = find(subsets, y);

        // Attach smaller rank tree under root of high rank tree
        // (Union by Rank)
        if (subsets[xroot].rank < subsets[yroot].rank)
            subsets[xroot].parent = yroot;
        else if (subsets[xroot].rank > subsets[yroot].rank)
            subsets[yroot].parent = xroot;

        // If ranks are same, then make one as root and increment
        // its rank by one
        else {
            subsets[yroot].parent = xroot;
            subsets[xroot].rank++;
        }
    }

    // The main function to construct MST using Kruskal's algorithm
    void KruskalMST() {
        Edge result[] = new Edge[V]; // Tnis will store the resultant MST
        int e = 0; // An index variable, used for result[]
        int i = 0; // An index variable, used for sorted edges
        for (i = 0; i < V; ++i)
            result[i] = new Edge();

        // Step 1: Sort all the edges in non-decreasing order of their
        // weight. If we are not allowed to change the given graph, we
        // can create a copy of array of edges
        Arrays.sort(edge);

        // Allocate memory for creating V ssubsets
        subset subsets[] = new subset[V];
        for (i = 0; i < V; ++i)
            subsets[i] = new subset();

        // Create V subsets with single elements
        for (int v = 0; v < V; ++v) {
            subsets[v].parent = v;
            subsets[v].rank = 0;
        }

        i = 0; // Index used to pick next edge

        int res = 0;
        // Number of edges to be taken is equal to V-1
        while (e < V - 1) {
            // Step 2: Pick the smallest edge. And increment
            // the index for next iteration
            Edge next_edge = new Edge();
            next_edge = edge[i++];

            int x = find(subsets, next_edge.src);
            int y = find(subsets, next_edge.dest);

            // If including this edge does't cause cycle,
            // include it in result and increment the index
            // of result for next edge
            if (x != y) {
                result[e++] = next_edge;
                Union(subsets, x, y);

                res += next_edge.weight;
            }
            // Else discard the next_edge
        }

        // print the contents of result[] to display
        // the built MST

        System.out.println("Weight of MST is: " + res);
    }

    // Driver Program
    public static void main(String[] args) {

        int V = 5; // Number of vertices in graph
        int E = 7; // Number of edges in graph
        Graph graph = new Graph(V, E);

        // add edge 0-1
        graph.edge[0].src = 0;
        graph.edge[0].dest = 1;
        graph.edge[0].weight = 10;

        // add edge 0-2
        graph.edge[1].src = 0;
        graph.edge[1].dest = 2;
        graph.edge[1].weight = 8;

        // add edge 0-3
        graph.edge[2].src = 1;
        graph.edge[2].dest = 2;
        graph.edge[2].weight = 5;

        // add edge 1-3
        graph.edge[3].src = 1;
        graph.edge[3].dest = 3;
        graph.edge[3].weight = 3;

        // add edge 2-3
        graph.edge[4].src = 2;
        graph.edge[4].dest = 3;
        graph.edge[4].weight = 4;

        // add egde 2-4
        graph.edge[5].src = 2;
        graph.edge[5].dest = 4;
        graph.edge[5].weight = 12;

        // add edge 3-4
        graph.edge[6].src = 3;
        graph.edge[6].dest = 4;
        graph.edge[6].weight = 15;

        graph.KruskalMST();
    }
}

Prim's Algorithm

import java.util.*;
import java.lang.*;
import java.io.*;

class Gfg {

    static final int V = 4;

    public static int primMST(int graph[][]) {

        int[] key = new int[V];
        int res = 0;
        Arrays.fill(key, Integer.MAX_VALUE);
        boolean[] mSet = new boolean[V];
        key[0] = 0;

        for (int count = 0; count < V; count++) {
            int u = -1;

            for (int i = 0; i < V; i++)
                if (!mSet[i] && (u == -1 || key[i] < key[u]))
                    u = i;
            mSet[u] = true;
            res += key[u];

            for (int v = 0; v < V; v++)

                if (graph[u][v] != 0 && mSet[v] == false)
                    key[v] = Math.min(key[v], graph[u][v]);
        }
        return res;
    }

    public static void main(String[] args) {
        int graph[][] = new int[][] { { 0, 5, 8, 0 }, { 5, 0, 10, 15 }, { 8, 10, 0, 20 }, { 0, 15, 20, 0 }, };

        System.out.print(primMST(graph));
    }
}

Dijkstra's Algorithm Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Gfg {

    static final int V = 4;

    public static int[] djikstra(int graph[][], int src) {

        int[] dist = new int[V];
        int res = 0;
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        boolean[] fin = new boolean[V];

        for (int count = 0; count < V - 1; count++) {
            int u = -1;

            for (int i = 0; i < V; i++)
                if (!fin[i] && (u == -1 || dist[i] < dist[u]))
                    u = i;
            fin[u] = true;

            for (int v = 0; v < V; v++)

                if (graph[u][v] != 0 && fin[v] == false)
                    dist[v] = Math.min(dist[v], dist[u] + graph[u][v]);
        }
        return dist;
    }

    public static void main(String[] args) {
        int graph[][] = new int[][] { { 0, 50, 100, 0 }, { 50, 0, 30, 200 }, { 100, 30, 0, 20 }, { 0, 200, 20, 0 }, };

        for (int x : djikstra(graph, 0)) {
            System.out.print(x + " ");
        }

    }
}

Kosaraju's Algorithm

import java.io.*;
import java.util.*;
import java.util.LinkedList;

class Graph {
    private int V;
    private LinkedList<Integer> adj[];

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void DFSUtil(int v, boolean visited[]) {

        visited[v] = true;
        System.out.print(v + " ");

        int n;

        Iterator<Integer> i = adj[v].iterator();
        while (i.hasNext()) {
            n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    Graph getTranspose() {
        Graph g = new Graph(V);
        for (int v = 0; v < V; v++) {
            Iterator<Integer> i = adj[v].listIterator();
            while (i.hasNext())
                g.adj[i.next()].add(v);
        }
        return g;
    }

    void fillOrder(int v, boolean visited[], Stack stack) {
        visited[v] = true;

        Iterator<Integer> i = adj[v].iterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                fillOrder(n, visited, stack);
        }

        stack.push(new Integer(v));
    }

    void printSCCs() {
        Stack stack = new Stack();

        boolean visited[] = new boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                fillOrder(i, visited, stack);

        Graph gr = getTranspose();

        for (int i = 0; i < V; i++)
            visited[i] = false;

        while (stack.empty() == false) {
            int v = (int) stack.pop();

            if (visited[v] == false) {
                gr.DFSUtil(v, visited);
                System.out.println();
            }
        }
    }

    public static void main(String args[]) {
        Graph g = new Graph(5);
        g.addEdge(1, 0);
        g.addEdge(0, 2);
        g.addEdge(2, 1);
        g.addEdge(0, 3);
        g.addEdge(3, 4);

        System.out.println("Following are strongly connected components " + "in given graph ");
        g.printSCCs();
    }
}

Bellman Ford Shortest Path Algorithm

class Graph {

    class Edge {
        int src, dest, weight;

        Edge() {
            src = dest = weight = 0;
        }
    };

    int V, E;
    Edge edge[];

    Graph(int v, int e) {
        V = v;
        E = e;
        edge = new Edge[e];
        for (int i = 0; i < e; ++i)
            edge[i] = new Edge();
    }

    void BellmanFord(Graph graph, int src) {
        int V = graph.V, E = graph.E;
        int dist[] = new int[V];

        for (int i = 0; i < V; ++i)
            dist[i] = Integer.MAX_VALUE;
        dist[src] = 0;

        for (int i = 1; i < V; ++i) {
            for (int j = 0; j < E; ++j) {
                int u = graph.edge[j].src;
                int v = graph.edge[j].dest;
                int weight = graph.edge[j].weight;
                if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v])
                    dist[v] = dist[u] + weight;
            }
        }

        for (int j = 0; j < E; ++j) {
            int u = graph.edge[j].src;
            int v = graph.edge[j].dest;
            int weight = graph.edge[j].weight;
            if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                System.out.println("Graph contains negative weight cycle");
                return;
            }
        }
        printArr(dist, V);
    }

    void printArr(int dist[], int V) {
        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < V; ++i)
            System.out.println(i + "\t\t" + dist[i]);
    }

    public static void main(String[] args) {
        int V = 4;
        int E = 5;

        Graph graph = new Graph(V, E);

        // add edge 0-1 (or A-B)
        graph.edge[0].src = 0;
        graph.edge[0].dest = 1;
        graph.edge[0].weight = 1;

        // add edge 0-2 (or A-C)
        graph.edge[1].src = 0;
        graph.edge[1].dest = 2;
        graph.edge[1].weight = 4;

        // add edge 1-2 (or B-C)
        graph.edge[2].src = 1;
        graph.edge[2].dest = 2;
        graph.edge[2].weight = -3;

        // add edge 1-3 (or B-D)
        graph.edge[3].src = 1;
        graph.edge[3].dest = 3;
        graph.edge[3].weight = 2;

        // add edge 2-3 (or C-D)
        graph.edge[4].src = 2;
        graph.edge[4].dest = 3;
        graph.edge[4].weight = 3;

        graph.BellmanFord(graph, 0);
    }
}