iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 14
2
Software Development

擁抱「資料結構」的「演算法」系列 第 14

擁抱「資料結構」的「演算法」(14) - 圖形 Graph

前言

說到圖形你會想到什麼呢?四邊形、五邊形還是長條圖、圓餅圖?圖形涵蓋的範圍非常的廣,而今天要討論的圖形指的是資料結構的其中一種,就讓我們一起來認識認識吧


生活常識

你有搭乘捷運或火車的經驗嗎?如果到了一個陌生環境,路線圖就會是你的好幫手,可以快速瀏覽目前所在位置目的地之間的關係,而觀察下圖,會發現是由所組成,每個車站都是一個,並且會與相鄰的車站連線,例如,與台北車站相鄰的有:中山、善導室、臺大醫院、西門,這些站點跟台北車站之間都有連線

https://ithelp.ithome.com.tw/upload/images/20200928/20129841qduviMoDjZ.png

另外我們在使用交友軟體時,常常發現朋友之間還有許多共同朋友,而每個人都可以看成一個,有成功建立朋友關係的人,他們之間則會存在連線,這就很像是我們的人脈網路圖
https://ithelp.ithome.com.tw/upload/images/20200928/20129841VWcBEdwVw7.png
圖片來源:freerangestock

最後,生活中常看到的電線桿電線也扮演著重要角色,讓整個城市都佈滿電力,其實也存在著線條的關係
https://ithelp.ithome.com.tw/upload/images/20200928/20129841vqS20g0H2m.png
圖片來源:https://www.pexels.com/zh-tw/photo/3881918/


專業知識 - 圖形 Graph

圖形定義

由上述的生活例子得知,有些圖形是由線條所組成,而資料結構的圖形也是類似的概念,是由頂點(Vertice)邊(Edge)所組成,所以我們會使用 G = (V, E) 來定義一個圖形

G = ( V, E )

  • G : 圖形(Graph)
  • V : 所有頂點(Vertice)的集合
  • E : 所有邊(Edge)的集合

圖形種類

  1. 無向圖(Undirected Graph):
    不具有方向性,例如雙向道,或像是先學畫畫再學書法,也可以學書法再學畫畫都可以,邊以 ( A , B ) 表示
  • V : { A, B, C, D, E }
  • E : { ( A, B ), ( A, C ), ( B, C ), ( B, D ), ( C, D ), ( C, E ), ( D, E ) }
    https://ithelp.ithome.com.tw/upload/images/20200928/201298411xbJSkg4HB.png
  1. 有向圖(Directed Graph):
    具有方向性,例如單向道,或是像一定要讀完小學才能讀國中,邊以 < A , B > 表示
  • V : { A, B, C, D, E }
  • E : { < A, C >, < B, A >, < B, C >, < B, D >, < C, D >, < C, E >, < D, E > }
    https://ithelp.ithome.com.tw/upload/images/20200928/20129841YL40UO6gf3.png

