Operations on Graph

In Computer Science, a Graph is a non-linear data structure that finds its use in numerous real-life problems ranging from Social Networking applications to Path Optimization problems. The graph data structure consists of nodes/vertices which are connected by edges.
The following are the operations that can be performed on Graph data structure:
1. Insert edge
2. Delete edge
3. Insert vertex
4. Delete vertex
5. Find the vertex
6. Graph traversal
7. Display graph

Shortest Path

Shortest path algorithms help us to find the shortest possible path between two vertices/nodes in a graph. There are two types of shortest path problems, namely - Single Source Shortest Path and All Pairs Shortest Path. There are also several shortest path algorithms such as,
1. Dijkstra's Algorithm (Single Source Shortest Path)
2. Bellman Ford's Algorithm (Single Source Shortest Path)
3. Floyd Warshall's Algorithm (All Pairs Shortest Path)

Dijkstra's Algorithm

By Aditya Narayan Joardar

● Published At Dec 2021

In this article, we will discuss Dijkstra’s Algorithm with various examples and explanations.... Keep reading ..

Find Maximum Shortest Distance in Each Component of a Graph

By Nishant Rana

● Published At Feb 2022

This blog will cover the question to find the maximum shortest distance in each component of a Graph.
... Keep reading ..

Johnson’s Algorithm for All-Pairs Shortest Paths

By Abhishek Ranjan

● Published At Jan 2022

In this article, we will discuss Jhonson's Algorithm for the all-pairs shortest path and try to understand its time complexity.... Keep reading ..

Why does Dijkstra’s algorithm fail on negative weights?

By Shreya Deep

● Published At Dec 2021

In this article, we will find out why Dijkstra's algorithm fails on negative edge weights.... Keep reading ..

Difference between the shortest and second shortest path in an Unweighted Bidirectional Graph

By Abhishek Ranjan

● Published At Dec 2021

In this article, we will try to solve a graph theory problem Difference between the shortest and second shortest path in an Unweighted Bidirectional Graph that can be asked in the interviews.
... Keep reading ..

Shortest path in a directed acyclic graph

By aniket verma

● Published At Oct 2021

This article will brief you on finding the shortest path in a directed acyclic graph.... Keep reading ..

Shortest path in an unweighted graph

By aniket verma

● Published At Oct 2021

This article will brief you on finding the Shortest path in an unweighted graph.... Keep reading ..

Number of distinct Shortest Paths from Node 1 to N in a Weighted and Directed Graph

By Abhishek Ranjan

● Published At Dec 2021

n this article, we will try to solve a graph theory problem that can be asked in the interviews.... Keep reading ..

Maximize the shortest path between given vertices by adding a single edge

By Apoorv

● Published At Feb 2022

This article will discuss the solution of the problem “Maximize the shortest path between given vertices by adding a single edge”
... Keep reading ..

Minimum Cost using Dijkstra by reducing the cost of an Edge

By Ishita Chawla

● Published At Dec 2021

This blog will discuss the problem of minimum cost using Dijkstra by reducing the cost of an edge.... Keep reading ..

Minimum possible modifications in the matrix to reach the destination

By GAZAL ARORA

● Published At Dec 2021

In this article, we are going to learn how to convert a matrix problem into a graph problem and solve it using graph algorithms.... Keep reading ..

Connectivity

Connectivity in a graph means that there is a path between every pair of the vertex in the graph. In graph theory, Connectivity is a simple yet very widely used concept. DFS and BFS traversals in a graph can be used to determine whether a graph is connected or not. The connectivity concept is used to find the number of connected components in a graph which is widely used in programming contests.

Find the number of islands

By Aditya Narayan Joardar

● Published At Dec 2021

This article discusses finding the number of islands in a given 2D matrix using DFS.... Keep reading ..

Number of Islands

By Alisha Chhabra

● Published At Nov 2021

This article covers the approach and Implementation of the problem Number of Islands in java.
... Keep reading ..

Minimum number of swaps required to sort an array

By Shreya Deep

● Published At Dec 2021

In this article, we will learn how to find the minimum number of swaps required to be done to sort an array... Keep reading ..

Weakly Connected Components in a Directed Graph

By GAZAL ARORA

● Published At Jan 2022

A directed graph is weakly connected if its undirected graph is connected. In this article, we will find weakly connected components in a given directed graph.
... Keep reading ..

Cycles

Cycles in a graph refer to a non-empty path of vertices in which the first and last vertices are equal. On the basis of the presence of cycles in a graph, a graph can be cyclic or acyclic. A directed graph without a directed cycle is called Directed Acyclic Graph(DAG). Cycle detection in a graph can be done by using Depth First Traversals. Cycles in graphs give rise to various other graph theory concepts like Topological Sorting and strongly connected components in directed graphs.

Check if a Cycle Exists Between Nodes S and T in an Undirected Graph with only S and T Repeating

By Anant Dhakad

● Published At Dec 2021

In this blog, we will discuss the DFS traversal of an undirected graph. We will also see the application of DFS in cycle detection.... Keep reading ..

Detect cycles in a directed graph.

By Gorakhnath yadav

● Published At Oct 2021

In this blog, we will learn about the Depth First Search traversal-based method to detect cycles in a directed graph.... Keep reading ..

How to detect cycles in an undirected graph

By Gorakhnath yadav

● Published At Oct 2021

In this blog, we will learn about the Depth First Search traversal-based method to detect cycles in an undirected graph.... Keep reading ..

Count of Simple Cycles in a Connected Undirected Graph Having N Vertices

By Malay Gain

● Published At Jan 2022

In this article, we will learn to count the number of simple cycles in an undirected graph with N vertices.
... Keep reading ..

Detect a Negative Cycle in a Graph using Shortest Path Faster Algorithm

By Riya

● Published At Feb 2022

This article will discuss how to detect a negative cycle using shortest path faster algorithm in a given graph, its C++ implementation, and its time and space complexity.... Keep reading ..

## Top Problems related to Operations on Graph

Colour The Graph

Properties of MST in a Undirected Graph

Detect Cycle in a Undirected Graph

Alien dictionary

DFS Traversal

Minimum Time in Wormhole Network

Minimum Spanning Tree

Count Ways

Detect Cycle in an Undirected Graph

Bridges In A Graph

Minimum steps to reach target by a Knight

Dijkstra's shortest path

Reachable Nodes

Path Queries

Shortest Path

Path Reversals

Road Constructor

Check If Path Exists

Roads

Number Of Triangles In An Undirected Graph

Detect Cycle in a Directed Graph