Data Structure

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 color of the node reached when DFS follows the edge.

2020-03-28T14:18:59+05:30Categories: 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 to k, for some integer k. For each element in

2019-09-09T22:07:18+05:30Categories: 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 below graph are articulation points. The easiest solution is to

2019-07-07T20:41:45+05:30Categories: 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 source or a sink from a DAG, the resulting graph

2019-07-07T18:46:44+05:30Categories: 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 basically a binary tree used for storing the intervals or

2019-06-26T18:50:30+05:30Categories: 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 }; class RB_Node { Colour clr; int val; RB_Node left; RB_Node

2019-06-25T23:27:08+05:30Categories: 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 text, consider it a starting position of the pattern and

2019-06-24T22:44:16+05:30Categories: 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 Output: Function should return [9, 7, 6, 3, 8] Explanation:

2019-03-10T11:12:04+05:30Categories: Data Structure|

Breadth First Search Analysis

The analysis of the non-recursive version of Depth First Search is identical to Breadth First Search. We first consider a rough analysis of the algorithm in order to develop some intuition. We then build on this analysis to provide a more accurate estimate. Here is the pseudocode for the algorithm along with the estimated time complexity for each line:   The time

2019-02-21T23:47:39+05:30Categories: Data Structure|Tags: |
Go to Top