Shortest path in a maze – Lee Algorithm
Given a maze in the form of the binary rectangular matrix, find the shortest path’s length in a maze from a given source to a given destination.
Tag: Breadth-first search
Check if a graph is strongly connected or not
Given a directed graph, check if it is strongly connected or not. A directed graph is said to be strongly connected if every vertex is reachable from every other vertex.
Chess Knight Problem | Find the shortest path from source to destination
Given a chessboard, find the shortest distance (minimum number of steps) taken by a knight to reach a given destination from a given source.
Total paths in a digraph from a given source to a destination having exactly `m` edges
Given a digraph (directed graph), find the total number of routes to reach the destination from a given source with exactly m edges.
Check if an undirected graph contains a cycle or not
Given a connected undirected graph, find if it contains any cycle or not. For example, the following graph contains a cycle 2–5–10–6–2.
Transitive closure of a graph
The transitive closure for a digraph G is a digraph G’ with an edge (i, j) corresponding to each directed path from i to j in G. The resultant digraph G’ representation in the form of the adjacency matrix is called the connectivity matrix.
Snake and Ladder Problem
Find the minimum number of throws required to win a given Snake and Ladder game. For example, the following game requires at least 7 dice throws to win.
Bipartite Graph
Given a graph, check if it is bipartite or not. A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V.
Breadth-First Search (BFS) – Iterative and Recursive Implementation
Breadth–first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’) and explores the neighbor nodes first before moving to the next-level neighbors.