A Guide to Master Graph Algorithms for Competitive Programming

A Guide to Master Graph Algorithms for Competitive Programming
A Guide to Master Graph Algorithms for Competitive Programming

Introduction 

In Computer Science, the concepts of master graph theory are different from what we have studied in our schools. A graph is considered a pictorial representation of heterogeneous objects having definitive meaning with interlinks or connections.

When you have to go shopping or to a restaurant, remember how you put your location and destination, and google map quickly shows you the shortest possible route from your place to the restaurant. It also redirects when you take the wrong turn.

Image Source: Google Maps

You can see how Google Maps shows all the possible routes from Vaishali(Delhi) to V-3S Mall(Delhi) and highlights the shortest path in the above snap.

Well, no magic there. It all works on the principle of graph algorithms! Graphs are the ultimate thought for many real-world problems, and today, technology exists that can use them as such.

In this blog, we will address the essential terminologies, the representation, and the traversals of the graph, accompanied by some advanced algorithms. One must know to outshine technical interviews and excel in competitive programming.

Graph

A Graph is a non-linear data structure that represents a relationship between various objects. It is a collection of two primary components: VERTEX AND EDGE.

Every node is known as a graph’s vertex, while the link that connects two or more nodes is known as an edge.

For example: 

Suppose there is a road network in a country with many states and union territories.

blog banner 1

Some states are not connected by other states or union territories like Andaman and Nicobar Islands in India. These Islands are accessed by air and waterways only.

If we consider states or union territories as nodes and roads as links, Andaman and Nicobar will not be linked with anyone, so this structure seems to be non-uniform, so we can’t use trees to store them. In such cases, the graph comes to the rescue.

Refer to the illustration below for a better understanding.

  • V(G) = {1,2,3,4,5,6}
  • E(G) = {(1,2), (1,5), (2,5), (5,4), (2,3), (3,4), (4,6)}

Let’s proceed to know the prerequisites to enter the world of graph data structures.

Prerequisites in master graph

Firstly you should have a solid knowledge of Recursion, Stack, and Queue data structures- as they will help in graph traversals. Don’t bother; we will discuss graph traversals in brief as we move further. 

Finally, a good grasp of Tree Data Structure in a master graph. Why? Because there exists a relationship between graphs and trees.

  • A tree is a specific type of graph in which we can reach any node from any other node using some unique path, unlike the graphs where this condition may or may not hold.
  • A tree is a graph with N vertices and precisely N-1 edges that do not have any cycles, while a graph may have cycles.

So this is some of the pre-learning you require before getting a deep understanding of graph concepts.

Basic terminologies of Graph

Before moving ahead, let’s get familiar with some basic terminologies of graphs.

  1. Vertices and Edges: Nodes are called vertices, and the connections between them are called edges
  1. Adjacent vertices: Two vertices are said to be adjacent if there exists a direct edge connecting them.
  1. Degree of a vertex: It is defined as the number of edges that are incident to a vertex. If the degree of vertex v is 0, it means that v does not belong to any edge, and such a node is known as an isolated vertex.
  1. Path In Graph: A path is a collection of edges through which we can reach from one node to another in a graph. 

A path P is written as P = {v0,v1,v2,….,vn} of length n from a node u to node v, is defined as a sequence of (n+1) nodes. Here u = v0, v = vn and vi-1 is adjacent to vi for i = 1,2,3,…..,n.

  1. Connected Graph: A graph is connected if there is a path between every pair of vertices.
  1. Connected Components In Graph: If the graph is not connected, then all the maximally connected subsets of the graphs are called connected components. Each component is connected within itself, but two different components of a graph are never connected.

Image Source: csteachers

Types of Graph

  1. Undirected Graphs: In undirected graphs, edges do not have any direction associated with them. In other words, if an edge is drawn between nodes A and B, then the nodes can be traversed from A to B as well as from B to A.
  1. Directed Graphs: In directed graphs, edges form an ordered pair. In other words, if there is an edge from A to B, then there is a direct path from A to B but not from B to A. The edge (A, B) is said to initiate from node A (also known as an initial node) and terminate at node B (terminal node).
  1. Unweighted Graphs: In unweighted graphs, an edge does not contain any weight.
  1. Weighted Graphs: If edges in a graph have weights associated with them, the graph is weighted.

Image Source: Geekgod

Representation of Graph

Suppose the graph is as follows:

