## Edge Classifications | Graph

Edge Types With DFS traversal of Graph, only some edges will be traversed. These edges will form a tree, called the depth-first-search tree starting at the given root, and the edges in this tree are called tree edges. We can classify the various edges of the graph based on the [...]

By |2020-03-28T14:18:59+05:30March 28th, 2020|Categories: Data Structure|Tags: |

## Counting Sort

Counting sort works by iterating through the input, counting the number of times each item occurs, and using those counts to compute an item's index in the final, sorted array. Counting sort assumes that each of the n input elements in a list has a key value ranging from 0 [...]

By |2019-09-09T22:07:18+05:30September 9th, 2019|Categories: Data Structure|

## Articulation points and Bridges

Articulation Point Let G= (V, E) be a connected undirected graph. An articulation point (or cut vertex) of G is a vertex whose removal disconnects G. In other words a vertex v is an articulation point if removing v increases the number of connected components. Nodes having color red in [...]

By |2019-07-07T20:41:45+05:30July 7th, 2019|Categories: Data Structure|

## Directed Acyclic Graphs

A directed acyclic graph(or DAG for short) is a directed graph that contains no cycles. In a DAG, a source is a vertex without incoming edges; a sink is a vertex without outgoing edges. Each DAG contains at least one source and one sink. Important points :- After removing a [...]

By |2019-07-07T18:46:44+05:30July 7th, 2019|Categories: Data Structure|

## Segment Tree

Introduction Segment Tree data structure allows answering range queries over an array effectively, while still being flexible enough to allow modifying the array. This includes finding the sum of consecutive array elements a[l…r], or finding the minimum element in a such a range in O(logn) time. Segment Tree is a [...]

By |2019-06-26T18:50:30+05:30June 26th, 2019|Categories: Data Structure|

## Red Black Tree

Introduction A red-black tree is a binary search tree with one extra attribute for each node: the colour, which is either red or black. We also need to keep track of the parent of each node, so that a red-black tree's node structure would be: enum Colour{ red, black }; [...]

By |2019-06-25T23:27:08+05:30June 25th, 2019|Categories: Data Structure|

## Maximum adjacent difference in an array in its sorted form

Given a unsorted array with n elements. How can we find the largest gap between consecutive numbers of sorted version in O(n). For example Input : arr[] = {1, 10, 5} Output : 5 Sorted array would be {1, 5, 10} and maximum adjacent difference would be 10 - 5 [...]

By |2019-05-23T14:30:25+05:30April 20th, 2019|Categories: Data Structure|

## String Search Algorithms

Introduction In this article, we’ll show several algorithms for searching for a pattern in a text. The fundamental string searching (matching) problem is defined as follows: given two strings – a text and a pattern, determine whether the pattern appears in the text. Naive Method For every position in the [...]

By |2019-06-24T22:44:16+05:30March 10th, 2019|Categories: Data Structure|

## Cyclic Array rotations

Rotation of the array means that each element is shifted right or left by one index. In case of right rotation the last element of the array is moved to the first place. For example Input : Given array A = [3, 8, 9, 7, 6] and K = 3 [...]

By |2019-03-10T11:12:04+05:30March 10th, 2019|Categories: Data Structure|