專有名詞

  • 完整圖形(Complete Graph)
    在無向圖中有 5 個頂點,若存在 10 個邊,符合公式:n ( n - 1 ) ÷ 2
    https://ithelp.ithome.com.tw/upload/images/20200928/20129841zfJdBIcPRF.png

 在有向圖中有 5 個頂點,若存在 20 個邊,符合公式:n ( n - 1 )

  • 子圖 (Subgraph)
    假設 乙圖甲圖 的子圖,則乙圖的頂點會包含在甲圖的頂點集合中,且乙圖的邊也會包含在甲圖的邊集合中,
    https://ithelp.ithome.com.tw/upload/images/20200928/201298414ZpFZZaoCI.png

  • 路徑 (Path)
    兩個頂點所經過的邊,稱為路徑,如上面乙圖的 A 到 D ,路徑為 { ( A, E), ( E, D ) }即為一條路徑

  • 路徑長度 (Path Length)
    路徑上總共包含幾條邊,如上面乙圖的 A 到 D ,路徑為 { ( A, E), ( E, D ) },經過2條邊

  • 簡單路徑(Simple Path)
    一條路徑中,起點與終點可以為同一個點,但其他頂點皆為不相同的點,不可重複出現
    例如 A B C D E A 為簡單路徑,其中 A 為終點與起點,所以可以重複
    例如 A B C D B A 不是簡單路徑,其中的 B 出現 2 次

  • 循環 (Cycle)
    起點與終點為同一個頂點的簡單路徑,例如 A B C D E A,其中 A 為終點與起點

  • 相連
    兩個頂點之間,存有路徑可以相通

  • 相連單元(Connected Components)
    Components 有元件的意思,在無向圖中,代表圖形中有不同的元件,而元件指的不是頂點,也不是邊,而是指這個圖形是由多個子圖而組成,子圖與子圖之間不相連,但子圖的內部任一端點都存在路徑可以通往任一端點,如下圖,A、B、C中任一端點都可以存有路徑可到其他端點,而 D 與 E 之間也存有路徑,但左圖的 ABC 與右圖的 DE 之間並不存在路徑,所以下圖是由 2 個相連單元所組成
    https://ithelp.ithome.com.tw/upload/images/20200928/20129841JZjK1VeyBa.png

  • 強相連 (Strongly Connected)
    有向圖中,任意兩頂點彼此之間存在路徑可以互通,如下圖,A 點可以到 B 或 C 點,B 點可以到 A 或 C 點,C 點也可以到 A 或 B 點
    https://ithelp.ithome.com.tw/upload/images/20200928/20129841WUcdkL2jHG.png

  • 強相連單元(Strongly Connected Components)
    有向圖中,任意兩頂點彼此之間不存在路徑,例如 A 可以透過路徑 B C 到 E,但 E 卻沒有路徑可以到 A,則代表下圖不是強相連,且其中包含了強相連單元
    https://ithelp.ithome.com.tw/upload/images/20200928/201298416veSEDSAPx.png
     強相連單元:
    https://ithelp.ithome.com.tw/upload/images/20200928/20129841qgVA1QmEqh.png

  • 分支度(Degree)
    在無向圖中:
    一個頂點含有幾個邊
    在有向圖中:
    入分支度(In-Degree):箭頭指入此端點的個數,如下圖 A 的入分支度為 1
    出分支度(Out-Degree):箭頭由此頂點指出的個數,如下圖 A 的出分支度為 2
    https://ithelp.ithome.com.tw/upload/images/20200928/201298419LhnJvJ8ke.png


今日小結

圖的專有名詞頗多,需要花一點時間理解一下,明天再來講圖形的表示法


今日謎題

在神密的麥田上,被刻畫了好幾個英文字母,並留下了這些訊息,請問你能從中觀察到什麼神秘訊息嗎?

  • V : { W, B, C, D, E }
  • E : { ( W, B ), ( B, D ), ( D, E ), ( E, C ), ( C, W ) }

https://ithelp.ithome.com.tw/upload/images/20200928/20129841eWcZvzsZHL.png

昨日解謎

謎題說明:後序式讀取順序為由左往右,讀取資料的規則為連續 2 個數字與 1 四則運算就開始計算

計算過程

  • 93 100 * 10 14 * + 13 +
    一開始會先讀取到 93 100 \*,電腦就會進行 93 * 100 = 9300 的運算

  • 9300 10 14 * + 13 +
    接著會讀取到 9300 10 14,但不符合連續 2 個數字與 1 四則運算的規則,所以繼續讀到 10 14 \*,電腦就會進行 10 * 14 = 140 的運算

  • 9300 140 + 13 +
    然後繼續由右往左讀取 9300 140 +,電腦就會進行 9400 + 140 = 9540 的運算

  • 9440 13 +
    最後電腦就會進行 9440 + 13 = 9453 的運算

所以小美想聽的就是玖壹壹演唱的 9453,你答對了嗎?


上一篇
擁抱「資料結構」的「演算法」(13) - 二元樹後序走訪
下一篇
擁抱「資料結構」的「演算法」(15) - 圖形表示法
系列文
擁抱「資料結構」的「演算法」30

1 則留言

0
Yanwei Liu
iT邦新手 5 級 ‧ 2021-02-20 13:13:59

無向圖的英文應該是:(Undirected Graph)
有向圖的英文應該是:(Directed Graph)

謝謝分享,文章很棒

小菜 iT邦新手 5 級 ‧ 2021-02-21 07:43:49 檢舉

謝謝你~~~ 已修正^^

我要留言

立即登入留言