图的基本概念
图是由顶点集合及顶点间的关系组成的一种数据结构，记作 G = (V, E)。其中 V 是有穷非空集合，代表顶点；E 是顶点间关系的有穷集合，代表边。
(x, y) 表示无向边，Path(x, y) 表示有向边。边上附带的数据信息称为权值。图中的顶点可以理解为现实中的地点或个体，边则是它们之间的联系，权值衡量这种联系的强弱。
有向图和无向图
在有向图中，顶点对 <x, y> 是有序的，<x, y> 和 <y, x> 是两条不同的边。在无向图中，顶点对 (x, y) 是无序的，(x, y) 和 (y, x) 是同一条边。
我们可以用社交关系类比：微信好友是双向的（无向图），而微博关注是单向的（有向图）。
完全图、邻接与度
- 完全图：n 个顶点的无向完全图有 n*(n-1)/2 条边；有向完全图有 n*(n-1) 条边。
- 邻接顶点：若 (u, v) 是边，则 u 和 v 互为邻接顶点。有向图中称 u 邻接到 v。
- 顶点的度：无向图中 deg(v) 为关联边的条数；有向图中 deg(v) = indev(v) + outdev(v)。
路径与连通性
- 路径：从 vi 到 vj 的顶点序列。路径长度是不带权图的边数或带权图的权值和。
- 简单路径与回路：顶点不重复为简单路径；首尾重合为回路。
- 连通图：任意一对顶点都有路径可达。有向图中若每对顶点都互相可达，则为强连通图。
- 生成树：连通图的最小连通子图，含 n 个顶点和 n-1 条边。
图的存储结构
图的存储需要保存节点和边关系。主要有两种经典方式。
邻接矩阵
使用二维数组表示节点关系。0 或 1 表示连通，权值表示距离。若不通则用无穷大代替。
- 优点：O(1) 判断两顶点是否连通，适合稠密图。
- 缺点：空间浪费大，查找某点所有连接边需遍历行/列，复杂度 O(N)。
template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph {
public:
typedef Graph<V, W, MAX_W, Direction> Self;
Graph() = default;
// 初始化顶点
Graph(const V* vertexs, size_t n) {
_vertexs.reserve(n);
for (size_t i = 0; i < n; ++i) {
_vertexs.push_back(vertexs[i]);
_vIndexMap[vertexs[i]] = i;
}
_matrix.(n);
(& e : _matrix) {
e.(n, MAX_W);
}
}
{
ret = _vIndexMap.(v);
(ret != _vIndexMap.()) ret->second;
();
}
_AddEdge( srci, dsti, W& w) {
_matrix[srci][dsti] = w;
(!Direction) _matrix[dsti][srci] = w;
}
{
_AddEdge((src), (dst), w);
}
:
map<V, > _vIndexMap;
vector<V> _vertexs;
vector<vector<W>> _matrix;
};
