×
Home Discussions Write at Opengenus IQ
×
  • #7daysOfCode
  • C Interview questions
  • Linux 💽
  • 🔊 Data Structures
  • Graph Algorithms
  • Dynamic Programming 💑
  • Greedy Algo 📔
  • Algo Book 🧠
  • String Algo 🧬
  • Join our Internship 🎓
  • Home

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.

Algorithms

Diameter of N-ary tree using Dynamic Programming

We are given input as the reference to the root of an N-ary tree. We need to calculate the diameter of the tree that is the longest path between any two nodes using Dynamic Programming.

Amruta U. Koshe
Algorithms

Finding Diameter of Tree using Height of each Node

We have explored the algorithm on how to find the diameter of the tree using height of each node. This will take linear time O(V+E) time complexity.

Hrithik Shrivastava
Software Engineering

Design Graph using OOP concepts in Java

You are going to learn to design and implement the graph data structure using OOP (Object Oriented Programming) Concepts. We will implement in Java but the ideas are applicable in any language.

Yash Shah
Algorithms

Maximum cut problem

In this article we'll be discussing on the concept of Maximum cut problem. Firstly will understand its basic concept with Introduction. Secondly, with a graph example will deep-dive into the concept.

Shiva Basava P
Algorithms

Find articulation point in Graph

In this article we'll be discussing on how to find articulation point in Graph. Firstly we'll discuss on the Introduction to Articulation Points. Secondly, we'll understand the Articulation Points concept with a graph example. At the end will write a Pseudo code & implementation for the same.

Shiva Basava P
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.

Hrithik Shrivastava
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.

Shiva Basava P
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.

Harini Jeyaraman Harini Jeyaraman
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.

Shiva Basava P
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.

Raghav Somani
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.

Sargam Monga Sargam Monga
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.

Abhijit Tripathy Abhijit Tripathy
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.

Abhijit Tripathy Abhijit Tripathy
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"

Abhijit Tripathy Abhijit Tripathy
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.

Abhijit Tripathy Abhijit Tripathy
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.

Abhijit Tripathy Abhijit Tripathy
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.

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

NIKHIL PRATAP SINGH NIKHIL PRATAP SINGH
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.

Anand Saminathan
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.

Sargam Monga Sargam Monga
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.

Sourajeet Mohanty Sourajeet Mohanty
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.

Shradha Sehgal
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.

Sourajeet Mohanty Sourajeet Mohanty
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

Sadanand Vishwas Sadanand Vishwas
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.

Sadanand Vishwas Sadanand Vishwas
×

Visit our discussion forum to ask any question and join our community

View Forum
OpenGenus IQ © 2021 All rights reserved â„¢ [email: team@opengenus.org]
Top Posts LinkedIn Twitter