題組內容

五、拓樸排序(topological sorting)是一個在沒有迴圈的有向性圖形(directed graph)找 出節點順序(Linear order)。例如,如果有一條有向連結從節點 u 指向節點 v,則 我們說 u v 的順序為 u 在 v 的前面。拓樸排序的演算法如下: 

⑵如果有向性圖 G=(V, E),節點集合的大小為 N,請問此演算法的時間複雜度 (time complexity)Big-O 為何?(請說明如何得到答案)(10 分)