Depth First Search

Detect Cycle in a Directed Graph

Problem Statement Given the directed, connected and unweighted graph G and the task to check whether the graph contains a cycle or not. Example Input Expected Output No Approach The approach is to use Depth First Traversal to detect a cycle in a Graph. While traversing through the graph if previous node visited node is encountered again …

Detect Cycle in a Directed Graph Read More »

Depth First Traversal for a Graph

Depth First Search (BFS) is a recursive graph traversal algorithm that is used to traverse all the vertices of a graph in a depthward motion. In other words, it starts the graph traversal from root node and explores all the branches. Example of Depth First Traversal for a Graph Depth First Traversal is used to traverse all the vertices of …

Depth First Traversal for a Graph Read More »

Number of Islands

Given a 2D grid consisting of either ‘1’ or ‘0’ character at each position. ‘1’ represents land and ‘0’ represents water. An island is a mass of land which is surrounded by water. Count the number of islands. . Example Test Cases Sample Test Case 1 Input grid: 11110 11010 11000 00000 Expected Output: 1 …

Number of Islands Read More »

Scroll to Top