Summary
Full Transcript
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: https://bellevueuniversity-my.sharepoint.com/:f:/g/personal/kbrehm_bellevue_edu/Ei9DcmrOBTlAuMxWUoq9ZqsB14M60jcpob-xdAYS6ruVWw?e=uP9KN0 The entire playlist can be found here: https://www.youtube.com/playlist?list=PLl-gb0E4MII0sGLCJeqDB3y63HZ6lM5LJ
Continue this lesson in the app
Install CourseHive on Android or iOS to keep learning while you move.
