 # Depth First Search

## Count number of trees in a forest

Problem Statement Given a forest with edge representation, find the number of trees in the forest. Example Input edges = {{0, 1}, {0, 2}, {3, 4}, {4, 5}, {5, 6}} Expected Output 2 Approach The idea is to apply Depth First Search on every node. If every connected node is visited from one source then …

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

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

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

Scroll to Top