Why to learn these graph algorithms?

Graph algorithms are a set of instructions that traverse (visits nodes of a) graph. Some algorithms are used to find a specific node or the path between two given nodes.

Graphs are very useful data structures which can be to model various problems. These algorithms have direct applications on Social Networking sites, State Machine modeling and many more. I have attached my source code for all the algorithms discussed below. You can use it for your referral.

1. Breadth First Searching

Breadth First Search is a recursive algorithm for searching all the vertices of a graph or tree data structure.
Breadth-first search is a graph traversal algorithm that starts traversing the graph from the root node and explores all the neighboring nodes. Then, it selects the nearest node and explores all the unexplored nodes. While using BFS for traversal, any node in the graph can be considered as the root node.

An simple algorithm to be remembered for BFS:

1. Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue.

2. If no adjacent vertex is found, remove the first vertex from the queue.

3. Repeat Rule 1 and Rule 2 until the queue is empty.

The Diagrammatic representation of BFS Traversal:

Reference code : Breadth First Searching

2. Depth First Searching

Depth first Search or Depth first traversal is a recursive algorithm for searching all the vertices of a graph or tree data structure.
Depth First Search (DFS) algorithm traverses a graph in a depthward motion and uses a stack to remember to get the next vertex to start a search, when a dead end occurs in any iteration.

An simple algorithm to be remembered for DFS:

1. Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.

2. If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the vertices from the stack, which do not have adjacent vertices.)

3. Repeat Rule 1 and Rule 2 until the stack is empty.

The Diagrammatic representation of DFS Traversal:

Reference code : Depth First Searching

3. Topological Sorting

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u v, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.
There can be more than one topological sorting for a graph.

An simple algorithm to be remembered for Topological sort:

1. mark u as visited

2. for all vertices v which is adjacent with u, do

2.1 if v is not visited, then

2.2 TopoSort(c, visited, stack)

2.3 done

1. push u into a stack

The Diagrammatic representation of Topological sort

One of the Topological sort for this graph is:

5 -> 4 -> 2 -> 3 -> 1 -> 0

Reference code : Topological Sorting

4. Detecting a cycle using Kahn's Algorithm

Kahn’s topological sort algorithm is cycle detection algorithm, which also provides an efficient way to print the topological order.
Kahn’s topological sort algorithm works by finding vertices with no incoming edges and removing all outgoing edges from these vertices.

Reference code : Detecting a cycle using Kahn's Algorithm

5. Dijkstra's Algorithm

Dijkstra's algorithm allows us to find the shortest path between any two vertices of a graph.
It differs from the minimum spanning tree because the shortest distance between two vertices might not include all the vertices of the graph.

It is a single-source shortest path algorithm. Here, single-source means that only one source is given, and we have to find the shortest path from the source to all the nodes.

After applying Dijkstra's Algorithm:

Reference code : Dijkstra's Algorithm

6. Bellman Ford's Algorithm

Bellman Ford algorithm helps us find the shortest path from a vertex to all other vertices of a weighted graph.
It is similar to Dijkstra's algorithm but it can detect graphs in which edges can have negative weight cycles.

Dijkstra's Algorithm (can't able to detect negative weight cycle) can give an incorrect result because they can go through a negative weight cycle and reduce the path length.

Dijkstra doesn’t work for Graphs with negative weights, Bellman-Ford works for such graphs. Bellman-Ford is also simpler than Dijkstra and suites well for distributed systems.

The Output Of Bellman Ford's Algorithm:

Reference code : Bellman Ford's Algorithm

7. Floyd-Warshall Algorithm

Floyd-Warshall Algorithm is an algorithm for finding the shortest path between all the pairs of vertices in a weighted graph. This algorithm works for both the directed and undirected weighted graphs. But, it does not work for the graphs with negative cycles (where the sum of the edges in a cycle is negative). Here, a dynamic programming concept will be used.

Algorithm Behind Floyd-Warshall Algorithm:

Dij(k) ← min ( Dij(k-1), Dik(k-1)+Dkj(k-1) )

Reference code : Floyd-Warshall Algorithm

8. Prim's Algorithm

Prim's Algorithm is a greedy algorithm that is used to find the minimum spanning tree from a graph. Prim's algorithm finds the subset of edges that includes every vertex of the graph such that the sum of the weights of the edges can be minimized.

*An simple algorithm to be remembered for Prim's Algorithm:*

1. Initialize the minimum spanning tree with a vertex chosen at random.

2. Find all the edges that connect the tree to new vertices, find the minimum and add it to the tree.

3. Keep repeating step 2 until we get a minimum spanning tree

Output:

Reference code : Prim's Algorithm

9. Kruskal's Algorithm

Kruskal's Algorithm is used to find the minimum spanning tree for a connected weighted graph. The main target of the algorithm is to find the subset of edges by using which we can traverse every vertex of the graph. It follows the greedy approach that finds an optimum solution at every stage instead of focusing on a global optimum.

An simple algorithm to be remembered for Prim's Algorithm:

1. First, sort all the edges from low weight to high.

2. Now, take the edge with the lowest weight and add it to the spanning tree. If the edge to be added creates a cycle, then reject the edge.

3. Continue to add the edges until we reach all vertices, and a minimum spanning tree is created.

Reference code : Kruskal's Algorithm

10. Kosaraju's Algorithm

If we can reach every vertex of a component from every other vertex in that component then it is called a Strongly Connected Component (SCC). Single node is always a SCC. The Brute force method will be Floyd Warshall Algorithm. But for better time complexity, we can use Kosaraju's Algorithm.

An simple algorithm to be remembered for Prim's Algorithm:

1. Perform DFS traversal of the graph. Push node to stack before returning.

2. Find the transpose graph by reversing the edges.

3. Pop nodes one by one from the stack and again to DFS on the modified graph.

Output:

Reference code : Kosaraju's Algorithm

These are the most important algorithms one should know as a programmer in graph data structure.
I will be uploading detailed explanation of each algorithm in upcoming posts. Stay Tuned!

Did you find the Algorithms listed in this article helpful?
If you enjoyed this article, share it with your friends and colleagues!
Leave your comments below!

Here's my another article: Learn Data Structures and Algorithms