Graph Algorithms

Algorithm to find Level of each node from root node

In this article we will be discussing on how to find the level of each node in a graph, the algorithm that we will be using to find the level of each node is breadth first search.

Algorithms

Algorithm to find all bridges in a Graph

In this article we'll be discussing on the algorithm to find all bridges in a Graph. Firstly we'll discuss on the Introduction to Bridges. Secondly, we'll understand the bridge concept with a graph example.

Algorithms

Cycle in a graph using degree of nodes of the graph

There are different ways of detecting cycle in a graph. Let us understand how to detect cycles in an undirected graph using the degree of each vertex.

Algorithms

Transpose Graph

In this article, we will explore the idea of Transpose Graph along with the basics of Graph Data Structures. We have presented an algorithm to get the transpose of a graph as well.

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.

Problems on Binary Tree

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.

Problems on Binary Tree

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.

Problems on Binary Tree

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