Graph Algorithms Checklist: 13 weeks free course

Graph Representation: Adjacency Matrix & Adjacency List is a technique used to represent graphs in computer science, where an adjacency matrix is a square matrix used to represent a finite graph, and an adjacency list is a collection of unordered lists used to represent a finite graph.

Directed Graph vs Undirected Graph explains the difference between these two types of graphs and how they can be represented mathematically.

Depth-First Search is an algorithm used to traverse a graph or tree in which the search moves down a branch as far as possible.

Breadth-First Search (BFS) is an algorithm used to traverse a graph or tree in which the search visits all the vertices at the same level before moving down to the next level. BFS is also a popular algorithm used to find shortest paths between nodes.

Depth First Search vs Breadth First Search is a comparison of two traversal algorithms used in graph theory.

Bidirectional Search Algorithm is a graph traversal algorithm that searches for a path between two nodes in a graph by simultaneously running two breadth-first searches, one from the start node and one from the end node, until the two searches meet in the middle.

Topological Sort using BFS works by initially finding all the nodes in the graph with zero incoming edges and adding them to a queue. Then it repeatedly removes the first node from the queue, adds it to the topologically sorted list, and removes all of its outgoing edges. If any nodes have zero incoming edges as a result of this removal, they are added to the queue. This process continues until the queue is empty and all nodes have been added to the topologically sorted list.

Learn how to perform Topological Sorting using DFS. The algorithm works by recursively visiting each node in the graph using DFS and keeping track of a list of nodes in the order in which they finish being visited.

Kahn's algorithm for topological sorting works by initially finding nodes in the graph with zero incoming edges, removing them and their outgoing edges from the graph, and repeating the process with the updated graph. This continues until all nodes have been removed and the algorithm outputs the nodes in the order in which they were removed.

Applications of Topological Sort discusses various real-world applications of topological sorting. It provides examples of how the technique can be used in areas such as project scheduling, build systems, and task management. Additionally, it discusses the benefits of using topological sorting in these contexts, such as improved efficiency and reduced errors.

Shortest path using topological sort article explains an algorithm to find the shortest path between two vertices in a directed acyclic graph (DAG), using a topological sorting technique and dynamic programming.

Counting Paths in a Matrix is a dynamic programming algorithm that counts the number of unique paths from the top left corner to the bottom right corner of a matrix, moving only right or down, by computing a table of intermediate counts for each position in the matrix and using this table to gradually update the total count. In the context of matrices, intermediate counts refer to the number of elements that are present between two specific elements in a matrix.

Print all the paths between two vertices article explains how to find and print all possible paths between two vertices in a graph, including paths that pass through other vertices, using Depth First Search(DFS) and backtracking.

Learn how to find the shortest path with k edges using an algorithm to find the shortest path between two vertices in a graph, with a constraint that the path must have a fixed number of edges, using dynamic programming.

Path between nodes in a directed graph article explains a recursive graph traversal algorithm used to find all possible paths between two nodes in a directed graph using DFS.

Dijkstra's Algorithm is a pathfinding algorithm that finds the shortest path between a starting node and all other nodes in a weighted graph, using a priority queue to efficiently explore the graph and update the distances to each node. Also learn about the algorithm's time and space complexity.

Shortest Path Faster Algorithm is an improvement on Dijkstra's algorithm for finding the shortest path in a weighted graph that allows negative edge weights. It uses a queue-based approach to efficiently explore the graph and update the distances to each node.

Floyd-Warshall Algorithm is a dynamic programming algorithm that finds the shortest path between all pairs of nodes in a weighted graph, by computing a table of intermediate distances between all pairs of nodes and using this table to gradually update the shortest path.

Bellman-Ford Algorithm is an algorithm for finding the shortest path between a starting node and all other nodes in a weighted graph, even when the graph has negative edge weights. It works by iteratively relaxing the edges of the graph to gradually find the shortest path. In addition, also understand the time and space complexity of the algorithm.

