Graph 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

algorithm

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.

algorithm

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.

algorithm

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.

algorithm

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

algorithm

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).

algorithm

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

algorithm

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

algorithm

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

algorithm

Johnson Algorithm to find the shortest paths between all pair of vertices

Johnson Algorithm is used to find shortest paths between every pair of vertices in a given weighted directed graph and here weights may be negative. Johnson Algorithm uses both Dijkstra and Bellman-Ford algorithms as subroutines.

algorithm

Centroid Decomposition of Tree

Centroid Decomposition is a divide and conquer technique which is used on trees. Given a tree with N nodes, a centroid is a node whose removal splits the given tree into a forest of trees, where each of the resulting tree contains no more than N/2 nodes.

algorithm

Clique in Graphs

A clique is a subset of vertices of an undirected graph G such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs.

algorithm

Solving Vertex Cover Problem from O(2^n) to O(n^2)

Vertex Cover Problem is a known NP Complete problem. We will see Naive approach and Dynamic programming approach to solve the vertex cover problem for a binary tree graph and reduce the complexity from O(2^n) to O(n^2).

algorithm

Understanding pairing nodes in Graphs (Maximum Matching)

A maximal matching is a matching M of a graph G with the property that if any edge not in M is added to M, it is no longer a matching, that is, M is maximal if it is not a subset of any other matching in graph G. We cover Blossom, Hungarian and Hopcroft Karp algorithm

algorithm

Blossom Maximum Matching Algorithm

The blossom algorithm, sometimes called the Edmonds' matching algorithm, can be used on any graph to construct a maximum matching. The blossom algorithm improves upon the Hungarian algorithm by shrinking cycles in the graph to reveal augmenting paths. The blossom algorithm will work on any graph.

algorithm

Hungarian Maximum Matching Algorithm

The Hungarian maximum matching algorithm, also called the Kuhn-Munkres algorithm, is a O(V3) algorithm that can be used to find maximum-weight matchings in bipartite graphs, which is sometimes called the assignment problem. A bipartite graph can easily be represented by an adjacency matrix

algorithm

Hopcroft Karp algorithm

The Hopcroft–Karp algorithm is an algorithm that takes as input a bipartite graph and produces as output a maximum cardinality matching, it runs in O(E√V) time in worst case.

algorithm

Hamiltonian Cycle

A Circuit in a graph G that passes through every vertex exactly once is called a "Hamilton Cycle". The Worst Case complexity when used with DFS and back tracking is O(N!).

algorithm

Hamiltonian Path

Hamiltonian Path is a path in a directed or undirected graph that visits each vertex exactly once. The problem to check whether a graph (directed or undirected) contains a Hamiltonian Path is NP-complete, so is the problem of finding all the Hamiltonian Paths in a graph.

algorithm

Bipartite checking using Graph Colouring and Breadth First Search (BFS) [O(V+E) time]

The algorithm to determine whether a graph is bipartite or not uses the concept of graph colouring and BFS and finds it in O(V+E) time complexity on using an adjacency list and O(V^2) on using adjacency matrix. It is used to decode codewords and model situations in cloud computing and big data

algorithm

Topological Sorting using Depth First Search (DFS)

We will implement Topological sorting using Depth First Search in linear time O(V+E). Topological Sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. It is useful in instruction scheduling and other

algorithm

Tarjan's Algorithm to find Strongly Connected Components

Tarjan's Algorithm is an efficient graph algorithm to find the strongly connected components in a directed graph in linear time by utilizing Depth First Search traversal of a graph. The key idea used is that nodes of strongly connected component form a subtree in the DFS spanning tree of the graph.

tensorflow

How TensorFlow uses Graph data structure concepts?

In this article, we explain various concepts in TensorFlow such as tensors, dataflow graphs and several optimizations such as decision tree pruning and demonstrate the use of graph data structure and algorithm concepts in TensorFlow

graph algorithm

Graph Representation: Adjacency Matrix and Adjacency List

A Graph is represented in two major data structures namely Adjacency Matrix and Adjacency List. This forms the basis of every graph algorithm. In this article, we have explored the two graph data structures in depth and explain when to use one of them

algorithm

Graph Coloring Greedy Algorithm [O(V^2 + E) time complexity]

In this article, we have explored the greedy algorithm for graph colouring. graph coloring is a special case of graph labeling ; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints.