45. 下列何者為圖形的拓撲排序(Topological Sorting)功能?
(A) 尋找圖形中的最短路徑
(B) 尋找圖形中的最小生成樹
(C) 尋找圖形中的循環結構
(D) 尋找圖形中的節點順序
答案:登入後查看
統計: A(27), B(10), C(5), D(42), E(0) #3241250
統計: A(27), B(10), C(5), D(42), E(0) #3241250
詳解 (共 2 筆)
#6417843
拓撲排序(Topological Sorting)主要用於有向無環圖(DAG, Directed Acyclic Graph)。它的功能是將圖中的所有頂點排成一個線性序列,使得對於圖中的任何有向邊 (u, v)(從頂點 u 指向頂點 v),頂點 u 在這個序列中都出現在頂點 v 之前。
這個排序代表了一種依賴關係的執行順序,例如課程的先修順序、專案任務的排程、編譯時的依賴關係等。
根據這個定義,我們來看選項:
- (A) 尋找圖形中的最短路徑: 這是戴克斯特拉演算法(Dijkstra's algorithm)或貝爾曼-福特演算法(Bellman-Ford algorithm)等的功能。
- (B) 尋找圖形中的最小生成樹: 這是普林演算法(Prim's algorithm)或克魯斯卡爾演算法(Kruskal's algorithm)的功能,通常用於無向圖。
- (C) 尋找圖形中的循環結構: 雖然拓撲排序的前提是圖中不能有循環(即必須是無環圖),且在執行過程中可以檢測到循環(如果無法完成排序),但其主要功能並非「尋找」循環本身,而是如果沒有循環,就給出一個排序。
- (D) 尋找圖形中的節點順序: 這正是拓撲排序的核心功能。它提供了一個滿足圖中所有有向邊所代表的先後約束的節點線性排序。
因此,最符合的描述是 (D) 尋找圖形中的節點順序。
1
0