iT邦幫忙

2

【小馬的資結演算法秘笈】(9) 做拓撲排序(topological sort)的兩種方法- 用queue及DFS

上回【小馬的資結演算法秘笈】(8) 有向圖(directed graph)及DAG(directed acyclic graph)的介紹我們簡介了DAG與拓撲排序(topological sort)的關係,
今天要來實際介紹兩種做topological sort的演算法

複習DAG與topological sort

一、 directed graph
先複習一下directed graph的概念,
我們可以用directed graph表示做事的先後順序,
用邊連接 A->B 表示 A要先做完才可以做B事

譬如說本圖表示要先吃完開胃菜才可以吃湯和主菜,
湯和主菜都吃完了才可以吃甜點,
至於飲料沒有限制,什麼時候吃都可以

https://ithelp.ithome.com.tw/upload/images/20200506/201171145seWRFa8px.png

二、 DAG
沒有環的directed graph就稱為是一個DAG,
即不會有事情互相卡住不能做的情況

三、topological sort
在表示做事先後順序的directed graph中,
找到一種做事的先後順序不違反圖的即為topological sort

  • DAG一定有辦法做topological sort
  • 不是DAG就無法做topological sort

topological sort方法一- 用queue

方法一較為直覺,
要怎麼保證事情一定可以按先後順序做完呢?
最簡單的想法就是,
想找不會被卡住的事情來做」,
譬如說這是一張某資工系的修課擋修表(內容隨意填寫,如有雷同純屬巧合)
https://ithelp.ithome.com.tw/upload/images/20200506/201171149IaBtY9Gmm.png

規定箭頭在前面的課程必須先完成,才可以挑戰後面的課,
要如何決定排出先後順序?
那我就先把沒有任何先修課程的課修掉啊(沒有被箭頭指向的課),
比如說現在「python程式設計一」和「離散數學」這兩門課可以修,
修完了之後,看看圖上還有哪些課是沒有先修課的,
https://ithelp.ithome.com.tw/upload/images/20200506/20117114YX1D9sKiAn.png
依序做下去,一定可以把所有課修完

<演算法>

  1. 一開始計算每個node有幾個點指向它(這個數值我們稱為indegree)
  2. 使用一個queue,持續跑while迴圈,將圖中indegree=0的node(沒有箭頭指向自己的node)加入queue中,
    依序處理,處理node時順便更新指向node的indegree

topological sort方法二- 用DFS

方法二更神奇,
從任何一個點開始做DFS,
記錄每個點的結束時間
一直做到所有點都拜訪過為止,
在topological sort愈前面的順序,它的結束時間也愈晚
(有點懶的寫細節,大家可查詢參考資料)

參考資料

  1. wiki- 拓撲排序
  2. Graph: 利用DFS尋找DAG的Topological Sort(拓撲排序)

尚未有邦友留言

立即登入留言