There are the following ways to implement a graph:

  1. Adjacency matrix: Here, we will create a 2D array where the cell (i, j) will denote an edge between node i and node j.  Adjacency Matrix is used in dense graphs, i.e. when there is a large number of edges.

For the above graph, the adjacency matrix looks as follows:

  1. Edge list
  •  We can create a class that could store an array of edges. 
  • The array of edges will contain all the connected pairs and all put together in one place.
  • It is not preferred to check for a particular edge connecting two nodes; we have to traverse the complete array leading to O(N2) time complexity in the worst case where N is the number of edges.
  • Pictorial representation for the above graph using the edge list is given below:
  1. Adjacency list

We will create an array of vertices, but this time, each vertex will have its list of edges connecting this vertex to another vertex. The key advantages of using an adjacency list are: 

  • It is often used to store graphs with a small-to-moderate number of edges, i.e., an adjacency list is preferred for representing sparse graphs in the computer’s memory.
  • It is easy to follow and clearly shows the adjacent nodes of a particular node. Adding new nodes in G is easy and straightforward when G is represented using an adjacency list.

Note: The major disadvantage of using the adjacency matrix:

  • Vast space consumption compared to the adjacency list.
  • The memory use of an adjacency matrix for V nodes is O(V^2), whereas the adjacency list requires O(V+E), where V is the number of vertices and E  is the number of edges.

Now that we have touched on the basics of a graph data structure, look at what Parikh Jain, Founding Member of Coding Ninjas, has to say about master graph data structure and algorithms. 

Graph Traversals

Traversing a graph means examining the nodes and edges of the graph. There are two standard methods of graph traversal, which we will discuss in this section. These two methods are:

Depth-first search (DFS) in master graph

  • The depth-first search(DFS) algorithm, as the name implies, first goes into the depth and then recursively does the same in other directions.
  • It begins at a starting node A which becomes the current node. Then, it examines each node along with a path P which starts at A. We process a neighbour of A, then a neighbour of the processed node, and so on. 
  • During the algorithm’s execution, if we reach a path with a node that has already been processed, we backtrack to the current node. Otherwise, the unvisited (unprocessed) node becomes the current node.
  • Below is the short animation of the DFS traversal to make it more clear:

Blue Colour shows the current node, and Green indicates already visited.

Image Source: gifer.com

DFS traversal of the above graph will be 1—2—4—3—5

Breadth-first search (BFS) in master graph

  • In the Breadth-first search(BFS) algorithm, we start from the selected node and traverse the graph level-wise, thus exploring the neighbour nodes directly connected to the starting node and then moving on to the next level neighbour nodes.
  • Below is the short animation of the BFS traversal to get more clarity about the algorithm

Where Green Colour shows the current node and White shows the unvisited node.

Image Source: Dev Community

BFS traversal of the above graph will be 1—2—3—4—5—6—7

Points to remember:

  • While depth-first search uses a Stack as an auxiliary data structure to store nodes for further processing, the depth-first search scheme uses a Queue
  • During the algorithm’s execution, every node in the graph will have the variable VISITED set to false or true, depending on its current state, whether the node has been processed, i.e., visited or not.

Since this article primarily focuses on the basic terminologies and the algorithms one must know to master graphs, we are not going into depth about BFS and DFS implementation. Still, you can study it from the guided path of Coding Ninjas created by our experts in data structures and algorithms.

Applications of BFS & DFS in master graph

Applications of Depth-First Search Algorithm in master graph.

Applications of Breadth-First Search algorithm in master graph

 (The shortest path is in terms of the minimum number of moves required to visit v from u or vice-versa).

In most technical interviews, the questions of graphs mostly revolve around BFS and DFS or their applications, but it’s not always true, so to be prepared for the most challenging. We will further see the advanced algorithms in graphs, which will help you crack the tough interview questions and outshine competitive programming.

Advanced algorithms in Graph

Spanning Tree

If we are given an undirected and connected graph, a spanning tree is a tree that contains all the vertices(V) of the graph and |V|-1 edges. For a given graph, we can have multiple spanning trees.

Refer to the example below for a better understanding of spanning trees.

If there are n vertices and e edges in the graph, then any spanning tree corresponding to that graph contains n vertices and n-1 edges.

Properties of spanning trees:

  • A connected and undirected graph can have more than one spanning tree.
  • The spanning tree is free of loops, i.e., it is acyclic.
  • Removing any one of the edges will make the graph disconnected.
  • Adding an extra edge to the spanning tree will create a loop in the graph.

