广度算法：
-------------------------------------------------------------
橫向優先搜尋 (breadth-first search)
breadth-first search 是以某一節點為出發點，先拜訪所有相鄰的節點。再依序拜訪與剛才被拜訪過的節點相鄰但未曾被拜訪過的節點，直到所有相鄰的節點都已被拜訪過。因此，進行 breadth-first search 時，需要使用 queue ，以便記錄拜訪的順序。
- 起始。
- 假設從 a 開始拜訪，我們將 a 放進queue。
| QUEUE
|
| queue front
| a
|
| queue back
| |
接下來把 a 從queue中取出，a 有三個節點可以拜訪 (b, c, d)。
- 假設我們選擇先拜訪 b ，我們將 b 放進queue。
| QUEUE
|
| queue front
| b
|
| queue back
| |
- 再來，假設我們選擇拜訪 c ，我們將 c 放進queue。
| QUEUE
|
| queue front
| b
|
|
| c
|
| queue back
| |
- 我們選擇拜訪 d ，我們將 d 放進queue。
| QUEUE
|
| queue front
| b
|
|
| c
|
|
| d
|
| queue back
| |
由於已經拜訪過所有與 a 相鄰的節點，我們從queue中取出下一個元素 b， b 有兩個節點可以拜訪 (e, f)。
| QUEUE
|
| queue front
| c
|
|
| d
|
| queue back
| |
- 假設我們選擇先拜訪 e ，我們將 e 放進queue。
| QUEUE
|
| queue front
| c
|
|
| d
|
|
| e
|
| queue back
| |
- 再來我們選擇拜訪 f ，我們將 f 放進queue。
| QUEUE
|
| queue front
| c
|
|
| d
|
|
| e
|
|
| f
|
| queue back
| |
由於已經拜訪過所有與 b 相鄰的節點，我們從queue中取出下一個元素 c， c 沒有節點可以拜訪。
| QUEUE
|
| queue front
| d
|
|
| e
|
|
| f
|
| queue back
| |
由於已經拜訪過所有與 c 相鄰的節點，我們再從queue中取出下一個元素 d， d 可以拜訪 g。
| QUEUE
|
| queue front
| e
|
|
| f
|
| queue back
| |
- 我們選擇拜訪 g ，我們將 g 放進queue。
| QUEUE
|
| queue front
| e
|
|
| f
|
|
| g
|
| queue back
| |
由於已經拜訪過所有與 d 相鄰的節點，我們從queue中取出下一個元素 e， e 沒有節點可以拜訪。
| QUEUE
|
| queue front
| f
|
|
| g
|
| queue back
| |
由於已經拜訪過所有與 e 相鄰的節點，我們從queue中取出下一個元素 f， f 沒有節點可以拜訪。
| QUEUE
|
| queue front
| g
|
| queue back
| |
由於已經拜訪過所有與 f 相鄰的節點，我們從queue中取出下一個元素 g， g 沒有節點可以拜訪。
由於 g 也沒有節點可以拜訪，此時 queue 已經全部清空，breadth-first search完成。
阅读(1359) | 评论(0) | 转发(0) |
