Graph Algorithms

Solving Course Scheduling Problem using Topological Sort

In this article at OpenGenus, we will solve the famous course scheduling problem and it's variations using the graph algorithm known as Topological Sort.

C++

Floyd Warshall Algorithm in C++

Floyd Warshall Algorithm is one of the famous graph algorithm for finding shortest path between a node to every other node. In this article at OpenGenus, we have implemented Floyd Warshall Algorithm in C++ programming language.

Time Complexity

Time Complexity of Topological Sort

In this article at OpenGenus, you will learn about Time Complexity of Topological Sort. Specifically, the version of Topological Sort using Khan's Algorithm, which uses Breath First Search with a Queue.

Python

Adjacency list and matrix in Python using OOP concepts

In this article at OpenGenus, we have implemented Adjacency list and matrix in Python using OOP concepts. This is a must for mastering Graph Algorithm in Python.

C++

Adjacency list and matrix in C++

In this article, we will take a look at the concept of Adjacency list and Adjacency matrix and how to implement both data structures in C++ Programming Language.

Algorithms

Minimum cost to connect all points (using MST)

In this article, we will understand how to solve the minimum cost to connect all the points problem using Minimum Spanning Tree.

Algorithms

Number of closed islands [2 solutions]

In this article, we have explored how to find the Number of closed islands in a graph. We have presented two approaches using the concept of BFS/ DFS and Union Find.

Graph Algorithms

Biconnected Components [Explained + Algorithm to find it]

Turns out, biconnected components are one of the most important topic in design analysis of algorithms, data structures and in many competitive exams. Biconnected components are defined as a maximal biconnected subgraph.

Graph Algorithms

Maximum sum leaf to root path

In this article, I will be discussing about Maximum sum leaf to root path in Binary tree along with time and space complexity.

Algorithms

Graph and subgraph isomorphism

In this article, we will learn about graph and subgraph isomorphism and the algorithms to check for graph and subgraph isomorphism.

Algorithms

Biconnected graph

A biconnected graph is a graph that is connected and has no articulation points.

Graph Algorithms

Entropy of Graph

In graph theory, entropy is the index for describing the structure and function of a network. Entropy is related to amount of information stored in a graph. This is used in field of computer science to check compression of data as compressed data is more random and hence has higher entropy.

Algorithms

Iterative In-order Traversal

In this article, we have explored the concept of Iterative In-order Traversal along with detailed step by step example and complete implementation.

Graph Algorithms

Directed vs Undirected Graph

In this article, we have explained the differences between Directed and Undirected Graphs based on different attributes such as adjacency matrix, entropy and much more.

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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

Algorithms

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.

Algorithms

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.