Graph Theory Algorithms

  1. Home
  2. Algorithms
  3. Graph Theory Algorithms

Tags: Algorithms

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

Last updated 2022-01-10 | 4.8

- Storage and representation of graphs (networks) on a computer
- Common graph theory problems
- Breadth first search algorithm

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

* Requirements

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

Description

  • 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 • 54 lectures

Graph theory introduction and basics 7 lectures

Graph Theory Introduction Preview 14:24

Graph Theory Introduction Quiz

Graph Theory Introduction Quiz

Problems in Graph Theory Preview 09:59

Depth First Search algorithm Preview 10:39

Breadth First Search algorithm Preview 07:45

Breadth First Search grid shortest path Preview 16:50

DFS & BFS quiz

DFS & BFS quiz

Graph theory and trees 7 lectures

Introduction to Trees Preview 09:56

An introduction to tree algorithms. This video covers how trees are stored and represented on a computer.

Beginner tree algorithms Preview 09:31

Rooting a tree Preview 04:57

Finding tree center(s) Preview 05:46

Identifying Isomorphic Trees Preview 10:52

Identifying Isomorphic Trees Source Code Preview 09:34

Tree quiz

Tree quiz

Classic graph theory algorithms 19 lectures

Topological sort algorithm Preview 14:04

Classic graph theory algorithms quiz #1

Topsort quiz

Shortest/longest path on a Directed Acyclic Graph (DAG) Preview 10:14

Dijkstra's shortest path algorithm Preview 24:31

Dijkstra's shortest path algorithm | source code Preview 09:11

Bellman-Ford algorithm Preview 15:16

Floyd-Warshall all pairs shortest path algorithm Preview 15:55

Floyd-Warshall all pairs shortest path algorithm | source code Preview 09:28

Classic graph theory algorithms quiz #2

Shortest path quiz

Bridges & Articulation points Preview 20:16

Bridges & Articulation points | source code Preview 09:22

Tarjan's strongly connected components algorithm (UPDATED) Preview 17:41

Tarjan's strongly connected components algorithm | source code Preview 07:11

Travelling Salesman problem Preview 20:48

Travelling Salesman problem | source code Preview 13:32

Existence of Eulerian path and circuits Preview 09:40

Eulerian path algorithm Preview 15:34

Eulerian path source code Preview 08:17

Classic graph theory algorithms quiz #3

Eulerian paths and circuits quiz

Network flow 12 lectures

Max Flow Ford Fulkerson | Network Flow Preview 13:05

Max Flow Ford Fulkerson | source code Preview 17:28

Unweighted bipartite matching | Network flow Preview 11:21

Bipartite Matching | The mice and owls problem | Network Flow Preview 08:27

Bipartite Matching | The elementary math problem | Network Flow Preview 10:44

Network flow quiz #1

Network Flow Quiz #1

Edmonds Karp | Network Flow Preview 09:31

Edmonds Karp | Network Flow | Source Code Preview 05:47

Capacity Scaling | Network Flow Preview 10:10

Capacity Scaling | Network Flow | Source Code Preview 06:23

Dinic's Algorithm | Network Flow Preview 11:39

Dinic's Algorithm | Network Flow | Source Code Preview 09:26

Bonus topics 9 lectures

Union Find data structure Preview 05:45

Kruskal's Minimum Spanning Tree Algorithm Preview 06:14

Prim's Minimum Spanning Tree (lazy version) Preview 14:43

Prim's Minimum Spanning Tree (eager version) Preview 14:33

Prim's Minimum Spanning Tree source code Preview 09:08

The sparse table data structure Preview 23: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 Code Preview 07:15

Lowest Common Ancestor (LCA) problem Preview 16:36

Bonus topics quiz #1