Graph theory algorithms visualized

An introduction to graph theory and problems it can solve, with various real life examples, and what is a graph?

Important points that have to be read to have a better learning experience

Types of graph (edgeless, complete, bipartite...) and important terms that are good to know for this course, with illustrations

A quiz to practice on terminology and types of graphs

One of the possible ways to represent a graph in memory: the adjacency list. Explained in this lecture with an example and the implementation

Another way of representing graphs in memory: the adjacency matrix. Also explained with an example and the implementation

A comparison between the adjacency list and the adjacency matrix in terms of time and space resources, to know which one to choose

One of the most fundamental graph algorithms to know: Depth-first search. It's a traversal algorithm that is explained in this lecture with a full animated example, implementation, and complexity analysis

A classic problem to practice on depth-first search, where the goal is to find if there exists a path from a source vertex to a destination vertex

A solution to the "Path exists in graph" problem, explained and implemented

Another fundamental graph algorithm to know: Breadth-first search. It's a traversal algorithm that is explained in this lecture with a full animated example, implementation, and complexity analysis

A classic problem to practice on breadth-first search, where the goal is to find the minimum number of edges required to go from a source vertex to a destination vertex

A solution to the "Minimum edges from start to end" problem, explained and implemented

Graphs can appear in many ways, not in the form of an adjacency list or matrix only, they can be implicit. For example, a grid can be considered as a graph! This is what we talk about in this lecture, with examples and implementation of dfs and bfs on a grid

A quiz to practice on algorithms learnt during this chapter (depth-first search and breadth-first search)

We can have a situation where elements have dependencies, for example tasks that require finishing other tasks before doing the current one (e.g.: Before painting a wall, we need to build it). And we may want a sequential ordering of elements that handles dependencies, this is where topological sorting comes in!

A first algorithm that is based on depth-first search to apply topological sorting, explained with an animated example then the implementation and time complexity analysis

A second algorithm that is based on breadth-first search to apply topological sorting, Kahn's algorithm, explained with an animated example then the implementation and time complexity analysis

An interesting problem that we solve by using topological sorting, the "Find all possible recipes" problem!

A solution to the "Find all possible recipes" problem, explained with an animated example then the implementation and time complexity analysis

One of the most important subtopics of graph theory: Shortest path problem, the problem of finding the shortest path from a source vertex to a destination vertex, introduced in this lecture with different variations

A fundamental graph theory algorithm: Dijkstra's algorithm, an algorithm that solves the single-source shortest path problem, explained in this lecture with the intuition behind it, a full example, pseudocode, implementation, path reconstruction, comparison between various implementations (sorted array, binary heap, Fibonacci heap), time complexity analysis, and limitations

Another single-source shortest path problem algorithm: Bellman-Ford algorithm. Explained in this lecture with the intuition behind it, an example, its dynamic programming aspect, implementation, time complexity analysis, and a comparison with Dijkstra's algorithm

A fundamental algorithm that solves the all-pairs shortest path problem: Floyd-Warshall algorithm. Explained in this lecture with the intuition behind it, an example, its dynamic programming aspect, implementation, time complexity analysis, and why it's efficient with dense graphs

Another all-pairs shortest path problem algorithms: Johnson's algorithm. An algorithm that combines Dijkstra's algorithm and Bellman-Ford algorithm to create an algorithm that is efficient for sparse graphs. It's explained in this lecture with an example, how to reweight edges, why it works, implementation, time complexity analysis, and a comparison with Floyd-Warshall algorithm

We may want to find the shortest path in an unweighted graph, such that the length of a path is defined by its number of edges. Instead of turning it to a weighted graph and use one of the previous algorithms, we can use a more efficient algorithm, it's explained in this lecture with an example, implementation, and time complexity analysis

Directed acyclic graphs are special cases of graphs where we can use more efficient shortest path algorithms, the topic of this lecture. We will study two approaches, an example for each, with implementation and time complexity analysis for both of them

A quiz to strengthen knowledge on algorithms taught in this chapter

Trees are one of the types of graphs, that come in many applications, this is why we study them in this lecture with definitions and examples, and how to check if a given graph is a tree or not

Out-trees are in reality the classic tree data structure you probably know about, you know, the one that has a root made of a value and multiple trees as children. We study the concept in this lecture with definitions and examples, and how to turn a graph into an out-tree

