Graph Algorithms

Find if there exists a path between two nodes in a directed graph

You are given a directed graph and two vertices on it. Your task is to find if there exists a path between the first vertex to the second vertex or not.

Algorithms

Push Relabel Algorithm

Push relabel algorithm is also known as Preflow Push algorithm. It is used for computing maximum flows in a flow network.

Algorithms

Travelling Salesman Problem using Branch and Bound approach

In this article we have discussed about the travelling salesman problem and the branch and bound method to solve the TSP.

Algorithms

Travelling Salesman Problem (Bitmasking and Dynamic Programming)

In this article, we will start our discussion by understanding the problem statement of The Travelling Salesman Problem perfectly and then go through the basic understanding of bit masking and dynamic programming.

Algorithms

Travelling Salesman Problem (Basics + Brute force approach)

In this article we will start our discussion by understanding the problem statement of The Travelling Salesman Problem perfectly and then go through the naive bruteforce approach for solving the problem using a mathematical concept known as "permutation"

Algorithms

Transitive Closure Of A Graph using Graph Powering

In this article, we will begin our discussion by briefly explaining about transitive closure and graph powering. We will also see the application of graph powering in determining the transitive closure of a given graph.

Algorithms

Transitive Closure Of A Graph using Floyd Warshall Algorithm

In this article, we will begin our discussion by briefly explaining about transitive closure and the Floyd Warshall Algorithm. We will also see the application of Floyd Warshall in determining the transitive closure of a given graph.

Algorithms

Overview of Maximum Flow Problem

The aim of the max flow problem is to calculate the maximum amount of flow that can reach the sink vertex from the source vertex keeping the flow capacities of edges in consideration.

Algorithms

Topological Sort using Breadth First Search (BFS)

In this article, we have explored how to perform topological sort using Breadth First Search (BFS) along with an implementation. We have compared it with Topological sort using Depth First Search (DFS).

Algorithms

DFS vs BFS (in detail)

DFS and BFS are two fundamental graph traversal algorithms and both are significantly different each with its own applications. DFS is used Kosaraju's algorithm while BFS is used in shortest path algorithms.

Algorithms

Bidirectional Search

Bidirectional Search is Graph Search Algorithm where two graph traversals (BFS) take place at the same time and is used to find the shortest distance between a fixed start vertex and end vertex. It is a faster approach, reduces the time required for traversing the graph.

Algorithms

Breadth first search (BFS)

Breadth first search (BFS) is one of the most used graph traversal techniques where nodes at the same level are traversed first before going into the next level. Queue is used internally in its implementation.

Algorithms

Topological Sorting using Kahn's Algorithm

We have explored topological sorting using Kahn's algorithm. The basic idea is that a DAG G has at least one vertex with in-degree 0 and one vertex with out-degree 0.

Algorithms

Fundamentals of Euler path in Graph Theory

In this article, we have explored the basic ideas/ terminologies to understand Euler Path and related algorithms like Fleury's Algorithm and Hierholzer's algorithm.

Algorithms

Shortest Path with k edges using Dynamic Programming

Given a weighted directed graph, we need to find the shortest path from source u to the destination v having exactly k edges. Brute force approach takes O(V^k) time complexity which we reduce to O(V^3 * k) using dynamic programming

Algorithms

Number of paths with k edges using Dynamic programming and Divide and Conquer

Given a directed graph, we need to find the number of paths with exactly k edges from source u to the destination v. A brute force approach has time complexity which we improve to O(V^3 * k) using dynamic programming which we improved further to O(V^3 * log k) using a divide and conquer technique.

Algorithms

Find height or depth of a binary tree

Length of the longest path from the root node to a leaf node is the height of the binary tree. We find it in linear time using a recursive algorithm

Algorithms

Overview of Graph Colouring Algorithms

In this introductory article on Graph Colouring, we explore topics such as vertex colouring, edge colouring, face colouring, chromatic number, k colouring, loop, edge, chromatic polynomial, total colouring and various algorithmic techniques for graph colouring.

Algorithms

Algorithm for finding minimum or maximum element in Binary Search Tree【O(log V) / O(V)】

Binary Search Tree is a node-based binary tree data structure and finding the maximum or minimum element take O(log N) in average and can take O(N) in the worst case to O(1) in the best case.

Algorithms

Algorithm for finding the minimum number of swaps required to convert a binary tree to binary search tree

We developed an algorithm for finding the minimum number of swaps required to convert a binary tree to binary search tree. The Idea is do the inorder traversal of binary tree and store it in an array.Then find the minimum number of swaps require to sort an array which is the output we want.

Algorithms

Find and print all the paths between two vertices in a graph【O((2^V)*(V+E))】

Given a directed graph, a vertex ‘v1’ and a vertex ‘v2’, print all paths from given ‘v1’ to ‘v2’. The idea is to do Depth First Traversal of given directed graph. Start the traversal from v1. Keep storing the visited vertices in an array say path[]. If we reach the vertex v2, pathExist becomes true

Algorithms

Find Mother Vertex in a Graph【O(V+E)】

mother vertex in a graph is a vertex from which we can reach all the nodes in the graph through directed path. If there exist mother vertex (or vertices), then one of the mother vertices is the last finished vertex in DFS. (Or a mother vertex has the maximum finish time in DFS traversal).

Algorithms

Kosaraju's Algorithm for Strongly Connected Components 【O(V+E)】

Kosaraju algorithm is a DFS based algorithm used to find Strongly Connected Components(SCC) in a graph. It is based on the idea that if one is able to reach a vertex v starting from vertex u, then one should be able to reach vertex u starting from vertex v

Algorithms

Count paths from Top Left to Bottom Right of a Matrix using Dynamic Programming【O(M*N)】

Count all the possible paths from top left to bottom right of a m x n matrix with the constraints that from each cell you can either move only to right or down. Brute force approach takes exponential time while dynamic programming takes O(M*N) time complexity

Algorithms

Using Farach Colton and Bender Algorithm to solve LCA【O(V) query】

The basic idea of Farach Colton and Bender Algorithm is to traverse all the nodes using the Depth First Search graph traversal and keep a record of all the visited nodes and there corresponding heights. This allows to answer LCA queries in O(V) time complexity