DFS/BFS Trees are Indeed Acyclic (Graphs: Algorithms & Theory)

Channel:

PageWizard Games, Learning & Entertainment

Subscribers:

785

Published on September 28, 2022 5:00:10 PM ● Video Link: https://www.youtube.com/watch?v=H-AZ0OY8ZAY

Duration: 20:29

16 views

1

In today's lesson, we learn that indeed a DFS/BFS traversal's forward/discovery edges form a spanning forest. We prove it formally!

Time Stamps:
0:00 Recap, reminder of what a DFS/BFS tree is, with example using DFS.
5:11 Claim to be proven, game plan
8:38 Proof
19:28 Summary
20:10 Closing

Have a beautiful day!

Supporters (to date of publication, by tier (top to bottom)):
----------------------------------------------------------
Patreon Supporters (General Support):
Draikou
Patreon Supporters (Basic Support):
Patreon Supporters (Supporter Access!):
Eric R
-----------------------------------------------------------
Become a supporter today! To support my work and mission to provide free or accessible Computer Science education (especially in theory), subscribe to the channel, share my videos. Please donate and contribute to support my work for more content:
PATREON: https://www.patreon.com/PageWizard
SUBSCRIBESTAR: https://www.subscribestar.com/drpage
PAYPAL: https://paypal.me/pagewizard

Follow also at:
FACEBOOK: https://www.facebook.com/DanielRPage
TWITTER: https://twitter.com/PageWizardGLE
QUORA: https://www.quora.com/profile/Daniel-R-Page
TWITCH: https://www.twitch.tv/pagewizard

#ComputerScience
#Algorithms
#graphtheory