Discrete Math II - 11.4.1 Spanning Trees - Depth-First Search
ฝัง
- เผยแพร่เมื่อ 26 มิ.ย. 2024
- We continue our study of trees by examining spanning trees. Spanning trees are subgraphs of a graph that contain all vertices of the original graph. The resulting subgraph is a tree, so the graph is connected and contains no cycles.
In our first methodology, we will use a depth-first search. That means that we will begin creating our spanning tree by choosing a specific vertex starting point, then follow that path until we can no longer reach any unvisited vertices. We will then backtrack through the vertices to visit any remaining unvisited vertices.
Video Chapters:
Intro 0:00
What is a Spanning Tree 0:11
Depth-First Search/Backtracking Method 1:15
Using a Stack 4:00
Practice 6:42
Up Next 8:27
This playlist uses Discrete Mathematics and Its Applications, Rosen 8e Power Point slide decks to accompany the videos can be found here: bellevueuniversity-my.sharepo...
The entire playlist can be found here: • Discrete Math II/Combi...
Well explained video thank you very much!
Thank you for this video
Thanks for your help!
Thanks for the super thanks! ❤️
Thanks so much
you missed vertex 'j' in the practice question.
isn't f incident to a?
yes it is, i believe you just add it to the stack above C, and when you visit it you just remove it