iT邦幫忙

1

【小馬的資結演算法秘笈】(6)超好懂的圖(gragh)與樹(tree) 的觀念介紹

今天要繼續介紹兩種常見的資料結構- 圖(gragh)與樹(tree)
什麼是一個圖呢?
這邊給個定義:

Graph定義

graph是由一些頂點和一些邊所構成,
任意兩個頂點之間可以有邊相連或沒有
譬如說底下就是一張有四個頂點的graph:

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

那麼graph有什麼用呢?
直接看一些生活上的例子應該會比較容易理解

一、表示地圖

譬如說這張是我隨意在網路上找的台灣地圖:

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

我們可以把每個縣市想成是一個頂點,
如果在地圖上縣市有土地直接相鄰,
那麼兩個頂點之間就有邊相鄰,否則沒有

為了避免等一下圖畫的眼花瞭亂,
以「新北」、「桃園」、「新竹」、「金門」四個縣市做示範:

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

譬如說「新北」與「桃園」相鄰,畫一條線連起來,
「桃園」與「新竹」相鄰,畫一條線連起來,
「金門」不與任何縣市相鄰,所以不與其它頂點相連

其它例子還有日常生活會看到的「台北捷運圖」啦,
頂點是車站名,邊表示車站之間是否相鄰

二、朋友關係圖

譬如說我們可以把每個人想成是頂點,
如果兩個人之間互相認識,中間就連線
比如說:

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

我們可以用這張圖表示A, B, C, D, E, F在同一個班級裡上課,
其中A, B互相認識,
C, D, E互相認識,
F是邊緣人與其它人都不認識

所以其實graph是很生活化的東西,
讀者們也可以想想日常生活中有沒有什麼情況也是graph呢?

tree定義

講完了graph,那什麼是一個tree呢?
tree是一種特別的graph,
滿足兩個條件:

  • 是一個連通圖(connected graph)
  • 沒有循環(cycle)

名詞解釋: 連通圖(connected graph)

連通圖很簡單,就是任兩個頂點都可以找到一條路徑把它連起來,
比如說台灣本島地圖(為了方便,只取「新北」、「桃園」、「新竹」三個縣市來畫)

https://ithelp.ithome.com.tw/upload/images/20200329/201171142SM3XEoGv0.png

儘管「新北」、「新竹」這兩個縣市沒有邊直接連接,
但是要從「新北」到「新竹」,可以走「新北->桃園->新竹」的路徑,
所以這張圖是連通的,
反之,若是加上離島(比如: 金門)的話圖就是不連通的,
因為金門沒有路徑到達其它的縣市

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

名詞解釋: 循環(cycle)

cycle就是頂點之間的連接形成了一個圈,比如:

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

了解基礎名詞解釋後,
我們來看看為什麼tree要滿足這兩個條件:

  • 是一個連通圖(connected graph)
  • 沒有循環(cycle)

這邊你可以將樹與現實中的樹聯想在一起,
https://ithelp.ithome.com.tw/upload/images/20200329/20117114aZXDHjujYx.png

因為樹由根開始生長,所以一定是連通的,
不可能隔空生長出葉子,
沒有循環(cycle)像是保證生長的順序,
一定是從「根->樹幹->樹枝->葉子」這樣生長,
葉子不會長出根

你看若是我將樹的分岔點都想成是頂點,
是不是就很像一開始介紹的一種graph呢?

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

有根樹 (rooted tree)

在資料結構中討論的有根樹
有個特別的頂點叫做
可能為了表示由上往下生長(如父親、兒子的關係),
的位置是放在最上面的,
與現實中的樹相反

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

名詞解釋: parent, chlidren

而節點之間的關係,也可以用parent, chlidren來互稱,
比如說這樣子的一棵樹:

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

那麼我們稱B是A的chlid,A是B的parent,
E是B的chlid,B是E的chlid

講到這裡,你是不是覺得跟公民課本上會看到的某張圖有點相似呢?
沒錯,就是家族樹

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

普通的家族樹滿足tree的定義,因為它

  • 是一個連通圖(connected graph)
  • 沒有循環(cycle)

但是在資料結構若是討論**有根樹 (rooted tree)**有更進一步的定義:

  • 除了root以外,每個頂點都恰好有一個parent
  • 每個頂點可以有多個chlidren
  • 沒有chlidren的頂點稱為leaf(葉子)

因此像家族樹中爸爸和媽媽生出你並不滿足**有根樹 (rooted tree)**的定義,
**有根樹 (rooted tree)**與生活中對應的樹,
比較像是「只記錄男性的家族族譜」,如圖:

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

對於graph跟tree的介紹就先到這邊,
今天暫沒有程式碼的實作,
希望融入日常生活的東西可以讓大家更了解概念


尚未有邦友留言

立即登入留言