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.

Time Complexity: O(V+E) from iterating all vertices and exploring neighbours at each vertex. Also, adjacency representation traversal results in O(V+E). If the same graph represented in adj matrix then complexity will be O(V2) since we will check if there’s an edge to all other vertices at each vertex resulting in V*V.

Space Complexity: O(V) (recursion stack:O(V) and visited Array O(V))

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.

Get Kranthi Munjampalli’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

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

Time Complexity: O((V+E)logV) Explanation: Extract min takes O(V*logV) operations and in the worst case, every edge is relaxation results in heapify in minHeap, resulting in O(E*logV) so overall time complexity: VlogV+ElogV = (V+E)logV
Space Complexity: O(V+E) Explanation: adj list takes up O(V+E) space, visited takes up O(V) space. Distance array takes up O(V) space and heap takes up O(V) assuming all vertices are added to heap. So overall O(V+E)

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) iterating all vertices for each edge. 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