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
● Published At Dec 2021
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
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
● 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
● 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.
● 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