今天的主題是DFS Spanning tree 跟 BFS Spanning tree，先說說樹是什麼吧。

樹 tree 的定義

沒有環路的連通圖。

• 此圖不是樹，因為有環路。
  

• 此圖不是樹，因為不連通。
  

• 此圖為樹，既連通又沒有環路
  

展開樹(生成樹) Spanning Tree

一個連通圖形G的 Spanning Tree定義為 :

1. T是G的子圖。
2. T包含G所有的頂點 (V(T) = G(T))。
3. T是一棵樹。

• 除非G本身就是樹，否則一個連通圖的Spanning Tree可能不只有一個。
• 以下圖G為例子，找出幾棵 Spanning Tree
  
• Spanning Tree (1)
  
• Spanning Tree (2)
  
• Spanning Tree (3)
  
• 此範例的Spanning Tree太多，在此僅列出3個作為舉例。

根據定義，一個連通圖的Spanning Tree，必定包含所有頂點，因此我們可以在走訪圖形的點時，將所有經過的邊逐一加入Spanning Tree中，構成 DFS Spanning tree 跟 BFS Spanning tree 。

• 使用之前的圖做為例子
  
• BFS Spanning tree
• 
• DFS Spanning tree
• 

參考

細談資料結構 第六版
ISBN 978-986-312-014-8