申論題

二、圖形（graph）G有 12 個節點（node），分別用數字 0, 1, 2, 3, 6, 7, 8, 9, 12, 13, 14, 15 標 記。標記為a, b的兩個節點間有邊線（edge），若且唯若a =a₁a₂a₃a₄, b =b₁b₂b₃b₄的四位 元二進位表示法恰有一個位元不相同。例如 1 = 0001, 3 = 0011, 9 = 1001, 則標記為 3 的節點與標記為 1 的節點間有邊線，與標記為 9 的節點間沒有邊線。

⑵請在標記小的節點先搜尋的規則下，產生以節點 0 為起始節點的廣度優先搜尋擴 張 樹 （ breadth-first search spanning tree ） 與 深 度 優 先 搜 尋 擴 張 樹 （ depth-first search spanning tree）。（10 分）