Top 10 graph algorithms every software developer must know

Graphs comprise a highly integral part of our day-to-day lives. They impact almost every sphere of living without us even realizing it. From developing the road networks on the macro scale to the internal internet working in the virtual world, graphs are there. This article will study a high-level view of ten graph algorithms that every aspiring software developer must know. Let’s begin!

Breadth-First Search (BFS)

My favorite graph algorithm. The Breadth-First Search algorithm, or BFS as it is popularly known, is a graph traversal algorithm. Graph traversal algorithms help us to travel the graph from node to node and edge to edge. BFS is one of the two most popular methods used for this purpose. The idea behind BFS is simple. Consider a node you have just visited and mark it visited. Now, consider all possible “unvisited” nodes adjacent to this node and mark them visited. Now consider this entire set of nodes obtained in the previous step and find all adjacent, unvisited nodes to each node in this set. We repeat these steps until we visit all nodes in the graph (given it is connected).

Depth-First Search (DFS)

The Depth-First Search, or DFS, is a counterpart to the BFS. In DFS, we consider a path starting from the source and follow it till the end until we reach a node with no adjacent unvisited nodes. Thus, we travel along the “depth” of the graph in one iteration. This traversal is in contrast to BFS, which simultaneously considers all unvisited adjacent nodes for a given node. When we reach the end of a path, we trace back our steps one at a time and follow a different path till the end as we did previously. This process repeats until all the nodes are visited (connected graph). Generally, the order of traversals generated by BFS and DFS are different, as we shall illustrate in the example below.

Dijkstra’s Algorithm

Now we will start with the shortest-path algorithms. Dijkstra’s is what you call a “single source shortest path algorithm.” It implies a single source node; from that point, we need to find the shortest path to all other nodes starting at the source. The idea used in this algorithm is simple. We start at the source node. From there, we consider all adjacent nodes to the source. We can note here the graph is a “positive weighted graph.” Each edge in the graph has the weight or “cost” of traversing that edge. We use the below formula for updating the shortest path value:

distance[node] = min(distance[node], distance[intermediary] + cost[intermediary][node]);

// cost[intermediary][node] is the weight of the edge connecting the "intermediary" and "node" nodesCode language: C++ (cpp)

Initially, assign all nodes with infinity as the shortest path value. Now consider the shortest weight edge outgoing from the source and assign this value to the respective node. Consider the next smallest weight edge outgoing from the start or this newly appointed node. Repeat the above process until we obtain the shortest path for each node. Can you find the shortest path to all nodes starting at node “a” in the example below:

Bellman-Ford Algorithm

As I mentioned in Dijkstra’s algorithm, we use it for “positive” weighted graphs. Dijkstra’s algorithm fails in case of a negative weight edge because it will continue to use the negative cost to reduce the node value. But this should not happen in reality. We use the Bellman Form algorithm in such a case to resolve this issue. The idea used in Bellman-Ford is continuous relaxation. We initialize all the shortest path distances for each node to be infinity except the source node, which we initialize to zero. So we consider all the edges in the graph in one iteration, and for each edge, we perform the following operation:

distance[node] = min(distance[node], distance[intermediary] + cost[intermediary][node]);

// cost[intermediary][node] is the weight of the edge connecting the "intermediary" and "node" nodesCode language: C++ (cpp)

But we perform this iteration |V|-1 times where |V| represents the number of nodes in the graph. We iterate only |V|-1 times and not more than that because then that will consider a loop in the graph, which we can avoid while making the shortest path computation.

Floyd-Warshall Algorithm

Floyd-Warshall is used to solve the problem of “all pairs shortest path.” It is quite a simple algorithm. The idea is to iterate over all nodes, and for each node, iterate over all other nodes. Now considering the first node and each node selected in the inner loop, we again iterate over all other nodes, which behave as intermediate nodes between the specified source and destination. Therefore, we will give some ideas below about the formula which we use here:

vector<int> nodes; // nodes in the graph
...
for (int src: nodes) {
    for (int dest: nodes) {
         for (int temp: nodes) {
             // idea of Floyd-Warshall algorithm
             distance[src][dest] = min(distance[src][dest], distance[src][temp] + distance[temp][dest]);
         }
    }
}Code language: C++ (cpp)

Kruskal’s Algorithm

We will use this and the following algorithm to build a Minimum Spanning Tree (MST) from a given graph. A Minimum Spanning Tree is a subgraph of the original graph in which we connect all the vertices, and the total cost of the edges included is the minimum among all Spanning Trees. The basic idea behind Kruskal’s algorithm is that we first sort all the edges in non-decreasing order. Then, one by one, we select each edge and try to include it in the constructed MST. If we form a cycle by including this edge, we discard it. Otherwise, we consider it and move to the next edge. We repeat this process till we have exactly |V|-1 edges in the MST. Any more edges will indicate a cycle which is not what we want. This algorithm follows a greedy approach.

Prim’s Algorithm

Prim’s algorithm is also a greedy approach to the Minimum Spanning Tree problem. In this case, we select a source node and include it in the MST. Now, we assign the respective edge weights to their adjacent neighbors. Then, we choose the minimum value among these values and include this vertex and edge in the final set. Now considering these two vertices and the same process as above, we find the third vertex and second edge for this MST. This process repeats until we have the final MST constructed. We can note that in Kruskal’s, the intermediate stage has a forest of trees, whereas Prim’s has one tree that grows to form the MST.

Topological Sort

“Topological Sorting” is the idea of arranging the vertices in a directed graph in a particular manner. Consider a directed edge from node “x” to node “y.” Therefore, node “x” appears before node “y” in the final topological ordering. We also note that multiple possible topological orderings for a given graph exist. Take a look at the example below for more clarity:

Cycle Detection

As the title suggests, “Cycle Detection” is used to find the presence of cycles in the given graph. We can implement this using simple BFS or DFS algorithms with a slight trick. We terminate both algorithms when there are no more “adjacent unvisited nodes” for a particular node. Consider the case that the algorithm terminates naturally, that is, if we reach a leaf node with no adjacent nodes apart from the vertex where we just arrived. In this case, we declare no cycle is found. But assume we reach a node with other adjacent nodes, and at least one of these nodes is previously visited. In this case, we declare that a cycle exists since we arrive at an already seen node from an unvisited node.

Strongly Connected Components

We call a graph component “strongly connected” if and only if we can visit every node in this component from every other node via some path. We have two algorithms, Tarjan’s and Kosaraju’s, for finding out the strongly connected components in a graph.

Conclusion

I hope to provide a valuable overview of the ten most essential algorithms prevalent in Graph Theory. These algorithms find their use in most graph applications in real life. Also, for students and professionals preparing for placements or improving their job profiles, these algorithms are a must-know for coding rounds and interview processes. Try these algorithms on your own and solve as many problems as possible to get a firm hand on them. Happy Coding!