Graph Theory Algorithms

Name: Graph Theory Algorithms
Rating: 4.5 (2112 reviews)

A complete overview of graph theory algorithms in computer science and mathematics.

Created byWilliam Fiset

Last updated 7/2020

English

English [Auto],Portuguese [Auto],

What you'll learn

Storage and representation of graphs (networks) on a computer
Common graph theory problems
Breadth first search algorithm
Depth first search algorithm
Various tree algorithms including: the height or a tree, finding the center of a tree, rooting a tree, and etc...
Dijkstra's algorithm
Topological sort algorithm
Shortest/longest path on a acyclic graph
Bellman Ford's algorithm
Floyd-Warshall all pairs shortest path algorithm
Finding bridges/articulation points
Finding strongly connected components (Tarjan's)
Travelling salesman problem (TSP)
How to find the maximum flow of a flow graph
Finding bipartite graph matchings
Various network flow algorithms including: Edmonds-Karp, Capacity Scaling, and Dinic's algorithm
Kruskal's Minimum Spanning Tree algorithm
The Lowest Common Ancestor (LCA) Problem

Course content

5 sections • 46 lectures • 9h 2m total length

Graph Theory Introduction14:24
Graph Theory Introduction Quiz
Problems in Graph Theory9:59
Depth First Search algorithm10:39
Breadth First Search algorithm7:45
Discover how breadth first search traverses a graph layer by layer using a queue to find shortest paths in unweighted graphs, with a practical solve and path reconstruction.
Breadth First Search grid shortest path16:50
DFS & BFS quiz

Introduction to Trees9:56
An introduction to tree algorithms. This video covers how trees are stored and represented on a computer.
Beginner tree algorithms9:31
Learn beginner-friendly tree algorithms by implementing recursive leaf-sum and binary-tree height calculations using depth-first search, with clear pseudocode and base-case strategies.
Rooting a tree4:57
Root a tree with depth-first search to obtain a rooted tree with directed edges. The method uses a designated root, maintains parent pointers, and avoids revisiting the parent during traversal.
Finding tree center(s)5:46
Identifying Isomorphic Trees10:52
Identifying Isomorphic Trees Source Code9:34
Tree quiz

Topological sort algorithm14:04
Learn how topological sort produces a valid ordering for directed acyclic graphs, useful for course prerequisites and program build dependencies, by performing depth-first search and producing a reverse ordering.
Classic graph theory algorithms quiz #1
Shortest/longest path on a Directed Acyclic Graph (DAG)10:14
Dijkstra's shortest path algorithm24:31
Dijkstra's shortest path algorithm | source code9:11
Explore the eager implementation of Dijkstra's shortest path algorithm in Java, including an indexed min d-ary heap, graph representation, edge relaxation, and path reconstruction.
Bellman-Ford algorithm15:16
Floyd-Warshall all pairs shortest path algorithm15:55
Floyd-Warshall all pairs shortest path algorithm | source code9:28
Learn the Floyd-Warshall all-pairs shortest path solver using an adjacency matrix, distance and next matrices, handling infinity and negative cycles, and reconstructing paths between node pairs.
Classic graph theory algorithms quiz #2
Bridges & Articulation points20:16
Bridges & Articulation points | source code9:22
Explore the algorithm to find bridges and articulation points in an undirected adjacency-list graph, with Java source code; learn how depth-first search and low-link values identify these points.
Tarjan's strongly connected components algorithm (UPDATED)17:41
Discover Tarjan's algorithm for finding strongly connected components by maintaining a stack and updating low-link values during DFS to identify SCCs in linear time.
Tarjan's strongly connected components algorithm | source code7:11
Travelling Salesman problem20:48
Travelling Salesman problem | source code13:32
Existence of Eulerian path and circuits9:40
Eulerian path algorithm15:34
Eulerian path source code8:17
Explore the Eulerian path algorithm's source code by instantiating the solver with a directed graph and retrieving the path, with in and out degree tracking, DFS, and GitHub-hosted examples.
Classic graph theory algorithms quiz #3

Max Flow Ford Fulkerson | Network Flow13:05
Discover how to compute maximum flow with the Ford-Fulkerson method on a flow graph using augmenting paths and residual edges to update bottlenecks.
Max Flow Ford Fulkerson | source code17:28
Unweighted bipartite matching | Network flow11:21
Bipartite Matching | The mice and owls problem | Network Flow8:27
Bipartite Matching | The elementary math problem | Network Flow10:44
Turns number pairs into a bipartite flow problem and solves it with max flow, building a graph from inputs to unique answers and deducing the operator for each pair.
Network flow quiz #1
Edmonds Karp | Network Flow9:31
Edmonds-Karp uses a breadth-first search to find the shortest augmenting path in the Ford-Fulkerson framework, delivering max flow with a strongly polynomial time bound O(V E^2).
Edmonds Karp | Network Flow | Source Code5:47
Capacity Scaling | Network Flow10:10
Capacity Scaling | Network Flow | Source Code6:23
Dinic's Algorithm | Network Flow11:39
Dinic's Algorithm | Network Flow | Source Code9:26

Union Find data structure5:45
Kruskal's Minimum Spanning Tree Algorithm6:14
Prim's Minimum Spanning Tree (lazy version)14:43
Prim's Minimum Spanning Tree (eager version)14:33
Learn Prim's eager algorithm for minimum spanning trees, using an index priority queue to maintain vertex edge pairs and relax edges. Compare with the lazy version and discuss graph performance.
Prim's Minimum Spanning Tree source code9:08
The sparse table data structure23:17
This is the sparse table data structure from my DS video series. We need to understand the sparse table DS to understand the solution to the Lowest Common Ancestor (LCA) problem
Sparse Table Source Code7:15
Lowest Common Ancestor (LCA) problem16:36
Learn to find the lowest common ancestor in rooted trees using an Euler tour, depth tracking, and a sparse table for fast queries.
Bonus topics quiz #1

Requirements

Exposure to computer science fundamentals (e.g: data structures, recursion, classes, OOP)

Description

Welcome to this Graph Theory Algorithms course!

Graph theory is a fundamental branch of mathematics that deals with the study of graphs, networks, and their applications in real-world scenarios. This course is designed to equip you with the necessary skills and knowledge to understand, analyze, and solve problems related to graph theory.

In this course, you will receive a thorough introduction to graph theory algorithms as they apply to computer science. Throughout the videos, we will cover a range of topics, including how to represent and store graphs on a computer, common graph theory problems encountered in real-world scenarios, famous graph traversal algorithms like DFS and BFS, as well as the lazy and eager versions of Dijkstra's shortest path algorithm. Additionally, we will explore what a topological sort is, how to identify one, and its applications. You will also learn about detecting negative cycles and finding shortest paths using the Bellman-Ford and Floyd-Warshall algorithms, discovering bridges and articulation points in graphs, understanding and detecting strongly connected components using Tarjan's algorithm, and finally, solving the traveling salesman problem with dynamic programming.

Throughout the course, we will use a hands-on approach to teaching, with plenty of examples and exercises to reinforce your understanding of the material. By the end of this course, you will have a deep understanding of graph theory algorithms and be able to apply them to solve real-world problems.

So, whether you are a computer science student, a software developer, or just someone interested in the fascinating world of graph theory, this course is for you! Join today and take your first step towards mastering the art of graph theory algorithms.

Who this course is for:

Anybody ready for a deep dive into graph theory!

Graph Theory Algorithms

What you'll learn

Explore related topics

Course content

Graph theory introduction and basics5 lectures • 1hr

Graph theory and trees6 lectures • 51min

Classic graph theory algorithms16 lectures • 3hr 41min

Network flow11 lectures • 1hr 54min

Bonus topics8 lectures • 1hr 38min

Requirements

Description

Who this course is for: