100+ Graph Algorithms and Techniques [Complete List]

In this article, we have listed 100+ problems on Graph data structure, Graph Algorithms, related concepts, Competitive Programming techniques and Algorithmic problems. You should follow this awesome list to master Graph Algorithms.

There are different categories of problems like Topological Sorting, Shortest Path in Graph, Minimum Spanning Tree, Maximum Flow Problem, Graph Coloring Problem, Maximum Matching Problem and much more.

Basics of Graph Algorithms

These are basic ways to represent a Graph and basic traversal techniques which you must learn about before attempting challenging problems.

• Graph Representation: Adjacency Matrix and Adjacency List: Learn how to represent Graph in a Data Structure.
• Depth First Search: Basic traversal technique.
• Breadth First Search: Another traversal technique.
• Bidirectional Search: An interesting traversal technique very few know. This is an efficient traversal technique compared to BFS and DFS.
• Comparison: DFS vs BFS
• Design Graph using OOP concepts in Java: Having a clean implementation of graph problem is important to make sure complex algorithms can be implemented easily. Using OOP concepts is the way to go.

Topological Sorting: order nodes in a Graph

Topplogical Sort is an important technique to order nodes in a Graph based on dependencies. It is used to solve several important problems.

• Topological Sorting using Depth First Search (DFS): Using DFS, we can generate Topological Sort.
• Topological Sort using Breadth First Search (BFS): Similar to DFS, we can use BFS to generate Topological sorting order.
• Topological Sorting using Kahn's Algorithm: Kahn's algorithm is a must know to do Topological Sorting.
• Applications of Topological Sort: Learn how Topological Sorting is used to solve real problems.

Shortest Path in Graph

Find the shortest path between two nodes in a Graph is a very important problem and several algorithms exist.

• Shortest Path using Topological Sort: Uisng Topological Sort, we can find the shortest path.

Some basic path related algorithms before finding the shortest path:

• Find and print all the paths between two vertices in a graph: This algorithm will help you find all paths between two nodes. This is often useful as a brute force approach for many problems.
• Count paths from Top Left to Bottom Right of a Matrix using Dynamic Programming: Finding all paths is a way to count the paths but there exists other optimal ways where we can find the the total count without finding the actual paths.
• Find if there exists a path between two nodes in a directed graph: Instead of finding the actual path, we find if such a path exists.

Standard algorithms to find shortest path:

• Dijkstra's algorithm: A Greedy Algorithm that is used to find shortest path between all nodes in O(E * V logV) time.
• Floyd-Warshall Algorithm: Shortest path between all pair of nodes in O(V³) time.
• Bellman Ford Algorithm: Finding shortest path from a node in O(V * E) time.
• Shortest Path Faster Algorithm: This is an improvement over Bellman Ford Algorithm and is widely used in Competitive Programming by top players.
• Johnson Algorithm: to find the shortest paths between all pair of vertices in O(V² logV + V * E) time.

Minimum Spanning Tree

Minimum Spanning Tree is a subset of a graph that connects all nodes by minimizing the cost of connecting edges. This is useful in solving several key problems.

• What is a Minimum Spanning Tree?: Learn the basics of MST.
• Kruskal Minimum Spanning Tree Algorithm: Kruskal's algorithm takes O(E logV) time.
• Prim Minimum Spanning Tree Algorithm: This is a Greedy algorithm and can be implemented in multiple ways. O(E + V logV) using fibonacci heap, O(E logV) using binary heap and O(V²) using adjacency matrix.
• Boruvka Minimum Spanning Tree: This algorithm takes O(E logV) time.
• Reverse Delete Algorithm for MST: This algorithm takes O(E logV (loglogV)³) time.

Maximum Flow Problem

Maximum Flow is an important graph problem with applications in Physics and Engineering.

• Overview of Maximum Flow Problem: Understand the Problem statement of Maximum Flow and related concepts.
• Ford Fulkerson Algorithm for Maximum flow in a graph: This technique takes O(V E²) time.
• Dinic's algorithm for Maximum flow in a graph: This technique takes O(E V²) time and is optimal compared to Ford Fulkerson Algorithm for dense graph.
• Edmonds Karp Algorithm for maximum flow: This technique takes O(V E²) time and is a modification of Ford Fulkerson Algorithm.
• Push Relabel Algorithm

Graph Coloring Problem

Graph Coloring is a key problem and is used to solve a wide range of challenging problems.

• Overview of Graph Colouring Algorithms: Understand the Graph Coloring problem and key concepts related to it.
• Welsh Powell Algorithm for graph coloring: This technique takes O(V²) time
• Wigderson Graph Colouring Algorithm: This technique takes O(V+E) time
• Graph Coloring Greedy Algorithm: This technique takes O(V² + E)
• Bipartite checking using Graph Colouring and Breadth First Search (BFS): This technique takes O(V+E) time.

Maximum Matching Problem

Maximum Matching is a problem of pairing nodes with a constraint and is important for solving a vast range of problems.

Understanding pairing nodes in Graphs (Maximum Matching): Basics of Maximum Matching
Hopcroft Karp algorithm: This technique takes O(E V^0.5) time.
Hungarian Maximum Matching Algorithm: This original algorithm took O(V⁴) time while an optimized version takes O(V³) time.
Blossom Maximum Matching Algorithm: This technique takes O(E V²) time while a much more complex variant of it takes O(E V^0.5) time.

