2–Edge Connectivity in a graph
Given an undirected connected graph, check if the graph is 2–edge connected or not. A connected graph is 2–edge connected if it remains connected whenever any edges are removed.
Tag: Algorithm
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.
Topological Sort Algorithm for DAG
Given a Directed Acyclic Graph (DAG), print it in topological order using topological sort algorithm. If the DAG has more than one topological ordering, output any of them.
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.
Depth First Search (DFS) – Iterative and Recursive Implementation
Depth–first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root for a graph) and explore as far as possible along each branch before backtracking.
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.
Binary Search in C++ STL and Java Collections
This post will discuss how to search for a given target value in a sorted array of integers using binary search implementation provided by the C++ standard library (STL) and Java Collection framework.
In-place vs out-of-place algorithms
All algorithms can be classified into in-place and out-of-place algorithms based on the amount of extra space used by them. In this quick article, we’ll explore the difference between the two.
Tower of Hanoi Problem
The Tower of Hanoi is a mathematical puzzle consisting of three rods and n disks of different sizes which can slide onto any rod.
Clock Angle Problem
Clock Angle Problem: Given time in hh:mm format, calculate the shorter angle between the hour and minute hand in an analog clock.