深度算法

深度算发：

 

 

 

 

縱向優先搜尋 (depth-first search)

---

depth-first search 是以某一節點為出發點，不斷地前進拜訪未曾被拜訪過的節點，直到無路可走或是所有相鄰的節點都已經拜訪過為止，然後再退回前一個節點，尋找沒有拜訪過的節點，直到所有相鄰的節點都已被拜訪過。因此，進行 depth-first search 時，需要使用 stack ，以便記錄所走過的路徑。

1. 起始。
   
   
   
2. 假設從 a 開始拜訪，我們將 a 放進stack。
   
   

   STACK
   stack top	a

   
   a 有三個節點可以拜訪 (b, c, d)。
   
   
3. 假設我們選擇拜訪 b ，我們將 b 放進stack。
   
   

   STACK
   stack top	b
   	a

   
   b 有三個節點可以拜訪 (c, e, f)。
   
   
4. 假設我們選擇拜訪 c ，我們將 c 放進stack。
   
   

   STACK
   stack top	c
   	b
   	a

   
   c 只能拜訪 f。
   
   
5. 我們選擇拜訪 f ，我們將 f 放進stack。
   
   

   STACK
   stack top	f
   	c
   	b
   	a

   
   由於 f 沒有節點可以拜訪，我們把 f 從stack取出。
   

   STACK
   stack top	c
   	b
   	a

   
   由於 c 也沒有節點可以拜訪，我們也把 c 從stack取出。
   

   STACK
   stack top	b
   	a

   
   b 可以拜訪 e。
   
   
6. 我們選擇拜訪 e ，我們將 e 放進stack。
   
   

   STACK
   stack top	e
   	b
   	a

   
   由於 e 沒有節點可以拜訪，我們把 e 從stack取出。

   STACK
   stack top	b
   	a

   
   由於 b 也沒有節點可以拜訪，我們也把 b 從stack取出。
   

   STACK
   stack top	a

   
   a 可以拜訪 d。
   
   
7. 我們選擇拜訪 d ，我們將 d 放進stack。
   
   

   STACK
   stack top	d
   	a

   
   d 只能拜訪 g。
   
   
8. 我們選擇拜訪 g ，我們將 g 放進stack。
   
   

   STACK
   stack top	g
   	d
   	a

   
   由於 g 沒有節點可以拜訪，我們把 g 從stack取出。
   

   STACK
   stack top	d
   	a

   
   由於 d 也沒有節點可以拜訪，我們也把 d 從stack取出。
   

   STACK
   stack top	a

   
   由於 a 也沒有節點可以拜訪，我們也把 a 從stack取出。
   此時 stack 已經全部清空，depth-first search完成。