Traversal
The process of exploring each vertex in a graph is known as graph traversal. Every problem on the graph includes traversing in some way. To avoid getting stuck in cycles, it's usually required to maintain track of visited vertices. DFS (Depth-first search) and BFS (Breadth-first search) are the two primary graph traversal strategies.
Breadth First Search(BFS)
Breath first search, or BFS, is a well-known graph/tree traversal algorithm. The core concept is that each node pays a visit to each of its children before paying a visit to their children's children. A queue is the data structure used to achieve BFS. It's typically used in problems where you have to find an optimum value, such as the shortest path in an unweighted graph.
Breadth-First Search
By Raksha jain
● Published At Jan 2022
The blog discusses "Breadth-First Search Traversal of the Graph." We'll discuss an interesting approach to solve the problem and its time and space complexity too. ... Keep reading ..
Minimum length paths between 1 to N including each node
By Aditya Narayan Joardar
● Published At Feb 2022
This article discusses how to calculate the minimum length paths between node 1 to N including each.... Keep reading ..
Check if the given permutation is a valid BFS of a given tree
By Ishita Chawla
● Published At Dec 2021
This blog will discuss the famous problem, check if the given permutation is a valid BFS of a given tree.... Keep reading ..
Find integral points with minimum distance from given set of integers using BFS
By Aman Chourasiya
● Published At Nov 2021
In this blog, we will take up a problem based on BFS - Breadth-First Search. We will use a common variant of BFS namely, multi-source BFS to solve the problem.... Keep reading ..
Implement Water Supply System
By Vaibhav Agarwal
● Published At Dec 2021
In this article, we will discuss the problem of implementing a water supply system.... Keep reading ..
0-1 BFS
By Sandeep kamila
● Published At Nov 2021
This blog will cover the 0-1 BFS algorithm, its approach using an example and code in C++. ... Keep reading ..
01 Matrix
By Saksham Gupta
● Published At Jan 2022
In this blog, we will discuss one of the famous and important questions from the interview perspective, i.e., 01 Matrix. ... Keep reading ..
Depth First Search(DFS)
Depth-first search is a technique for traversing or exploring data structures such as trees and graphs. The algorithm begins at the root node and travels as far as feasible down each branch before returning to the root node. So the fundamental concept is to begin at the root or any random node and mark the node before moving to the next unmarked node and repeating this loop until there are no unmarked nearby nodes. Then go back and look for more unmarked nodes to traverse.
DFS Traversal of a Graph - Iteratively
By Gaurish Anand
● Published At Feb 2022
In this article, we will see the DFS traversal of a graph iteratively. ... Keep reading ..
Implementation Of DFS Using Adjacency Matrix
By Harsh Goyal
● Published At Jan 2022
This article will discuss the implementation of DFS using an adjacency matrix and how to approach this problem.... Keep reading ..
Check if there are at least T continuous blocks of 0s or not in a Binary Matrix
By GAZAL ARORA
● Published At Jan 2022
In this article, we will check if there are at least T continuous blocks of 0s or not in a given Binary Matrix Mat of size N*M in O(N*M) time where T is the GCD of N and M. ... Keep reading ..
Find Regions with Most Common Region Size in a Given Boolean Matrix
By Abhishek Ranjan
● Published At Dec 2021
In this article, we will try to solve a graph theory problem that can be asked in the interviews.... Keep reading ..
Clone of an undirected graph
By Vaibhav Agarwal
● Published At Dec 2021
In this article, we will discuss the approach to making a clone of an undirected graph... Keep reading ..
Parallel Courses III
By Pranav Gautam
● Published At Dec 2021
Learn to find the minimum number of months required to complete all the parallel courses given as a graph.... Keep reading ..
General Problems
Proficiency in the practices of data structures and algorithms is essential for acing any coding test/interview. Many of the difficulties we face on a daily basis may be reduced to a graph problem or a closely related subproblem. As a result, considerable acquaintance with various graph modifications and their applications is necessary. Most of the problems based on graphs include the following general algorithms: 1. BFS 2. DFS 3. TOPOLOGICAL SORTING 4. MINIMUM SPANNING TREES (MST) 5. SHORTEST PATH ALGORITHMS 6. CYCLE DETECTION
Course Schedule
By Shreya Deep
● Published At Oct 2021
In this article, we’ll learn how to solve the problem named Course Schedule where we have to find the correct ordering of tasks using topological sorting. ... Keep reading ..
Topological sort without Kahn’s algorithm
By Malay Gain
● Published At Nov 2021
This article will discuss an alternative approach to Khan’s algorithm for topological sorting.... Keep reading ..
Clone a Directed Acyclic Graph
By Vibhor Bhatnagar
● Published At Dec 2021
This article will discuss the problem to clone a directed acyclic graph. ... Keep reading ..
Word Ladder
By GAZAL ARORA
● Published At Dec 2021
In this article, we will solve a programming problem: Given a dictionary of words, find the length of the shortest chain to reach a target word from a given start word. ... Keep reading ..
Minimum Cost Path in a directed graph via a given set of necessary nodes
By Apoorv
● Published At Feb 2022
This article will discuss finding a Minimum Cost Path in a directed graph via a given set of intermediate nodes. The blog also focuses on time and space complexity for the solution.... Keep reading ..
Stepping Numbers
By Aditya Narayan Joardar
● Published At Feb 2022
This article discusses finding stepping numbers in a given range using Brute Force and DFS.... Keep reading ..
Print all paths from a given source to a destination
By Aditya Narayan Joardar
● Published At Dec 2021
This article discusses printing all paths from a given source to a given vertex.... Keep reading ..
Accounts Merge
By Ishita Chawla
● Published At Nov 2021
In this blog, we will discuss the problem of Accounts Merge using Depth First Search and discuss its time and space complexity. ... Keep reading ..
Euler and Hamiltonian Paths
By Harsh Goyal
● Published At Nov 2021
This article will introduce Euler and Hamiltonian paths and discuss approaches to use them in different data structure problems. ... Keep reading ..
How to check if an array of strings can form a circle or not?
By Gorakhnath yadav
● Published At Oct 2021
In this blog, we learned about how to check if a given array of strings can form a circle or not. Read more to learn the detailed solution.... Keep reading ..
Beautiful Arrangement
By Harsh Goyal
● Published At Nov 2021
This article will discuss the Beautiful Arrangements problem and various ways to solve this problem, starting from the brute force approach to the efficient approach. ... Keep reading ..