iT邦幫忙

2

【小馬的資結演算法秘笈】(8) 有向圖(directed graph)及DAG(directed acyclic graph)的介紹

哈囉~ 大家好,
之前在【小馬的資結演算法秘笈】(6)超好懂的圖(gragh)與樹(tree) 的觀念介紹介紹過什麼是graph,
那什麼是directed graph呢?

其實很簡單,undirected graph的邊是沒有分方向的,
邊所連結的兩個頂點是互通的
譬如說這張地圖(北- 新北、桃- 桃園、竹- 新竹):

https://ithelp.ithome.com.tw/upload/images/20200329/20117114MAhFwuK1Om.png

「新北」與「桃園」相鄰,畫一條線連起來,
「桃園」與「新竹」相鄰,畫一條線連起來,
彼此是可以互通的

但是如果是directed graph,
我們就會把邊標上方向,
代表可以從哪邊走到哪邊,
譬如畫成這樣:
https://ithelp.ithome.com.tw/upload/images/20200506/20117114SExTpEKoVB.png

那麼意思就變成桃園跟新北是可以互通的,
但是只有桃園可以去新竹,新竹不可以去桃園

因為directed graph,是有方向性的,
就很適合用來表示有單行道的地圖,
或是用來表達有先後關係的做事順序,
來看看一些生活上的例子幫助理解吧

一、吃飯順序

你去餐廳吃飯的時候,
餐點可能會按照一定的順序出來,
用頂點 A->B 表示 A要先吃完,B餐點才會出現

譬如說本圖表示要先吃完開胃菜才可以吃湯和主菜,
湯和主菜都吃完了才可以吃甜點

至於飲料沒有限制,什麼時候吃都可以

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

二、修課順序

譬如說在修課的時候,部分課程會要求「先修課程」,
也可以用有向圖表達修課先後關係,
譬如說圖中表示要修「進修英文」之前要先修完「基礎英文一」和「基礎英文二」才可以修,
通識課程則不需要先修課程

https://ithelp.ithome.com.tw/upload/images/20200506/20117114kL2VjiAtfl.png

DAG(directed acyclic graph)

簡單介紹完directed graph,
那什麼是directed acyclic graph呢?
acyclic是沒有環的
如果一個directed graph裡面沒有cycle,
就稱為是一個DAG

cycle簡單來說,就是你可以從一個點出發,
經過一條路徑後又回到原點,
譬如說這張圖你可以從A出發,
走A->B->C->D->A繞一圈回到A,
這張圖就是有cycle的
https://ithelp.ithome.com.tw/upload/images/20200506/2011711485u4YJErQG.png

反之,若把圖改成這樣就沒有cycle
https://ithelp.ithome.com.tw/upload/images/20200506/20117114FYqtB0d7Xf.png

直觀來說,如果用directed graph表示做事順序的話,
DAG可以保證找到一個順序把事情做完,
如果不是DAG就沒辦法做(表示有環,會互相把事情卡住),
舉例來說:

我有很多東西想吃,

  • 吃魚之前要先吃豆花
  • 吃飲料之前要先吃魚
  • 吃水果之前要先吃飲料
  • 吃飲料之前要先吃豆花
    https://ithelp.ithome.com.tw/upload/images/20200506/20117114vOnxUtP1mp.png

這樣的話就沒辦法找到滿足上述條件的吃東西順序

簡單介紹topological sort

topological sort(中文譯作拓撲排序)與DAG習習相關,
既然名字都叫做sort了,
表示是某種排序

topological sort就是找到一種順序,
使得你能夠順利把事情把表示事情先後順序的directed graph做完,
譬如說這張圖是吃飯順序
https://ithelp.ithome.com.tw/upload/images/20200506/201171145seWRFa8px.png

  • 先吃完開胃菜才可以吃湯和主菜,
  • 湯和主菜都吃完了才可以吃甜點
  • 飲料沒有限制,什麼時候吃都可以

那麼「開胃菜」->「湯」->「主菜」->「甜點」->「飲料」是一個合法的拓撲排序,
「開胃菜」->「飲料」 ->「主菜」->「湯」->「甜點」也是一個合法的拓撲排序,
拓撲排序有很多種可能排法,只要不違反先後次序的都可以

如何判斷一張有向圖有沒有cycle呢?

我們可以思考一個問題,給你一個directed graph,
你如何能夠用程式判斷這張圖有沒有cycle呢?
這就留到下一章講如何寫程式做topological sort的時候一併講吧

參考資料

  1. wiki- 拓撲排序

尚未有邦友留言

立即登入留言