Articles for author: Paras Yadav

Detect Cycle in Directed Graph

Problem Statement Given a Directed graph $G=(V, E)$ with $V$ vertices numbered from $0$ to $V-1$ and $E$ edges. The task is to detect cycle in the directed graph $i.e.$ to check if there exists a cycle in the given graph. Examples Example 1 Input: Output:NO Explanation: No cycle exists in the above give Directed ...

Advanced Data structures

Data structures are fundamental components in data science, enabling efficient storage, organization, and manipulation of information. Mastery of advanced data structures is vital for programmers, as they underpin the design and implementation of effective algorithms and software systems. The efficiency of algorithms often hinges on the choice and implementation of data structures, influencing both time ...

Bellman–Ford Algorithm

The Bellman-Ford algorithm is an example of Dynamic Programming. It starts with a starting vertex and calculates the distances of other vertices which can be reached by one edge. It then continues to find a path with two edges and so on. The Bellman-Ford algorithm follows the bottom-up approach. What is Bellman-Ford Algorithm? The Bellman-Ford ...

Shortest Path in Directed Acyclic Graph

In graph theory, identifying the shortest path from a single vertex to all others is essential. The Bellman-Ford algorithm accomplishes this in O(V×E) time. However, for Directed Acyclic Graphs (DAGs), topological sorting offers a more efficient approach. Before delving deeper, let’s understand what a Directed Acyclic Graph (DAG) is. Essentially, it’s a directed graph free ...

Depth First Search (DFS) Algorithm

Depth First Search (DFS) is an algorithm that is mainly used to traverse the graph data structure. The algorithm starts from an arbitrary node (root node in case of trees) and explore as far as possible in the graph before backtracking. After backtracking it repeats the same process for all the remaining vertices which have ...

Print Left View of Binary Tree

The left view of a binary tree corresponds to the nodes of the tree, which would be visible to someone seeing the tree from its left side, as shown in the image below – To print the left view of a binary tree, it’s essential to recognize that the leftmost node at each level is ...

Disjoint Set

The Disjoint-Set data structure, also known as Union-Find, manages elements in non-overlapping subsets. It’s primarily used for graph connectivity problems, offering two operations: Union, to merge sets, and Find, to identify a set’s leader. This structure excels in tasks involving elements initially represented as separate sets, enabling efficient set combination and connectivity checks between elements. ...

Red Black Tree

Red-Black Trees are balanced binary search trees where nodes are colored red or black. This color scheme ensures O(log n) time complexity for search, insert, and delete operations. They self-balance, adapting to changes, making them efficient for managing large datasets. Simple rules govern their structure, ensuring fast searching, sorting, and data management. Properties of Red ...

Radix Sort Algorithm

Radix Sort is a non-comparative algorithm that sorts the data in lexicographical (dictionary) order using Counting Sort as a subroutine. It is ideal for sorting integers digit by digit and strings character by character, it distributes elements into buckets by digit value, sorting repeatedly from least to most significant digit for final order. Radix Sort ...

Kargers Algorithm for Minimum Cut

In graph theory, a cut is a set of edges removal of which divides a connected graph into two non-overlapping (disjoint) subsets. The minimum cut (or min-cut) is defined as the minimum number of edges, when removed from a graph, divide the graph into two disjoint sets. A randomized contraction algorithm $i.e.$ Karger's Algorithm is ...