Depth-First Search

• 一些基本定義：
  1.Subgraph

  點和邊都是原圖的一小部分
  

  2.Spanning subgraph

  點與原圖一樣，但邊少了一些
  

  3.connected

  任兩點都有一個路徑連通起來
  

  4.connected component
  5.(free)Tree

  connected且無cycle
  -->以前談到的為rooted tree（差在有無指定root）
  

  6.forest

  很多個tree
  

  7.Spanning tree

  在connected graph中為一個spanning subgraph且為tree
  

• Traversal of graphs
  1.DFS
  2.BFS

• DFS
  1.能全部走一遍
  2.辨別是否connected
  3.看幾個connected component
  4.複雜度：O(m+n)
  5.用最少的memory
  6.找出兩點間的path
  7.找出有無cycle
  8.類似preorder
  9.用stack