Chapter 3 | Graph Traversal Algorithms - #SoMEpi

0:00 Intro
0:46 Definition of a Tree
1:49 BFS and DFS
4:03 Knight’s Shortest Path
4:50 Maze Generation with DFS
5:50 Connectivity Check
6:24 Cycle Detection
7:01 Topological Sorting
8:35 A Simple Spanning Tree Algorithm
10:38 Recap - Euler Trails and Circuits
13:17 Definition of a Bridge
14:10 Number of Connected Components of a Graph
15:04 Fleury’s Algorithm
18:04 BFS | Intro
18:48 Parent | Level | Visited
20:32 Queue Data Structure
21:47 BFS - Python Code with Animation
26:39 DFS | Intro
27:18 Idea behind the DFS Implementation
29:34 Stack Data Structure
30:42 DFS - Python Code with Animation
39:05 Outro

Python Code

Animations have been created with Manim, Adobe Premiere Pro and Blender.

▶ Did You Try Your Best - Alec Slayne
▶ Honesty Matters - Kikoru
▶ Light-Footed - Bonnie Grace
▶ Pattern View - David Celeste
▶ Resolution - Marten Moses
▶ Fractal Patterns - Bonnie Grace
▶ Parallel Existence - Raymond Grouse
▶ Organic Textures - David Celeste
▶ National Security - Isaac Larson
▶ Rememberance - Fabien Tell
▶ In a Gyroscope - T. Morri
▶ Weapon of Choice - Fabien Tell
▶ Unknown Phenomenon - Dream Cave
▶ Trembling Anticipation - Dream Cave
▶ Turncoat - Michael Rothery
▶ Fall Afoul - Jon Sumner
▶ Silent Witness - Dream Cave
▶ Cutting Corners - Jon Sumner

Sound effects:

Blender-Model:

SVG/PNG graphic files:

#graphtheory #mathematics

[adamjam]

what an animation! really nice to watch

[JorgetePanete]

Is there an online algorithm in the class L for traversing an undirected cyclic graph where each vertex has a unique label and each vertex and edge can be visited more than once?

[what_if-kyml]

can you make dp series with visualization, there are graph visualization videos but not dp or greedy ones

[carpa_guitar]

Amazing animations. Did you use Manim?