橫向優先搜尋 (breadth-first search)

clipped from nthucad.cs.nthu.edu.tw breadth-first search 是以某一節點為出發點，先拜訪所有相鄰的節點。再依序 拜訪與剛才被拜訪過的節點相鄰但未曾被拜訪過的節點，直到所有相鄰的節點都已被 拜訪過。 因此，進行 breadth-first search 時，需要使用 queue ，以便記錄拜訪的順序。 起始。 假設從 a 開始拜訪，我們將 a 放進queue。 QUEUE queue front a queue back 接下來把 a 從queue中取出，a 有三個節點可以拜訪 (b, c, d)。 QUEUE queue empty 假設我們選擇先拜訪 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。