Johnson Algorithm is an algorithm for finding the shortest path between all pairs of nodes in a weighted graph. It works by first reweighting the edges of the graph using a potential function, and then using Dijkstra's algorithm to find the shortest path between each pair of nodes.

DeSopo-Pape algorithm article explains a single-source shortest path algorithm that handles negative edge weights by using a stack and a priority queue, and can work on both directed and undirected graphs. It is an improvement over Dijkstra's algorithm.

Minimum Spanning Tree is a tree that spans all the vertices of a connected, weighted graph with the least possible total edge weight.

Kruskal's Minimum Spanning Tree Algorithm involves sorting the edges by weight and adding them one by one to the tree as long as they don't create a cycle. Also analyse the time and space complexity of the algorithm.

Prim's Minimum Spanning Tree Algorithm involves starting with an arbitrary vertex and adding the edge with the smallest weight to the growing tree until all vertices are included. Additionally, learn about the algorithm's time and space complexity.

Boruvka's Minimum Spanning Tree Algorithm involves creating a forest of trees where each tree is a single vertex, and then repeatedly adding the cheapest edge that connects two different trees until all vertices are in a single tree.

Reverse Delete Algorithm involves starting with all edges in a graph and removing them one by one in non-increasing order of weight until the remaining edges form a tree.

Maximum Flow Problem involves finding the maximum flow that can be sent through a network from a source to a sink. Here, the term "flow" refers to some quantity, such as data, that is being transported through a network represented as a directed graph. Solving the maximum flow problem has many real-world applications, such as optimizing transportation networks, managing internet traffic, and designing water distribution systems.

Ford-Fulkerson Algorithm is based on the concept of augmenting paths and works by iteratively finding augmenting paths from the source to the sink until no more paths can be found. This algorithm makes use of Depth First Search (DFS). In a flow network, an augmenting path is a path that can be used to increase the amount of flow that can be sent from the source to the sink.

Dinic's Algorithm is based on the concept of layered graphs and works by iteratively building a layered graph and finding blocking flows until no more blocking flows can be found. A layered graph is a type of graph where the nodes are partitioned into layers, with each layer representing a different distance from the source. In other words, nodes in the same layer are at the same distance from the source.

Edmonds-Karp Algorithm for Maximum Flow uses a breadth-first search to find augmenting paths and then calculates the maximum amount of flow that can be sent from the source to the sink.

Push-Relabel Algorithm works by maintaining a preflow, which is a partial flow that satisfies certain conditions, and then iteratively pushing flow from nodes with excess flow to nodes with deficit flow.

Graph Colouring Algorithms involve assigning colors to the vertices of a graph such that adjacent vertices do not have the same color.

Learn about Bipartite Checking using BFS. A graph is bipartite if it is possible to divide its vertices into two independent sets such that every edge connects a vertex from one set to a vertex from the other set. We use Breadth First Search (BFS) to color the vertices of the graph in two colors, starting from an arbitrary vertex. If, during this process, an edge is found that connects two vertices of the same color, then the graph is not bipartite. If all edges can be colored without any conflicts, then the graph is bipartite.

Graph Colouring using Greedy Algorithm is a widely used algorithm for graph coloring that assigns colors to vertices in a way that minimizes the total number of colors used.

Wigderson algorithm is a randomized algorithm for coloring graphs. The algorithm works by randomly partitioning the vertices of the graph into subsets, and then recursively coloring each subset using a reduced color palette.

Welsh-Powell Algorithm for Graph Coloring is a simple heuristic algorithm used to color graphs that sorts the vertices in decreasing order of degree and assigns colors to each vertex, making sure that no adjacent vertices have the same color.

Explore the flood fill algorithm, a technique used to fill a connected region of pixels with a particular color.

Maximum matching is a graph theory problem that involves finding the largest set of edges in a graph such that no two edges share a common vertex. It has applications in fields such as computer networking, image processing, and social network analysis.

The Hungarian algorithm is a well-known algorithm for solving the maximum matching problem in bipartite graphs. It works by augmenting the matching until no further improvement is possible.

