18. 基础图论

定义

一个图 $G = (V,E)$ 由点的集合 $V$ 和边的集合 $E$ 组成
平行边 两个节点之间存在多条边界
self-loop 自循环
没有自循环的图称为 simple graph，两端不同的边称为 simple path
connect path: 一个 simple path 存在于任意一对 vertices 之间 (节点间均间接/直接相连)
cycle: 简单路径除了首尾 vertex 相同

稠密度

• complete graph 任意两个 vertex 直接相连
• dense graph 稠密图表示图内的 edge 数量很多 $E\sim V^2$
• sparse graph 稀疏图 $E\sim V$

相邻关系表示

邻接矩阵 adjacency matrix

一个 0-1 矩阵，坐标 i,j 表示边 (i,j) 是否存在于图中
常用于无权图

距离矩阵 distance matrix

在这个距离矩阵中，对应坐标的值表示对应 edge 的距离
一般用 $\infty$ 表示不存在通路

邻接表 adjacency list

点均边拥有量 $\sim E/V$
找到对应 vertex 的 list 用时 $O(1)$ (用 unordered_map)
找到 edge 用时 $O(E/V)$
每个节点平均时间花销 $O(1 + E/V)$
因此对于所有节点都执行一遍，总的时间花销是 $O(V + E)$

c++ 的无穷表示

库

#include <limits>
对应无穷变量 numeric_limits<double>::infinity()

常用算法

假设一个无向有权图 $G = (V,E)$:

从 vertex x 到 vertex y 是否存在直达

case	adjacency matrix	adjacency list
best	O(1)	O(1)
worst	O(1)	O(V)
avg	O(1)	O(1 + E/V)

从 X 出发的最近节点

case	adjacency matrix	adjacency list
best	O(V)	O(1) (只有一个节点)
worst	O(V)	O(V)
avg	O(V)	O(1 + E/V)

判断 edge 是否从某个节点 X 出发

这个问题只需要在 unordered map 中查找对应的 vertex 看是否有从其出发的 edge

case	adjacency matrix	adjacency list
best	O(1)	O(1)
worst	O(V)	O(1)
avg	O(V)	O(1)

图的遍历

DFS

只能作用于 tree 结构即不可存在 cycle 结构