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)

好的今天就先到这边啦！明天见啦～掰掰！