The Hopcroft-Karp algorithm is an efficient algorithm for finding the maximum matching in a bipartite graph. It works by alternating between finding augmenting paths and updating the matching, and has been used in applications such as online advertising and recommendation systems.

The Blossom algorithm is a graph theory algorithm for finding maximum matchings in general graphs. It works by finding augmenting paths in a way that reduces the size of the graph, and has applications in areas such as transportation and supply chain management.

Stable matching is a problem in which two groups of individuals have preferences for members of the other group, and the goal is to find a stable pairing of individuals such that no two individuals prefer each other to their current partners. Also learn about the Gale-Shapley algorithm, which is a popular algorithm for solving this problem.

Variants of stable matching are modifications to the original stable matching problem that involve additional constraints or objectives. This article discusses two common variants: incomplete preference lists, in which some individuals do not have preferences for all members of the other group, and weighted preferences, in which individuals have numerical rankings of their preferences that are used to compute a weighted stability score for each pairing.

Maximum Cut Problem article discusses the maximum cut problem in graph theory, which involves dividing the nodes of a graph into two disjoint sets with the maximum number of edges between them.

Minimum Cut Problem article explains the minimum cut problem in graph theory, which involves finding the smallest cut in a graph that divides the nodes into two disjoint sets.

Understand how to find articulation points or cut vertices in a graph. In a graph, connected components are groups of vertices that are connected to each other by edges. Articulation points are the vertices in a graph that, if removed, would increase the number of connected components in the graph. If you remove this vertex, the graph might split into multiple smaller pieces, and each piece would become a connected component on its own.

Learn how to find cut edges in a graph and how to identify them. Cut edges are the edges in a graph that, if removed, would increase the number of connected components in the graph.

Karger Algorithm to Find Minimum Cut is a randomized algorithm used to find the minimum cut in a graph. The algorithm works by iteratively contracting two randomly chosen vertices until only two vertices are left. The cut that corresponds to these two vertices is the minimum cut of the original graph.

Euler or Eulerian Tour is a path that visits every edge exactly once. Euler tour can be found in both directed and undirected graphs.

Tarjan's Algorithm is a graph traversal algorithm used to find strongly connected components in a directed graph. It uses a stack-based approach and a recursive depth-first search.

Kosaraju's Algorithm for Strongly Connected Components is an algorithm used to find strongly connected components in a directed graph. It uses two depth-first searches and a stack-based approach.

Learn how to find transitive closure using Floyd Warshall Algorithm. The Floyd Warshall algorithm computes the shortest path between all pairs of vertices in a graph. By modifying the algorithm to compute boolean values instead of distances, we can use it to find the transitive closure of a graph, which indicates whether there is a path between every pair of vertices.

Transitive Closure using Graph Powering explains how to find the transitive closure of a graph. In this method, the transitive closure matrix is computed iteratively by raising the adjacency matrix of the graph to increasingly higher powers.

Travelling Salesman Problem - Brute Force explains one of the simplest approaches for finding the shortest possible route that visits every city on a given list exactly once and returns to the starting city. The brute force algorithm involves generating all possible permutations of the cities and calculating the distance of each permutation.

Travelling Salesman Problem - Branch and Bound explains an optimization algorithm for solving the Travelling Salesman Problem. The Branch and Bound algorithm uses a tree structure to explore the possible solutions to the problem, pruning branches that cannot possibly lead to the optimal solution. This algorithm is more efficient and can handle larger sets of cities.

Travelling Salesman Problem - Dynamic Programming explains another optimization algorithm for solving the Travelling Salesman Problem. The Dynamic Programming algorithm works by breaking down the problem into smaller sub-problems and solving them recursively.

Travelling Salesman Problem - Approximation algorithm uses the concept of Minimum Spanning Tree to solve this problem. This approach involves finding the best way to connect the cities, creating a circle that goes through all the cities and finding the shortest way to do so

Explore the problem of making a large island by changing the value of some 0s to 1s in a given matrix.

Maximum Area of Island is a common problem in computer science where you need to find the largest connected group of 1's in a grid of 1's and 0's. This problem can be solved using techniques such as depth-first search or breadth-first search.

