# 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.

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.

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.

**Vertices and Edges**: Nodes are called vertices, and the connections between them are called edges.

**Adjacent vertices**: Two vertices are said to be adjacent if there exists a direct edge connecting them.

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

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

**Connected Graph**: A graph is connected if there is a path between every pair of vertices.

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

**Types of Graph**

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

**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).

**Unweighted Graphs**: In unweighted graphs, an edge does not contain any weight.

**Weighted Graphs**: If edges in a graph have weights associated with them, the graph is weighted.

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

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

**3. 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.

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.

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.

- Finding a path between two specified nodes, u and v, of an unweighted graph.

- Finding a path between two specified nodes, u and v, of a weighted graph.

__Find Number of Connected Components____.__

__Shortest Path In Binary Matrix__

- Computing the spanning tree of a connected graph.

__Is Graph Tree Or Not?__

__Colour The Graph__

__Largest Island__

__Count Nodes Within K Distance__

- Prism Algorithm

Applications of Breadth-First Search algorithm in master graph

__Finding all connected components in a graph__

- Finding all nodes within an individual connected component

- Finding the shortest path between two nodes, u and v, of an unweighted 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.

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.

Various graph Algorithms to find MST are:

__Kruskal’s Algorithm__

__Prim’s Algorithm__

__Cycle Detection__: While inserting a new edge in the MST, we have to check if introducing that edge makes the MST cyclic or not.

- Union Find Algorithm In Graph

**Shortest Path Algorithms**

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

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

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

- Strongly Connected Components – Tarjan’s Algorithm

__Count-Ways__

__Alien-Dictionary__

__Minimum Direction Changes__

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

## Conclusion

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.

Recommended Readings:

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.