[数据结构#2] 图(1) | 概念 | 邻接矩阵 | 邻接表

图是由顶点集合及顶点间的关系（边）组成的数据结构，可用 $G = (V, E)$ 表示，其中：

顶点集合 $V$ : $V=\{x|x\in\text{某数据对象集}\}$ ，为有限非空集合；
边集合 $E$ : $E=\{(x,y)|x,y\in V\}$ 或 $E=\{\langle x,y\rangle|x,y\in V\}$ ，表示顶点间的关系。

顶点和边：

顶点 $x$ 代表数据元素，第 $i$ 个顶点记作 $v_i$ ；
边 $e_k$ 连接两个顶点，记作 $e_k=(v_i,v_j)$ 或 $\langle v_i,v_j\rangle$ 。

分类：有向图与无向图

有向图：边有方向， $\langle x, y \rangle \neq \langle y, x \rangle$ 。
无向图：边无方向， $(x, y) = (y, x)$ 。

树与图的关系

树是图的一个特殊形式：无环连通图
树的特点：
- 更关注顶点间的结构关系。
- 二叉搜索树、AVL树等属于存储型数据结构。
图的特点：
- 表示顶点间的关系（如权值）。
- 可以用于更广泛的场景，如城市地图、社交网络。

常见应用：

社交网络：
- 无向图：如微信好友关系。
- 有向图：如微博关注关系。

下面的图，顶点可能表示城市，边表示城市之间一个关系（高铁距离、高铁价格、高铁时间。。。）

有了这个东西，提出DFS，BFS遍历，最小生成树（最小代价把图连图），最短路径(一个顶点到其他顶点或者多个顶点之间最短路径)的问题。

完全图

完全图是指任意两个顶点之间都有边相连的图。具体来说：

在有n个顶点的无向图中，若有n * (n-1)/2条边（这实际上是一个等差数列求和的结果），即任意两个顶点之间有且仅有一条边，则称此图为无向完全图。例如，上图中的G1就是一个无向完全图。
在n个顶点的有向图中，若有n * (n-1)条边，意味着任意两个顶点之间存在方向相反的两条边，则称此图为有向完全图。如上图中的G4所示。

邻接顶点

在无向图G中，若(u, v)是E(G)中的一条边，则称u和v互为邻接顶点，并称边(u,v)依附于顶点u和v；
在有向图G中，若<u, v>是E(G)中的一条边，则称顶点u邻接到v，而顶点v邻接自顶点u，并称边<u, v>与顶点u和顶点v相关联。

顶点的度

顶点v的度定义为与它相关联的边的数量，记作deg(v)。对于有向图：

顶点v的入度是以v为终点的有向边的数量，记作indev(v)；
顶点v的出度是以v为起点的有向边的数量，记作outdev(v)。
因此，在有向图中，顶点v的总度等于其入度加出度：dev(v) = indev(v) + outdev(v)。
对于无向图，顶点的度等于该顶点的入度和出度之和，即dev(v) = indev(v) = outdev(v)。
类似于树节点的度：子树的个数

路径

在图G = (V， E)中，从顶点vi出发通过一系列边可以到达顶点vj，则称从vi到vj的顶点序列为一条路径。

路径长度

对于不带权的图，路径长度指的是路径上的边的数量；
对于带权的图，路径长度是指路径上所有边的权值总和。

简单路径与回路

如果路径上的所有顶点v1，v2，v3，…，vm都是唯一的，则这样的路径称为简单路径；
若路径的起始顶点v1和结束顶点vm相同，则这样的路径称为回路或环。

子图

如果一个图G1的所有顶点V1属于另一个图G的顶点集V，且G1的所有边E1也属于G的边集E，则称G1是G的一个子图。

连通图

连通图特指无向图，其中任意一对顶点间都存在至少一条路径。如果一个无向图中的任何一对顶点都可以相互到达，则该图被称为连通图。

强连通图

强连通图是对有向图而言的，指在一个有向图中，对于每一对顶点vi和vj，既存在从vi到vj的路径，也存在从vj到vi的路径。此时称此图为强连通图。

生成树

生成树是一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边

2. 图的存储结构

存储要素

保存顶点信息；
保存顶点间的关系（边）。

//V 顶点类型,  W 权值类型, Direction  表示有向/无向
template<class V,class W,bool Direction>
class Graph
{private:vector<V> _vertexs;//顶点集合map<V, int> _IndexMap;//顶点与下标映射
};

2.1 邻接矩阵

使用二维数组存储顶点关系：

顶点编号后用下标表示，如 $\rightarrow 0, 1, 2, 3$ ；
矩阵值：
- 若无权图：边对应 $1$ 或 $0$ ；
- 若加权图：用权值替代；若无连接，标记为 $\infty$ 。

无权图：

加权图：

特点：

优点：
- 易于判断两顶点是否连通， $O (1)$ ；
- 快速获取边权值。
- 邻接矩阵存储方式非常适合稠密图
缺点：
- 稀疏图存储低效，存在大量 $0$ 。
- 查找一个顶点的所有邻接点需遍历 $O (N)$ 。

假设有n个顶点，是不是要所有顶点遍历一遍才知道某个顶点到底和那些顶点相连。
时间复杂度是O(N)，N是顶点个数。

假设有100个顶点，我这个顶点只和三个顶点相连只有三条边，但也要遍历100次，能不能有个方法快速把与之相连的三条边都找到呢?

2.2 邻接表

将图表示为顶点数组和链表结合的结构：

顶点数组：保存所有顶点；
边链表：存储某顶点的邻接点及边权值。

邻接表和哈希桶类似。使用一个指针数组，把自己和连接的顶点边都挂在下面。

注意：

无向图：同一边在邻接表中存储两次；
有向图：边存储一次，出边表表示出度。

无向图邻接表存储

注意：无向图中同一条边在邻接表中出现了两次。如果想知道顶点vi的度，只需要知道顶点vi边链表集合中结点的数目即可。

有向图邻接表存储

注意：有向图中每条边在邻接表中只出现一次，与顶点vi对应的邻接表所含结点的个数，就是该顶点的出度，也称出度表，要得到vi顶点的入度，必须检测其他所有顶点对应的边链表，看有多少边顶点的dst取值是i。

一般情况下有向图，存储一个出边表即可。

特点：

优点：
- 适合稀疏图；
- 易于查找某顶点的出边；
缺点：
- 判断两顶点是否连通效率低。
  总结一下：邻接矩阵和邻接表其实属于相辅相成，各有优缺点的互补结构。具体还是看场景选择用邻接矩阵和邻接表

图的实现与操作

1. 邻接矩阵实现

概念简介

邻接矩阵是一种用于表示图的数据结构。通过一个二维数组来记录顶点间的边关系，可用于无向图和有向图。每个矩阵元素的值代表了边的权重。

模板设计

template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph {
private:vector<V> _vertexs;        // 顶点集合map<V, int> _IndexMap;     // 顶点到下标的映射vector<vector<W>> _matrix; // 邻接矩阵

V: 顶点类型（如int, char）
W: 权值类型（如int, double）
MAX_W: 默认最大权值（用来表示不存在的边）
Direction: 是否为有向图（默认无向）

图的创建

可以通过以下几种方式创建图：

IO输入（适用于在线评测环境）
文件读取
手动添加边

针对手动添加边的方式：

Graph(const V* a, size_t n) {_vertexs.reserve(n);for (size_t i = 0; i < n; ++i) {_vertexs.push_back(a[i]);_IndexMap[a[i]] = i;}_matrix.resize(n, vector<W>(n, MAX_W));
}

初始化顶点集合与邻接矩阵。
所有边初始权值为MAX_W（表示“无边”）。

边的操作

获取顶点下标

size_t GetVertexindex(const V& v) {auto it = _IndexMap.find(v);if (it != _IndexMap.end()) {return it->second;} else {throw invalid_argument("不存在的顶点");}
}

添加边

void _AddEdge(const size_t& srci, const size_t& dsti, const W& w) {_matrix[srci][dsti] = w;if (!Direction) { // 无向图_matrix[dsti][srci] = w;}
}void AddEdge(const V& src, const V& dst, const W& w) {size_t srci = GetVertexindex(src);size_t dsti = GetVertexindex(dst);_AddEdge(srci, dsti, w);
}

根据图的有向性决定边的存储方向。

打印图

void Print() {// 打印顶点for (size_t i = 0; i < _vertexs.size(); ++i) {cout << "[" << i << "] -> " << _vertexs[i] << endl;}cout << endl;// 打印邻接矩阵for (size_t i = 0; i < _matrix.size(); ++i) {cout << i << " ";for (size_t j = 0; j < _matrix[i].size(); ++j) {if (_matrix[i][j] == MAX_W) {printf("%4c", '*');} else {printf("%4d", _matrix[i][j]);}}cout << endl;}cout << endl;
}

2. 邻接表实现

邻接表是一种用来表示稀疏图的数据结构，使用一个数组结合链表的方式存储。适合存储有大量顶点，但边相对较少的图。

定义边结构

template<class W>
struct Edge {size_t _srci, _dsti; // 起始点和目标点的下标W _w;                // 权值Edge<W>* _next;Edge(const size_t& srci, const size_t& dsti, const W& w) : _srci(srci), _dsti(dsti), _w(w), _next(nullptr) {}
};

图类设计

template<class V, class W, bool Direction = false>
class Graph {typedef Edge<W> Edge;
private:vector<V> _vertexs;        // 顶点集合map<V, int> _IndexMap;     // 顶点到下标映射vector<Edge*> _tables;     // 邻接表

图的创建

Graph(const V* a, size_t n) {_vertexs.reserve(n);for (size_t i = 0; i < n; ++i) {_vertexs.push_back(a[i]);_IndexMap[a[i]] = i;}_tables.resize(n, nullptr);
}

和邻接矩阵一样，初始化顶点集合。

边的操作

添加边

void _AddEdge(const size_t& srci, const size_t& dsti, const W& w) {Edge* edge = new Edge(srci, dsti, w);edge->_next = _tables[srci];_tables[srci] = edge;if (!Direction) { // 无向图Edge* new_edge = new Edge(dsti, srci, w);new_edge->_next = _tables[dsti];_tables[dsti] = new_edge;}
}void AddEdge(const V& src, const V& dst, const W& w) {size_t srci = GetVertexindex(src);size_t dsti = GetVertexindex(dst);_AddEdge(srci, dsti, w);
}

获取顶点下标 跟邻接矩阵相同。

打印图

void Print() {for (size_t i = 0; i < _vertexs.size(); ++i) {cout << "[" << i << "] -> " << _vertexs[i] << endl;}cout << endl;for (size_t i = 0; i < _tables.size(); ++i) {cout << _vertexs[i] << "[" << i << "] ->";Edge* cur = _tables[i];while (cur) {cout << "[" << _vertexs[cur->_dsti] << ":" << cur->_dsti << ":" << cur->_w << "] ->";cur = cur->_next;}cout << "nullptr" << endl;}cout << endl;
}

sum：

邻接矩阵：适合稠密图，快速判断连通性。
邻接表：适合稀疏图，快速找到某顶点的所有出边。