題組內容

三、圖形的追蹤(Graph Traversal)可分為深度優先搜尋法與廣度優先搜尋法：

(一)請說明深度優先搜尋法(Depth First Search, DFS)及廣度優先搜尋法(Breadth First Search, BFS)。（10 分）。

詳解 (共 2 筆)

詳解 提供者：佘坤穎 QQ
深度優先搜尋法，是一種用來遍尋一個樹(tree)或圖(graph)的演算法。由樹的根(或圖的某一點當成 根)來開始探尋，先探尋邊(edge)上未搜尋的一節點(vertex or node)，並儘可能深的搜索，直到該節點的所有邊上節點都已探尋；就回溯(backtracking)到前一個節點，重覆探尋未搜尋的節點，直到找到目 的節點或遍尋全部節點。 1>11>10>9>2>5>4>8>12>3>6>7 廣度優先搜尋法，是一種圖形(graph)搜索演算法。 從圖的某一節點(vertex, node)開始走訪，接著走訪此一節點所有相鄰且未拜訪過的節點，由走訪過的節點繼續進行先廣後深的搜尋。 以樹(tree)來說即把同一深度(level)的節點走訪完，再繼續向下一個深度搜尋，直到找到目的節點或遍尋全部節點 1>2>8>11>9>10>5>12>3>4>6>7
詳解 提供者：Show-ping Wang

不好意思，這題廣度優先搜尋(BFS)的部分，樓上給的答案中後段的部分好像都怪怪的，因為依照廣度優先搜尋(BFS)「先進先出」的原則， 第二層(...|  2 8 9 11  |... ) 2出去5進來，8出去3,12進來，9出去10進來，整體排序應該是 1 |  2 8 9 11  | 5 3 12 10 | 4 6 | 7，不是嗎?                                                                                                                           --> 佐證網址