Union–Find Algorithm for cycle detection in a graph
Given an undirected connected graph, check if it contains any cycle or not using the union–find algorithm.
Tag: Recursive
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.
Disjoint–Set Data Structure (Union–Find Algorithm)
This post explains the working of disjoint-set data structure (also called union find data structure). A disjoint-set is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets.
Check if a digraph is a DAG (Directed Acyclic Graph) or not
Given a directed graph, check if it is a DAG (Directed Acyclic Graph) or not. A DAG is a digraph (directed graph) that contains no cycles.
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.
Determine whether an undirected graph is a tree (Acyclic Connected Graph)
Given an undirected graph, check if it is a tree or not. In other words, check if a given undirected graph is an Acyclic Connected Graph or not.
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.
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.
Arrival and departure time of vertices in DFS
The arrival time is the time at which the vertex was explored for the first time in the DFS, and departure time is the time at which we have explored all the neighbors of the vertex, and we are ready to backtrack.
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.