×

Home Discussions Write at Opengenus IQ

×

Graph Algorithms

Graph algorithms are algorithms that work over graph data structures and are able to solve certain problems efficiently and intuitively. It is the basis of features used by billions of people like Facebook's graph API, friend recommendations, Google's knowledge graph and many others.

Maximum area of island

In this article, we have presented an efficient algorithm to find the maximum area of island in a grid. This includes the concept of BFS and DFS.

Graph Algorithms

D’Esopo-Pape Algorithm

In this article, we are going to explore D’Esopo-Pape Algorithm, a single source shortest path algorithm proposed by D’Esopo and Pape in 1980. This is an efficient alternative to the famous Dijkstra's Algorithm, but has an exponential time complexity in the worst case.

Graph Algorithms

Depth Limited Search

In this article, we have explored Depth Limited Search algorithm which is a restricted version of Depth First Search (DFS).

Search Algorithms

Iterative Deepening Search

In this article, we are going to discuss about the Iterative Deepening Search Technique. It is also, known as Iterative Deepening Depth-First Search ( IDDFS) and is a modification of Depth First Search and Depth Limited Search.

De Bruijn Sequences

In this article, we have explored De Bruijn Sequences and 3 algorithms to calculate De Bruijn Sequences using ideas like Hamiltonian Cycle, Euler's path.

Detect Cycle in Undirected Graph using Union Find algorithm

In this article, we've explored the approach to detect a cycle in undirected graph using union-find algorithm. This takes O(VE) Time Complexity.

Time Complexity

Time and Space Complexity of Kruskal’s algorithm for MST

In this article, we have explored Time and Space Complexity of Kruskal’s algorithm for MST (Minimum Spanning Tree). We have presented the Time Complexity of different implementations of Union Find and presented Time Complexity Analysis of Kruskal’s algorithm using it.

Time Complexity

Time & Space Complexity of Dijkstra's Algorithm

In this article, we have explored the Time & Space Complexity of Dijkstra's Algorithm including 3 different variants like naive implementation, Binary Heap + Priority Queue and Fibonacci Heap + Priority Queue.

Making A Large Island by changing one 0 to 1

In this article, we have explored an insightful approach/ algorithm to find the largest island by changing one 0 to 1 in MxN matrix. This is an extension of Number of Islands in MxN matrix (of 0 and 1).

Time & Space Complexity of Bellman Ford Algorithm

In this post, we do an analysis the Bellman Ford's single source shortest path graph algorithm to find its computational Time and Space complexity for Best case, Worst case and Average Case.

Alien Dictionary problem: Sorted order of characters

In this article, we are given a sorted list of words in some alien dictionary. Based on the list, we have to generate the sorted order of characters in that alphabet. This problem can be solved using the idea of Topological Sort and Direct Acyclic Graphs.

Number of Islands in MxN matrix (of 0 and 1)

In this article, we have explored an insightful approach/ algorithm to find the number of islands in MxN matrix. An extension of this algorithm is used by online battleship game engine.

Flood Fill Algorithms

Flood Fill algorithm is an Algorithm that determines the area connected to a given node in a N-dimensional array. Some operations are performed on the connected nodes like color change. This is also known as Seed Fill Algorithm.

Karger’s algorithm to find Minimum Cut

In this article, we will explore how the Karger's algorithm works to find the minimum cut in a graph and its C++ implementation. This is a randomized algorithm based on Graphs.

Adjacency Matrices Explained: A Representation of Graphs

In this article, we have explained the idea of Adjacency Matrix which is good Graph Representation. We have presented it for different cases like Weighted, undirected graph along with implementation and comparison with Adjacency List.

Graph Algorithms

100+ Graph Algorithms and Techniques [Complete List]

We have listed 100+ problems on Graph data structure, Graph Algorithms, related concepts, Competitive Programming techniques and Algorithmic problems.

Two Sum Problem in Binary Search Tree

We have solved the Two Sum Problem in Binary Search Tree using three different approaches involving Depth First Search, Inorder Traversal and Augmented Binary Search Tree.

Shortest Path using Topological Sort

We have explained the algorithm to find the shortest path in a Directed Acyclic Graph using Topological Sort.

Karp's Minimum Mean Cycle Algorithm

We have presented Karp's Minimum Mean Cycle Algorithm along with C++ Implementation. Karp's theorem and Complexity Analysis.

Minimum Cut Problem [Overview]

We have covered the basics of Minimum Cut Problem, its applications like Network Reliability, algorithms like Ford-Fulkerson Algorithm to solve it and much more.

Reverse Delete Algorithm for MST

We have explored the Reverse Delete Algorithm for finding Minimum Spanning Tree (MST) along with time and space complexity, implementation and application.

Applications of Topological Sort [Explained]

In this article, we have covered various Applications of Topological Sort in depth. Topological Sort of a directed graph is a linear ordering of its vertices.

Minimum number of nodes to be removed such that no subtree has more than K nodes

The article contains editorial + implementation for Finding minimum number of nodes to be removed such that no sub tree has more than K nodes.

Variants of Stable Marriage Problem

We have explored the variants of stable marriage problem like Egalitarian Stable Matching, Minimum Regret Stable Matching, Stable marriage with ties, Stable marriage with incomplete lists and others.

Basics of stable matching

We have covered the basics of Stable Matching and algorithms associated with it like Gale Shapley Algorithm, Irving's Algorithm, Hospital Residents Problems and more.