[prev] 8 [next]

Exercise #1: Traversal-induced Spanning Trees

A spanning tree of a graph
  • includes all vertices
  • uses a subset of edges, without cycles
Show the DFS and BFS spanning trees for the graph below, starting with 0:

[Diagram:Pic/traversal1.png]

Consider neighbours in ascending order