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
Search (BFS) is an algorithm used to traverse a graph or tree in which the search visits all the
the same level before moving down to the next level. BFS is also a popular algorithm
used to find shortest paths between nodes.
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.
Week 2: Topological Sorting
Topological Sort (BFS)
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.
Topological Sorting (DFS)
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.
Algorithm for Topological Sorting
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
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
Week 3: Shortest Path in Graph
Shortest path using topological sort
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
Counting Paths in a Matrix
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.
all the paths between two vertices
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.
Shortest path with k edges
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
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
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.
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.
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.
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.
Week 4: Minimum Spanning Tree
Introduction to Minimum Spanning Trees
Spanning Tree is a tree that spans all the vertices of a connected, weighted graph with the least
possible total edge weight.
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
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.
Week 5: Maximum Flow Problem
Introduction to Maximum Flow Problem
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
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.
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.
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.
Week 6: Graph Coloring Problem
Overview of Graph Colouring Algorithms
Graph Colouring Algorithms involve assigning colors to the vertices of a graph such
that adjacent vertices do not have the same color.
Bipartite Checking using BFS
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.
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.
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
Week 7: Maximum Matching Problem
Introduction to Maximum Matching
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.
Hungarian Maximum Matching Algorithm
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.
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.
Blossom Maximum Matching Algorithm
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.
Week 7: Stable Marriage Problem
Matching and Gale-Shapley algorithm
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
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.
Week 8: Maximum / Minimum Cut Problems
Maximum Cut Problem
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
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.
Articulation Points or Cut Vertices in a Graph
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.
Edges in a Graph
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.
Week 8: Strongly Connected Components
or Eulerian Tour
Eulerian Tour is a path that visits every edge exactly once. Euler tour can be found in both directed
and undirected graphs.
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.
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
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.
Week 9: Travelling Salesman Problem
Travelling Salesman Problem - Brute Force
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
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
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
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
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
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).
of Closed Islands
Explore the Number
of Closed Islands article that explains an algorithm to determine the number of isolated regions
binary matrix where 0 represents water and 1 represents land.
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.
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.
Algorithm to Find Cliques of a Given Size k
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.
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.
of Paths with K Edges
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.
Fundamentals of Euler Path
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.
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.
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
Entropy of Graph
how to calculate the entropy of a graph, which measures the degree of randomness or uncertainty in the
using information theory.
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.
Week 12: Other Tree based Problems
Decomposition of Tree
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.
using Height of Node
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
of n-ary Tree (DP)
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.
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.
Minimum Nodes Removed (No Subtree More than K Nodes)
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
Maximum Sum Leaf to Root Path
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
refers to a node in a tree data structure that does not have any branches or sub-nodes stemming from it.
or Depth of Binary Tree
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.
Number of Swaps Required to Convert Binary Tree to
Binary Search Tree
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
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
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.
Week 13.b: Miscellaneous Graph Theory Problems
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.
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 Subgraph Isomorphism
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.
Week 13.c: Graph Data Structure using Java
using OOP in Java
Graph using OOP
Java tutorial explains how to implement a graph data structure using object-oriented programming
principles in Java, a popular programming language.
Week 13.d: Applications of Graph in Real life
Algorithm Behind Bill Splitting App
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.
Sum Problem in Binary Search Tree
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.
Use of Graph data structure in TensorFlow
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