iT邦幫忙

2021 iThome 鐵人賽

DAY 11
0
Software Development

少女人妻在廚房裡想不通的演算法系列 第 11

【在廚房想30天的演算法】Day 11 資料結構:圖 Graph

Aloha!我是少女人妻 Uerica!終於來到第 11 天了,終於過了三分之一了!真是可喜可賀啊!去年也跟先生過著鐵人賽天天壓線的日子,啊真是一點都不令人懷念啊 XD

圖 (Graph)

圖是一種相鄰關係的資料結構,與樹不同之處在於樹只能有一個父節點往下延伸,而圖則是可以有多個節點互相連結或關聯,日常生活中常見的有人際網絡的表示圖,或捷運路線圖等。

jxku5zp

圖的定義與特性

圖 (Graph) 是由數個頂點 vertex (或稱節點 node ),以及代表點之間連接關係的邊 edge 所組成的有限集合。寫成 G = (V,E)。因點與線的特性,可以替點與線加上權重或有意義的名字、代號。邊線的連接也可分為有方向性或無方向性兩種。

  • 加權圖形 (Weighted Graph): 有數值後可說明連接程度,或車站之間的票價、時間,網路連接時間等。

72rLp64

  • 無向圖: 點與點之間連接的邊線無方向性,表示關係是互通的,例如人際關係圖。

HKLcgCx

  • 有向圖: 點與點之間連接的邊線有方向性,點到點之間若單向箭頭表示只能單向通行,雙向通行則會由兩個反向的單向箭頭表示,例如Instagram 好友、行程圖等。

L9aTW8K

圖的表示法

然而我們在看到圖時,雖然簡單明瞭,但如果儲存在電腦中,要如何表示呢?以下介紹幾種常用的表示法,根據不同的圖形結構有對應的表示方法。

邊表 (Edge List)

邊表是用一維陣列或串列來紀錄所有邊線的關係。雖然這種方式相當簡單、省空間,但卻不適合用於計算,也無法迅速找到一個點碰觸的所有邊。因此大家又發明其他的方式,其中以 Adjacency Matrix 、 Adjacency Lists 最廣為使用。

相鄰矩陣 (Adjacency Matrix)

利用矩陣的方式儲存點以及邊線的方向或權重關係。此方式可以記錄邊線的方向及權重,但無法紀錄點的權重或其他資訊,故若需紀錄此資訊需另建立一個陣列來儲存。

p6b7qWA

相鄰串列 (Adjacency List)

將一張圖上的點依序標示編號。每一個點,後方列出所有相鄰的點。另外,相鄰的點也可以想成是相鄰的邊。

8aSLcuN

參考資料

Graph: Intro(簡介)

演算法筆記: Graph

資料結構的圖形結構(Graphs)


好的今天就先到這邊啦!明天見啦~掰掰!


上一篇
【在廚房想30天的演算法】Day 10 資料結構:樹 Tree
下一篇
【在廚房想30天的演算法】Day 12 資料結構:雜湊表 Hash Table
系列文
少女人妻在廚房裡想不通的演算法30

1 則留言

0
WeiYuan
iT邦新手 4 級 ‧ 2021-09-26 23:25:09

圖片好精美哦,推一個!

感謝鼓勵~~/images/emoticon/emoticon35.gif

WeiYuan iT邦新手 4 級 ‧ 2021-09-29 23:31:28 檢舉

必須推薦!!!

我要留言

立即登入留言