A problem to practice on trees: All nodes distance k in a tree, we want nodes we can reach by performing k moves from the start node

A solution to the "All nodes distance k in a tree" problem, explained with an example, implementation, and time complexity analysis

Minimum spanning trees (MSTs) are an important topic in graph theory, they appear in many real life problems. We introduce them in this lecture.

Prim's algorithm is one of the algorithms that find the minimum spanning tree of a graph, we study it in this lecture with a full example, implementation, and how we improve the approach and use a Fibonacci heap to have a lower time complexity

Kruskal's algorithm is another minimum spanning tree algorithm that works that always adding the lightest edge that doesn't form a cycle in the MST. We explain it in this lecture with an example, implementation, and why we use a disjoint-set (union find) data structure to improve the time complexity

A problem to practice on minimum spanning trees: Min cost to connect all points.

A solution to the "Min cost to connect all points" problem, illustrated with an example and the implementation, and which algorithm to use, Prim or Kruskal, to get a better time complexity

We may want a path that passes from each edge exactly once, that's what we call a Eulerian path. In this lecture, we study Eulerian paths, Eulerian cycles, when is a graph considered semi-Eulerian, Eulerian, and what are conditions it needs to respect, all that with examples of course

Hierholzer's algorithm is an algorithm that finds a Eulerian path in a graph, we study it in this lecture with a full animated example, implementation, and time complexity analysis

A problem to practice on Eulerian paths: Reconstruct itinerary

A solution to the "Reconstruct itinerary" problem, with an example, implementation, and time complexity analysis

We may want a path that passes from each vertex exactly once this time, that's what we call a Hamiltonian path. In this lecture, we study Hamiltonian paths, Hamiltonian cycles, when is a graph considered semi-Hamiltonian, Hamiltonian, and do we have ways to know if a graph is Hamiltonian quickly, with examples obviously

In this lecture, we discuss an algorithm that uses backtracking to find a Hamiltonian cycle in a graph, with a full animated example, implementation, and time complexity analysis

A multiple choices questions quiz on Eulerian and Hamiltonian paths/cycles to strengthen the knowledge gained during this chapter

A quiz to strengthen your knowledge on concepts and algorithms presented in this chapter

Let's say you have multiple rides to perform in a day, each with a start and end time. You may not be able to use only one car for them all because some of them may overlap in time. How to calculate the minimum number of required cars then? This is where graph coloring comes in, discover it in this lecture along with multiple examples, important definitions, lower and upper bounds of the minimum number of colors (chromatic number), and the four color theorem

Checking if a graph can be colored with only 2 colors is equivalent to checking if it's bipartite, this is what we learn to do in this lecture, with an example, implementation, and time complexity

To find if a graph can be colored with at most k colors and find its chromatic number, we can use backtracking, this is what we learn to do in this lecture, with an example, implementation, and time complexity

The algorithm of the previous lecture is really slow, we may want a faster algorithm, one that runs in linear time, even if it doesn't always give the optimal result. This is what we learn about in this lecture: greedy coloring, an approximation algorithm for graph coloring problem. You will find an example, its lower and upper bound, implementation, and time complexity analysis

Greedy coloring doesn't always give good results, it may give really bad examples because of a bad vertex traversal ordering. To improve the way we choose the ordering, we can use heuristics such as Welsh-Powell and DSatur, the topic of this lecture. Both heuristics are illustrated with an example, implementation, and time complexity analysis

Sudoku is a popular grid game that you probably played before, in this problem you are asked to solve it by using graph coloring

In this lecture, we learn how to solve a Sudoku grid with graph coloring, with an example and the implementation

A quiz to strengthen knowledge on TSP and its algorithms

A quiz to strengthen your knowledge on the maximum flow problem and its algorithms

Practice problem: Keys and rooms, the LeetCode problem number 841

We solve the Keys and rooms practice problem, by using both depth-first search and breadth-first search

Practice problem: Rotting oranges, the LeetCode problem number 994

We solve the Rotting oranges problem by applying our knowledge on implicit graphs, because we work on a grid

Practice problem: Alternating color path, the LeetCode problem number 1129

We solve the Alternating color path problem, we see how we can adapt bfs to introduce a new constraint

Practice problem: Sum of distances in tree, the LeetCode problem number 834