試題詳解

5. 一個無向圖(undirected graph)共有 6 個頂點(vertices)，分別為 A，B，C，D，E，F，頂
點彼此間的連接關係以鄰近矩陣(adjacency matric)表示如下(0 表示不相連，1 表示有相連)：

請以「廣度優先搜尋(Breath First Search，BFS)」方式，從 A 開始拜訪，並假設一旦需要將多個相鄰頂點加入佇列(queue)時，會依照頂點英文字母排序(由前到後)的規則將其排入佇列。請問最終 BFS 的拜訪次序為何？
(A)A → B → C → D → E → F
(B)A → B → D → C → E → F
(C)A → C → B → D → F → E
(D)A → C → B → E → D → F
A B C D E F
A 0 1 1 0 0 0
B 1 0 0 1 1 0
C 1 0 0 0 1 1
D 0 1 0 0 1 0
E 0 1 1 1 0 1
F 0 0 1 0 1 0