9.1   图

非线性数据结构，由顶点（vertex）和边（edge）组成

图G表示为一组顶点V和一组边E的集合

\(𝑉={1,2,3,4,5}\) \(𝐸={(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(4,5)}\) \(𝐺={𝑉,𝐸}\)

想象一下：顶点为节点，边为指针➡链表的拓展

9.1.1   图的常见类型与术语

边的方向：无向图/有向图 无向：双双绑定 有向：相互独立，即使你指我我指你，边不是一个边

顶点是否连通：连通图/非连通图 连通：从某个顶点出发可到其余任意顶点 非联通：从某个顶点出发至少有一个顶点无法到达

有权图：添加“权重”变量

常用术语： - 邻接（adjacency）：当两顶点之间存在边相连时，称这两顶点“邻接”。在上图中，顶点 1 的邻接顶点为顶点 2、3、5。 - 路径（path）：从顶点 A 到顶点 B 经过的边构成的序列被称为从 A 到 B 的“路径”。在上图中，边序列 1-5-2-4 是顶点 1 到顶点 4 的一条路径。 - 度（degree）：一个顶点拥有的边数。对于有向图，入度（in-degree）表示有多少条边指向该顶点，出度（out-degree）表示有多少条边从该顶点指出。

9.1.2   图的表示

“邻接矩阵”和“邻接表”。以下使用无向图进行举例。

1.   邻接矩阵

一个 𝑛×𝑛 大小的矩阵来表示图 用1/0表示两个顶点是否存在边，元素按顺序排成行和列，5个元素就是5 * 5的矩阵。比较的是时候是一个格子比较另一个各自来判断是否存在边

邻接矩阵具有以下特性。

• 顶点不能与自身相连，因此邻接矩阵主对角线元素没有意义。
• 对于无向图，两个方向的边等价，此时邻接矩阵关于主对角线对称。
• 将邻接矩阵的元素从 1 和 0 替换为权重，则可表示有权图。

2.   邻接表

使用 𝑛 个链表来表示图，链表节点表示顶点。 第 𝑖 个链表对应顶点 𝑖 ，其中存储了该顶点的所有邻接顶点（与该顶点相连的顶点）