Learn about the problem of finding the number of islands in a given matrix, where an island is a group of connected 1s (representing land) surrounded by 0s (representing water). Explore two approaches to solve this problem: depth-first search (DFS) and breadth-first search (BFS).

Explore the Number of Closed Islands article that explains an algorithm to determine the number of isolated regions within a binary matrix where 0 represents water and 1 represents land.

In Cycle using Degree of Nodes in a Graph, you'll learn how to detect cycles in a graph using the degree of nodes.

Fleury Algorithm: Finding Eulerian Tours in a Graph introduces the Fleury algorithm, which finds an Eulerian tour in a graph. Eulerian tour is a path in a graph that visits every edge exactly once and returns to its starting point.

Learn about Hamiltonian Path and Hamiltonian Cycle and explore algorithms to find them.

Vertex Cover Problem explains how to find the smallest set of vertices that covers all edges in a graph.

Clique in Graphs are a subset of vertices where every vertex is connected to every other vertex in the subset. Learn about the basics of cliques, including properties, types and algorithms for finding cliques in a graph, such as brute force, Bron-Kerbosch algorithm, and cliquer algorithm. Explore some applications of cliques, such as in social networks, gene expression networks, and computational biology.

Bron-Kerbosch algorithm is a recursive algorithm for finding all maximal cliques in an undirected graph. The algorithm works by selecting a pivot vertex and iterating through all possible combinations of vertices that are adjacent to the pivot, checking whether each combination forms a clique, and recursively calling the algorithm on the remaining vertices.

Learn how to find all cliques of a given size k in an undirected graph. The algorithm is based on the Bron-Kerbosch algorithm, and it involves iterating through all possible subsets of vertices, checking whether each subset forms a clique of size k, and keeping track of all such cliques.

Explore a greedy algorithm for finding a single maximal clique in an undirected graph. The algorithm starts with a random vertex and iteratively adds adjacent vertices to the clique until no more vertices can be added.

Farach-Colton and Bender Algorithm (LCA) describes the Farach-Colton and Bender algorithm, which can be used to solve the lowest common ancestor problem in trees.

Mother Vertex in Graph explains how to find a vertex that can reach all other vertices in a directed graph, using Tarjan's algorithm which involves identifying strongly connected components.

Number of Paths with K Edges explains how to count the number of paths in a graph with a fixed number of edges, using dynamic programming to build a matrix of counts for each pair of vertices and number of edges.

In Fundamentals of Euler Path, understand the concepts and properties of Euler paths and circuits in graphs, including the conditions for their existence and how to construct them.

Learn how to create the transpose of a graph, which is a new graph with all the edges reversed, using an adjacency matrix or an adjacency list.

Learn how to find all the bridges in an undirected graph, which are edges whose removal would disconnect the graph, using Tarjan's algorithm and depth-first search.

Karp's Minimum Mean Cycle Algorithm first finds the shortest paths to all vertices using Bellman-Ford, and then iteratively adds edges to the graph to find the minimum mean weight cycle. The mean weight of a cycle is the sum of the weights of the edges in the cycle divided by the number of edges. The minimum mean weight cycle is the cycle with the smallest mean weight in the graph. It is useful in various applications such as transportation and logistics.

Learn how to detect cycles in an undirected graph using Depth First Search (DFS) algorithm and the disjoint-set data structure.

Biconnected Graph is a connected graph that remains connected even after any vertex (or node) is removed. The article explains the concepts of biconnected components and biconnected graphs and presents algorithms for finding them.

Entropy of Graph explains how to calculate the entropy of a graph, which measures the degree of randomness or uncertainty in the graph, using information theory.

Biconnected Components article explains an algorithm used in graph theory to identify the set of edges that would remain if any single vertex was removed from the graph.

In Centroid Decomposition of Tree a tree is recursively divided into smaller subtrees by finding its centroid (i.e., the node that minimizes the maximum subtree size), and each subtree is processed separately. We can use this to solve tree based problems like finding the diameter of a tree, computing the distance between two nodes etc.

