Graph Algorithms

DFS:

1. Start from a node and pick any of unvisited neighbours(connected nodes from current), when a node is explored, we mark it visited.
2. Once we hit the dead-end, as we backtrack and reach back the source.
3. Next, we pick any node that is not yet visited and repeat.

Topological Sort:

1. Form adjacency graph for the given input.
2. Keep track of in-degrees of each node. and add nodes with no incoming edges to the queue.
3. We will use queue(simple linkedlist) to keep track of the nodes to process.
4. While queue is not empty, we can keep polling the queue and reduce the in-degree of nodes connected by outbound edges.
5. This process may generate new nodes with 0 in-degree. we can add them to the queue.

If there’s a cycle then there will be nodes with non zero in-degree and they will never be added to queue.

Also, the order in which the elements are popped from the queue is the order in which they should be processed.

        int[] indegree = new int[numCourses];

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

        // form adjacency graph
        for(int[] edge : prerequisites){
            graph.get(edge[1]).add(edge[0]);
            indegree[edge[0]]++;
        }

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

        for(int i=0;i<numCourses;i++){
            if(indegree[i]==0) queue.add(i); // add all start nodes(in-degree=0)
        }

        int count=0;
        while(!queue.isEmpty()){
            int curr = queue.poll();
            count++;

            for(int course : graph.get(curr)){
     //if we remove all outgoing edges from curr, then remove incoming edges for
      //neighbours.
                if(--indegree[course] == 0) queue.add(course); 
            }
        }
        return count==numCourses;

BFS:

Dijikstra’s single source shortest path:

Will work only if there are no cycles with negative weights.

1. We will use the priority queue to pick the next node with minimum weight.
2. We maintain an array distance to keep track of distance from source to each node. Initially it will be 0 for source and infinity for others. We keep updating the distances as we explore new nodes.
3. The main idea is to reach all nodes from source, while exploring the least weight edge(PriorityQueue).

public int networkDelayTime(int[][] times, int n, int k) {
    // Build adjacency list
    Map<Integer, List<int[]>> graph = new HashMap<>();
    for (int[] t : times) {
        graph.computeIfAbsent(t[0], x -> new ArrayList<>()).add(new int[]{t[1], t[2]});
    }

    // Dijkstra's algorithm
    Map<Integer, Integer> distances = new HashMap<>();
    distances.put(k, 0);
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    heap.add(new int[]{0, k});

    while (!heap.isEmpty()) {
        int[] curr = heap.poll();
        int dist = curr[0], node = curr[1];

        if (dist > distances.getOrDefault(node, Integer.MAX_VALUE))
            continue;

        for (int[] edge : graph.getOrDefault(node, new ArrayList<>())) {
            int neighbor = edge[0], weight = edge[1];
            int newDist = dist + weight;
            if (newDist < distances.getOrDefault(neighbor, Integer.MAX_VALUE)) {
                distances.put(neighbor, newDist);
                heap.add(new int[]{newDist, neighbor});
            }
        }
    }

    if (distances.size() != n) return -1;
    return Collections.max(distances.values());

Bellman-ford single source shortest path algorithm

This algorithm will work even with negative edges but not with negative cycles.

Idea here is to keep going through the edges and update the distances. We repeat this process V-1 times because for a graph with Vvertices, longest path can be at most V-1 edges long.

Below we are running V times(1 time extra to check for the cycles).

Time Complexity: O(V*E) Space Complexity: O(V)

static int[] bellmanFord(int V, int[][] edges, int src) {

        // Initially distance from source to all other vertices 
        // is not known(Infinite).
        int[] dist = new int[V];
        Arrays.fill(dist, (int)1e8);
        dist[src] = 0;

        // Relaxation of all the edges V times, not (V - 1) as we  
        // need one additional relaxation to detect negative cycle
        for (int i = 0; i < V; i++) {
            for (int[] edge : edges) {
                int u = edge[0];
                int v = edge[1];
                int wt = edge[2];
                if (dist[u] != 1e8 && dist[u] + wt < dist[v]) {

                    // If this is the Vth relaxation, then there is
                    // a negative cycle
                    if (i == V - 1)
                        return new int[]{-1};

                    // Update shortest distance to node v
                    dist[v] = dist[u] + wt;
                }
            }
        }
        return dist;
    }

Floyd-Warshall all pairs shortest path algorithm

Idea here is to treat each vertex as potential intermediate node between a source and destination. So the shortest route can be with or without the current node.

static void floydWarshall(int[][] dist) {
        int V = dist.length;
        int INF = (int)1e8;

        // for each intermediate vertex
        // between source and destination
        for (int k = 0; k < V; k++) {

            // Pick all vertices as source one by one
            for (int i = 0; i < V; i++) {

                // Pick all vertices as destination
                // for the above picked source
                for (int j = 0; j < V; j++) {

                    // shortest path from i to j 
                    if(dist[i][k] != INF && dist[k][j]!= INF) 
                        dist[i][j] = Math.min(dist[i][j], 
                                              dist[i][k] + dist[k][j]);
               }
            }
       }
}

Prim’s MST

Kruskal’s MST

Union-Disjoint Sets