# Shubham Singh

## Shortest path in an unweighted graph

Problem Statement Given the directed, connected and unweighted graph G, a Source and a Destination and the task to find the shortest path possible between two given vertices in the graph. Note: The path does not contain any cycle which means path have finite number of vertices. Example Input Expected Output Path : 0 3 Implementation in …

## Nodes are on same path in a tree or Not

Problem Statement Given a tree and two nodes of tree and the task to check whether these two nodes are on the same path from root to the bottom or not. Example Input Node1 = 1 Node2 = 5 Expected Output Yes Approach The idea is to apply Depth First Search on every node. And …

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

Problem statement Given a snake and ladder coordinates which represent the actual snake and ladder board, find the minimum number of dice throws required to reach the destination cell from source cell. This problem can be easily solved bu using 0-1 BFS. Example Input Expected Output Implementation in Python

## Topological Sorting

In graph theory, a topological sorting of a directed graph is a linear ordering of vertices of graph such that if there is a directed edge uv from vertex u to vertex v, u comes before v in the ordering. Note: Graph must be directed and acyclic. Example Input Expected Output 0 2 1 3 Pseudocode Implementation in Python

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

## Water Jug problem using BFS

Problem Statement Given two jugs with J1 and J2 litres of capacities which are initially empty. Using these jugs you have to measure L litres of water (L < J2).The (x, y) is the state where x and y are the amount of water in J1 and J2 respectively. The task is to find the path from …

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

## Breadth First Traversal for a Graph

Breadth First Search (BFS) is a graph traversal algorithm that is used to traverse all the vertices of a graph in a breadthward motion. In other words, it starts the graph traversal from root node and explores all the neighboring nodes first instead of going deep. Example of Breadth First Traversal for a Graph Breadth First …

## array::size() function in C++ STL

The array::size() is a C++ Standard Library function which is used to get the size of the array. Syntax: Parameter: The array::size() function does not accepts any parameters. Return value: The array::size() function returns the size of the array. Example of array::size() Function Output

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]