Minimum Spanning Tree(MST) 

The MST is a spanning tree with minimum weight in a weighted graph than all other spanning trees. 

Refer to the image below for better understanding, where the edges marked in bold represent the edges of the spanning tree.

Various graph Algorithms to find MST are:

Shortest Path Algorithms

  1. Dijkstra’s Algorithm

This algorithm is used to find the shortest distance between any two vertices in a weighted non-cyclic graph. Dijkstra’s Algorithm is also known as the Minimum Cost Path. It is one of the most favourite algorithms of interviewers of big-tech companies like Amazon, Google, Adobe, etc. 

  1. Bellman-Ford Algorithm

The Bellman-Ford algorithm is an algorithm that measures the shortest path from a single source vertex to all of the other vertices in a weighted graph. It is slower than Dijkstra’s Algorithm but more versatile as it can detect negative cycles also.

  1. Floyd Warshall Algorithm

It is an algorithm for finding the shortest paths in a directed weighted graph with positive or negative edge weights but with no negative cycles.

Topological Sort

A Directed Acyclic Graph (DAG) is a directed graph that contains no cycles.

Topological Sorting of DAG is a linear ordering of vertices such that for every directed edge from vertex ‘u’ to vertex ‘v,’ vertex ‘u’ comes before ‘v’ in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

Graphs In Matrix

We have already seen that the adjacency matrix is one of the representations of a graph. Now we should try our hands on some problems of Graphs in Matrix given below:

Other Algorithms for Competitive Programming

Here we are listing some algorithms and problems falling under the tricky category, which will help you recognise and apply creative ideation problem-solving techniques in competitive programming and challenging technical interviews.

If you have read this far, you will master graphs too.

Like any other data structure, this demands your perseverance and practice, maybe a little more than others, but in the end, You’ll not regret it, and it’ll all be worth it. Just build a good grasp on pre-requisites, then learn and practice the questions given above, and you will be one step closer to your dream company.

Frequently Asked Questions

What is a graph in coding?

A Graph is a non-linear data structure that represents a relationship between various objects. It is a collection of two primary components: Vertex and Edge.

How do you master a graph in data structure?

If you want to master graph data structure, then you are on the right page.
Follow the comprehensive guide given above by our experts and then practice plenty of questions on CodeStudio created by the next generation of product engineers from Microsoft, Google and Amazon, which provides you hassle-free, and excelling online courses, practice questions, blogs, and mentors’ support. Trust me; you won’t regret exploring it once.

How difficult is graph theory?

Graph theory is not difficult if you have a solid fundamental knowledge of Recursion, Stack, Queue, and Tree. The best way to understand something is to understand its applications, so you are provided with several applications that you can practice in this article.

How is graph theory used in real life?

Graph theory is used in many real-life applications. For example, all roads and motorways also form an extensive network of navigation services like Google Maps when working out the shortest route between two given points.

What is the difference between tree and graph?

Graph and Tree both are non-linear data structures in the master graph. A tree is a graph with N vertices and precisely N-1 edges that do not have any cycles, while a graph may have cycles.

What are some of the top graph algorithms?

Some of the top graph algorithms are mentioned below.

1. Implement breadth-first traversal
2. Implement depth-first traversal
3. Calculate the number of nodes at a graph level
4. Find all paths between two nodes
5. Find all connected components of a graph
6. Prim’s and Kruskal Algorithms
7. Dijkstra’s algorithm to find the shortest path in graph data
8. Topological Sorting

Key Takeaways

This article summarises graph data structures, but it highlights pre-learning like Recursion, Stack, Queues, and Trees before going into depth.

It also addresses the essential terminologies like vertex, edges, types of graphs followed by the representations of graph and graph traversal techniques with its applications.

Then we further specify the advanced graph-algorithms like Minimum Spanning Trees, Dijkstra, Graph in Matrix, etc. That will help in cracking technical interviews and excelling in competitive programming.

Programming is like sport. The more you spend your time on the field, the more you become an expert. Likewise, in programming, the more you practice, the more you learn. So keep on practising various problems. You should check out CodeStudio – A platform developed by aspiring enthusiasts and working professionals who have experience in companies like Google, Amazon, Microsoft, Adobe etc.

At CodeStudio, you will get interview problems, experiences, and practice problems that can help you to land your dream job.

By Aanchal Tiwari