DEV Community: Kousik Raj

The Top 10 Algorithms Every Programmer Should Know In Graph Data Structure!

Kousik Raj — Wed, 09 Feb 2022 09:36:20 +0000

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:

Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue.
If no adjacent vertex is found, remove the first vertex from the queue.
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:

Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.
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.)
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:

mark u as visited
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

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:*

Initialize the minimum spanning tree with a vertex chosen at random.
Find all the edges that connect the tree to new vertices, find the minimum and add it to the tree.
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:

First, sort all the edges from low weight to high.
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.
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:

Perform DFS traversal of the graph. Push node to stack before returning.
Find the transpose graph by reversing the edges.
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

Learn Data Structures and Algorithms

Kousik Raj — Tue, 08 Feb 2022 07:40:20 +0000

Why to Learn Data Structures and Algorithms?

Data structures and algorithms (DSA) goes through solutions to standard problems in detail and gives you an insight into how efficient it is to use each one of them. It also teaches you the science of evaluating the efficiency of an algorithm. This enables you to choose the best of various choices.

What are Algorithms?

In computer programming terms, an algorithm is a set of well-defined instructions to solve a particular problem. Informally, an algorithm is nothing but a mention of steps to solve a problem. It takes a set of input and produces a desired output. For Example,

An algorithm to find largest of two numbers:

Take two numbers as an input
Compare number1 with number2 with '>'. If it is greater, then store number1 in another variable named max
Else it is obvious that number2 is greater. So, store number2 in the variable max.
Print the variable max.

This is how a algorithm looks like. It is independent of Programming languages. It is just a step-by-step solution to given a problem which could be understood by everyone.

Data Structures

Data Structures are the programmatic way of storing data so that data can be used efficiently. Almost every enterprise application uses various types of data structures in one or the other way.
Data structure is a storage that is used to store and organize data. It is a way of arranging data on a computer so that it can be accessed and updated efficiently.
Depending upon the requirement, we can select a particular data structure.

For example, if you want to store data sequentially in the memory, then you can go for Array data structure

Remember these two simple equations:

Related data + Permissible operations on the data = Data Structures
Data structures + Algorithms = Programs

NOTE : Data structure and data types are slightly different. Data structure is the collection of data types arranged in a specific order.

Classifications of Data Structure

Primitive Data Structure
- Integer
- Float
- Boolean
- Character
- Pointer, etc.
Non-Primitive Data Structure

i) Linear Data Structure

Array
Linked Lists
Stack
Queue

ii) Non-linear Data Structure

Trees
Graphs

Linear Data Structure

A linear data structure has data elements connected to each other so that elements are arranged in a sequential manner and each element is connected to the element in front of it and behind it. This way, the structure can be traversed in a single run.

Linear data structures can be implemented easily as computer memory is also arranged in a linear manner.

1. Arrays

One of the simplest data structures, an array is a collection of items that are stored sequentially. An array contains values or variables—known as “elements”—of the same data type and is of a fixed size, so you cannot change the size of an array. Each item in an array is indexed starting with 0.

Usage:

Arrays are commonly used as structures for building other, more complicated data structures. They are also used for sorting algorithms.

2. Linked Lists

A linked list stores a collection of items in a linear order. Each element, or node, in a linked list contains a data item, as well as a reference, or link, to the next item in the list. In Other words, Data elements are connected through a series of nodes and, each node contains the data items and address to the next node.

Usage:

Linked lists are used for symbol table management in switching between programs using Alt + Tab (On a PC).
Multiplayer games use a circular list to swap between players in a loop.

3. Stacks

A stack stores a collection of items in the linear order that operations are applied. This order could be last in, first out (LIFO) or first in, Last out (FILO). That is, the last element stored in a stack will be removed first. It works just like a pile of plates where the last plate kept on the pile will be removed first.

You can “push” a new element onto the top of the stack, or you can “pop,” deleting the element inserted last which is at the top of the stack.

Usage:

Stacks can be used for Memory Management.
Stack data structures are used in backtracking problems.

4. Queues

A queue functions similarly to a stack, but instead of being a LIFO structure, it is a FIFO (First In First Out) structure. The easiest way to think about a queue is to think of a line of people waiting to enter a building. The person at the beginning of the line will enter the building first, while the person at the end will enter last.

You can enqueue an element in this structure, which means inserting the element to the end of the queue. You can also dequeue an element, which means deleting an element from the beginning of the queue.

Usage:

In real life scenario, Call Center phone systems uses Queues to hold people calling them in an order, until a service representative is free.

Non-Linear Data Structure

Unlike linear data structures, elements in non-linear data structures are not in any sequence. Instead they are arranged in a hierarchical manner where one element will be connected to one or more elements.

As the arrangement is non-sequential, so the data elements cannot be traversed or accessed in a single run. In the case of linear data structure, element is connected to two elements (previous and the next element), whereas, in the non-linear data structure, an element can be connected to more than two elements.

1. Graphs

It is a non-linear data structure that consists of various linked nodes. It has a hierarchical tree structure that forms a parent-child relationship. In graph data structure, each node is called vertex and each vertex is connected to other vertices through edges. It is a collection of nodes that have data and are connected to other nodes.

The diagrammatic representation of a graph data structure looks like:

Usage:

Google maps uses graphs for building transportation systems, thus their navigation system is based on the algorithm to calculate the shortest path between two vertices.
Facebook’s Friend suggestion algorithm uses graph theory. Facebook is an example of undirected graph.

2. Trees

Similar to a graph, a tree is also a collection of vertices and edges. However, in tree data structure, there can only be one edge between two vertices. Each node is associated with a key value, with parent nodes linked to child nodes or sub nodes. There is one root node that is the ancestor of all the nodes in the tree.

Usage:

Binary search trees are used in many different types of search applications. Other types of trees are used in wireless networking and to create expression solvers.

Other Data Structures:

Hash Table

A hash table also known as a hash map stores a collection of items in an associative array that plots keys to values. A hash table uses a hash function to convert an index into an array of buckets that contain the desired data item.

Heaps

A heap is a tree-based structure in which each parent node's associated key value is greater than or equal to the key values of any of its children's key values.

Trie

A Trie is an advanced data structure that is sometimes also known as prefix tree or digital tree. It is a tree that stores the data in an ordered and efficient way. We generally use trie's to store strings.

Conclusion:

Knowledge about data structures help you understand the working of each data structure. This helps you write memory and time efficient code.

This is my first post. Please let me know your valuable feedbacks.

Thank You! :)