Stable Marriage Problem

Stable Marriage Problem is variant of Maximum Matching problem and is used in real life problems.

Basics of stable matching: Overview of Stable Marriage Problem and related concepts.
Gale Shapley Algorithm for Stable Matching problem: Time Complexity of this technique is O(V²) time.
Stable Roommates Problem (Irving's Algorithm): Time Complexity of this technique is O(V²) time.
Variants of Stable Marriage Problem: There are several variants of Stable Marriage Problem
Hospital Residents Problem:

Maximum / Minimum Cut Problems

Minimum and Maximum cut problems are important problem as it reveals the weakest problem in a graph. In real problem, these algorithms are used to find weak points and fix them / or prepare for it.

Overview of Minimum Cut Problem: Overview of Minimum Cut Problem
Overview of Maximum cut problem: Overview of Maximum Cut Problem
Find cut edges in a graph: An algorithm to find cut edges in a graph.
Find articulation points or cut vertices in a graph: An algorithm to find cut vertices (not edges) in a graph.
Find articulation point in Graph: An algorithm to find articulation point in a graph.

• Find articulation point in Graph

Strongly Connected Components

Strongly Connected Components are sub-graphs where every vertex is connected by a path.

• Tarjan's Algorithm to find Strongly Connected Components: This algorithm takes O(V+E) time complexity.
• Kosaraju's Algorithm for Strongly Connected Components: This algorithm takes O(V+E) time using adjacency list or O(V²) time using adjacency matrix.

Transitive Closure

• Transitive Closure Of A Graph using Floyd Warshall Algorithm: This approach takes a time complexity of O(V³) with space complexity of O(V²).
• Transitive Closure Of A Graph using Graph Powering: Another innovative idea to find the transitive closure.

Travelling Salesman Problem

Travelling Salesman Problem is a NP-Complete problem and is one of the most difficult problems in Computer Science.

• Travelling Salesman Problem (Basics + Brute force approach): Basics of Travelling Salesman Problem along with Brute Force approach to solve this problem.
• Travelling Salesman Problem (Bitmasking and Dynamic Programming): A Dynamic Programming approach to solve Travelling Salesman Problem.
• Travelling Salesman Problem using Branch and Bound approach: A Branch and Bound approach to solve Travelling Salesman Problem.
• Approximation Algorithm for Travelling Salesman Problem: Tough NP-Complete problems are solved using approximation algorithm.

Other Graph based Problems

These are other core Graph based problems that you must learn about.

• Cycle in a graph using degree of nodes of the graph: We can check if a graph has a cycle using the degree of nodes.
• Algorithm to find all bridges in a Graph: Similar to cut problem, we have to find bridges in a graph.
• Algorithm to find Level of each node from root node: Breadth First Search technique can be used to find level of nodes. There are other techniques as well.
• Finding nodes at distance K from a given node: An optimal algorithm to find nodes at a particular distance.
• Minimum number of nodes to be removed such that no subtree has more than K nodes: A seemingly challenging problem with a simple solution.
• Finding Diameter of Tree using Height of each Node: Diameter is the longest path and is an important problem for solving several problems.
• Diameter of N-ary tree using Dynamic Programming: A Dynamic Programming algorithm to find the Diameter.
• Hamiltonian Path: A key concept.
• Hamiltonian Cycle: Another key concept.
• Find Mother Vertex in a Graph: Time Complexity of this algorithm is O(V+E) time.
• Fundamentals of Euler path in Graph Theory: Euler Path is a key concept in graph.
• Transpose Graph: Another key concept.
• Using Farach Colton and Bender Algorithm to solve LCA: LCA is a key problem and this algorithm takes O(V) time for each query.
• Solving Vertex Cover Problem: This covers different algorithms to solve vertex cover problem and takes the time complexity from from O(2^N) to O(N²).
• Clique in Graphs: A key concept arising to several challenging problems.
• Centroid Decomposition of Tree: A divide and conquer technique on graphs.
• Karp's Minimum Mean Cycle Algorithm: An algorithm to find minimum mean cycle.
• What is a Euler or Eulerian tour?: A key concept.
• Fleury’s Algorithm: Finding Eulerian tours in a graph: An algorithm to find Euler tours.
• Number of paths with k edges using Dynamic programming and Divide and Conquer: A very important problem whose ideas can be used to solve a wide range of similar problems.
• Shortest Path with k edges using Dynamic Programming: A variant of the above problem.

Applications of Graph in Real problems

• How TensorFlow uses Graph data structure concepts?: Application of graph ideas in TensorFlow, a leading Machine Learning Library by Google.
• Algorithm behind Bill splitting app: A graph based algorithm to power a bill splitting application.

With this article at OpenGenus, you must have a strong hold of Graph data structure, related concepts and Algorithmic problems based on it. Keep practicing.

Try learning other algorithmic concepts:

• 100+ Dynamic Programming based Problems
• 50+ Problems based on Linked List
• 50+ Problems based on Array
• 50+ Problems based on Binary Tree: Binary Tree is a tree data structure and can be visualized as a graph. To have a strong hold of Graph, practice these problems as well.