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

圖 (Graph)

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

圖的定義與特性

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

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

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

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

圖的表示法

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

邊表 (Edge List)

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

相鄰矩陣 (Adjacency Matrix)

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

相鄰串列 (Adjacency List)

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

參考資料

Graph: Intro(簡介)

演算法筆記: Graph

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

好的今天就先到這邊啦！明天見啦～掰掰！