DFS Spanning Tree (DST)

DFS Spanning Tree (DST)

Given a graph 𝐆 = (𝐕, 𝐄) and given a node 𝑋₁, a DFS spanning tree 𝐓 of 𝐆 is generated by applying a depth-first-search traversal over the graph, yielding an ordering 𝑑 = (𝑋₁, …, 𝑋_𝑛). The DFS spanning tree 𝐓 of 𝐆 is defined as the tree rooted at the first node, 𝑋₁, and which includes only the traversed edges of 𝐆

DFS spanning tree 𝐓 = (𝐕, 𝐄’) where:

• 𝐕 = same 𝐕
• 𝐄’ = {(𝑋_𝑖, 𝑋_𝑗) | 𝑋_𝑗 traversed from 𝑋_𝑖 by DFS traversal}