Diameter Using Height of Node article explains how to find the diameter of a tree using the height of its nodes, by computing the heights of each node and finding the pair of nodes with the maximum distance between them.

Diameter of n-ary Tree (DP) article explains how to find the diameter of an n-ary tree using dynamic programming. An n-ary tree is a tree data structure in which each node can have at most n children.

Learn how to find Ancestors of Node in Binary Tree using iterative and recursive approaches.

Nodes which are at distance K from root article explains how to find all nodes in a binary tree that are at a distance of K from the root node, using a simple depth-first search approach and maintaining the level of each node in the tree.

Learn how to find all nodes in a binary tree that are at a distance of K from a given node , using a combination of depth-first search and breadth-first search. The algorithm first finds the target node and then performs a breadth-first search to find all nodes at a distance of K from it.

Learn how to find the minimum number of nodes that need to be removed from a tree in order to ensure that no subtree in the resulting tree has more than K nodes. The algorithm recursively computes the size of each subtree and performs a post-order traversal to mark the nodes that need to be removed. Traversal begins first the left subtree, then the right subtree, and finally the root node.

Maximum Sum Leaf to Root Path article discusses an algorithm for finding the maximum sum leaf-to-root path in a binary tree, which is the path with the highest sum of node values from any leaf node to the root node. A "leaf node" refers to a node in a tree data structure that does not have any branches or sub-nodes stemming from it.

Explore how to find height or depth of Binary Tree using an algorithm to find the height or depth of a binary tree, a tree data structure where each node has at most two child nodes.

Minimum Number of Swaps Required to Convert Binary Tree to Binary Search Tree explains an algorithm that converts a binary tree into a binary search tree with minimum swaps, using a combination of in-order traversal and a modified selection sort.

Learn how to find the level or depth of a node in a binary tree from the root node using recursion and depth-first search.

Learn how to find maximum or minimum element in Binary Search Tree using an algorithm used to find the maximum or minimum element in a binary search tree, a data structure that allows for efficient searching, insertion, and deletion operations.

Depth Limited Search is a variant of depth-first search where a maximum depth limit is set for the search. This is useful in cases where we don't want the search to go too deep and want to limit the amount of resources used by the search algorithm.

Iterative Deepening Search is a search algorithm that combines the benefits of both depth-first search and breadth-first search. It starts with a depth limit of 0 and gradually increases the depth limit until the goal is found. This algorithm is useful in cases where the search space is large and the depth of the solution is unknown.

Iterative Inorder Traversal is a method for traversing a binary tree in an inorder fashion (i.e., visiting the left subtree, then the root, then the right subtree) without using recursion. It uses a stack data structure to simulate the recursive calls used in the recursive version of the inorder traversal algorithm.

Understand how to create an alien dictionary given a list of words in a specific order. It presents an approach to solve this problem using topological sorting, which is a technique used to order the vertices in a directed graph.

De Bruijn Sequences are special sequences that contain every possible k-length sequence of a given alphabet exactly once as a substring. They have applications in various fields such as coding theory, cryptography, and bioinformatics.

Graph and Subgraph Isomorphism is the problem of determining whether a given graph contains a subgraph that is structurally identical to a given graph. It is an important problem in computer science and has applications in various fields such as chemistry, biology, and computer vision.

Graph using OOP Java tutorial explains how to implement a graph data structure using object-oriented programming principles in Java, a popular programming language.

Learn about the algorithm behind Bill Splitting App which involves dividing bills among friends based on their respective shares, and ensuring that everyone pays and receives the correct amount.

Two Sum Problem in Binary Search Tree explains how to solve the two sum problem for a binary search tree, which involves finding two nodes in the tree that add up to a given target value. Learn a simple recursive approach that utilizes the properties of binary search trees to achieve linear time complexity. This problem is applicable in real-life scenarios such as financial transactions, data analysis, engineering, and image processing.

Learn about the applications of Graph in TensorFlow. Tensorflow is an open-source machine learning framework that uses a computation graph to represent a machine learning or deep learning model, with each node in the graph representing an operation and each edge representing the flow of data between these operations.