这是一篇关于图的存储方式的介绍。

# 概述

图可以分成稠密图和稀疏图。一般边数与点数之间为线性关系为稀疏图，近似为二次关系则为稠密图。此外，根据关系是否是对称的，采用有向图或无向图进行表示。对于路径、圈、树等基本概念，在此不再重复。

在下面的算法表述和复杂度分析中，我们默认采用 $V$ 表示顶点集，采用 $E$ 表示边集，采用 $|V|$ 或 $n$ 表示顶点数，采用 $|E|$ 或 $m$ 表示边数。

# 图的存储

由于图的规模不同，图中顶点和边的关系也不同，于是对于图，我们需要采用不同的方式进行图的存储。

# 关联矩阵

关联矩阵即采用一个大小为 $n \times m$ 的二维数组存储一个图。其中，每一行代表一个顶点，每一列代表一条边，如果某一条边$e_j$ 的端点为某一个顶点 $v_i$, 那么我们将 $(i,j)$ 处的元素为 $1$, 否则为 $0$. 对于有向图，我们一般规定贡献出度的边标 $1$, 贡献入度的边标 $-1$.

关联矩阵的优点在于比较清晰，缺点在于矩阵中的大多数元素被浪费了。且图较稠密时，矩阵更加庞大。

# 邻接矩阵

邻接矩阵是处理较小规模的图时常常采用的存储方法。邻接矩阵的大小为 $n \times n$, 其中若点 $v_i$ 与点 $v_j$ 之间有边相连，那么 $(i,j)$ 处及 $(j,i)$ 处的元素为 $1$, 否则为 $0$. 类似地，对于有向图，我们同样规定贡献出度的边标 $1$, 贡献入度的边标 $-1$.

在此规定下，对一个邻接矩阵 $X$, 若 $X_{i,j}^k=l$, 则说明从 $v_i$ 至 $v_j$ 的长度为 $k$ 的有向路径有 $l$ 条。

如果一个图是加权的，那么我们可以将 $(i,j)$ 处的值改为边 $v_iv_j$ 的权重。这样上述有向路径的结论便不再成立。

// from oi-wiki

#include <iostream>

#include <vector>

using namespace std;

int n, m;

vector<bool> vis; // if this vertex visited 

vector<vector<bool> > adj; // adjacent matrix

bool find_edge(int u, int v) { return adj[u][v]; }

void dfs(int u) {

  if (vis[u]) return;

  vis[u] = true;

  for (int v = 1; v <= n; ++v) {

    if (adj[u][v]) {

      dfs(v);

    }

  }

}

int main() {

  cin >> n >> m;

  vis.resize(n + 1, false);

  adj.resize(n + 1, vector<bool>(n + 1, false));

  for (int i = 1; i <= m; ++i) {

    int u, v;

    cin >> u >> v;

    adj[u][v] = true;

  }

  return 0;

}

# 复杂度

• 查询是否存在某条边：$O(1)$。
• 遍历一个点的所有出边：$O(n)$。
• 遍历整张图：$O(n^2)$。
• 空间复杂度：$O(n^2)$。

应用

邻接矩阵仍然存在空间浪费的问题。如果图较稀疏，那么图中的相当一部分空间都是被浪费的。于是，我们在此基础上优化，得到了邻接表方法。

# 邻接表

邻接表是一个列表数组。首先，我们建立一个长度为$n$ 的数组 a ，其中的每一项是一个链表 List 。链表与图中的顶点一一对应，链表中的每一项存储该顶点可以到达的顶点。因此，采用邻接表存储可以有效解决从一个点进行遍历的问题，同时对于稀疏矩阵更节约空间。但是缺点在于链表的访问速度慢于数组。

下面是 ChatGPT 给出的一个采用邻接表存储含权图的简单例子：

#include <iostream>

#include <vector>

#include <utility> // 使用 std::pair

using namespace std;

class Graph {

private:

    int num_vertices; // 顶点个数

    vector<vector<pair<int, int>>> adj_list; // 邻接表

public:

    // 构造函数

    Graph(int V) {

        num_vertices = V;

        adj_list.resize(V);

    }

    // 添加边

    void add_edge(int u, int v, int w) {

        adj_list[u].push_back(make_pair(v, w)); // 将 (v, w) 添加到 u 的邻接表中

        adj_list[v].push_back(make_pair(u, w)); // 将 (u, w) 添加到 v 的邻接表中（如果是无向图）

    }

    // 打印邻接表

    void print_adj_list() {

        for (int i = 0; i < num_vertices; i++) {

            cout << i << ": ";

            for (int j = 0; j < adj_list[i].size(); j++) {

                cout << "(" << adj_list[i][j].first << ", " << adj_list[i][j].second << ") ";

            }

            cout << endl;

        }

    }

};

int main() {

    Graph G(5); // 创建一个有 5 个顶点的图

    G.add_edge(0, 1, 2);

    G.add_edge(0, 4, 5);

    G.add_edge(1, 2, 3);

    G.add_edge(1, 3, 4);

    G.add_edge(1, 4, 2);

    G.add_edge(2, 3, 1);

    G.add_edge(3, 4, 3);

    G.print_adj_list(); // 打印邻接表

    return 0;

}

在这个实例中，存储图的结构是 vector<vector<pair<int, int>> . 这个结构存储图的效率可能会很低。如果想要提高效率，可以将最外围的 vector 更改为一个定长的数组。

或者看看 oi-wiki 给出的：

#include <iostream>

#include <vector>

using namespace std;

int n, m;

vector<bool> vis;

vector<vector<int> > adj;

bool find_edge(int u, int v) {

  for (int i = 0; i < adj[u].size(); ++i) {

    if (adj[u][i] == v) {

      return true;

    }

  }

  return false;

}

void dfs(int u) {

  if (vis[u]) return;

  vis[u] = true;

  for (int i = 0; i < adj[u].size(); ++i) dfs(adj[u][i]);

}

int main() {

  cin >> n >> m;

  vis.resize(n + 1, false);

  adj.resize(n + 1);

  for (int i = 1; i <= m; ++i) {

    int u, v;

    cin >> u >> v;

    adj[u].push_back(v);

  }

  return 0;

}

# 复杂度

• 查询是否存在 $u$ 到 $v$ 的边：$O(d^+(u))$. 如果事先进行了排序就可以使用二分查找做到 $O(\log(d^+(u)))$.
• 遍历点 $u$ 的所有出边：$O(d^+(u))$.
• 遍历整张图：$O(n+m)$.
• 空间复杂度：$O(m)$.

# 十字链表

对于稀疏图$G$, 我们可以采用十字链表存储其邻接矩阵。十字链表是一种特殊的数据结构，每一个节点含有两个指针域，分别指向同行和同列的下一个节点。这样，对于稀疏矩阵，我们在节约空间的情况下，以$O(d(v))$ 复杂度访问一个节点指向和被指向的全部节点，这是较快的。

# 链式前向星

// from oi-wiki

#include <iostream>

#include <vector>

using namespace std;

int n, m;

vector<bool> vis;

vector<int> head, nxt, to;

void add(int u, int v) {

  nxt.push_back(head[u]);

  head[u] = to.size();

  to.push_back(v);

}

bool find_edge(int u, int v) {

  for (int i = head[u]; ~i; i = nxt[i]) {  // ~i 表示 i != -1

    if (to[i] == v) {

      return true;

    }

  }

  return false;

}

void dfs(int u) {

  if (vis[u]) return;

  vis[u] = true;

  for (int i = head[u]; ~i; i = nxt[i]) dfs(to[i]);

}

int main() {

  cin >> n >> m;

  vis.resize(n + 1, false);

  head.resize(n + 1, -1);

  for (int i = 1; i <= m; ++i) {

    int u, v;

    cin >> u >> v;

    add(u, v);

  }

  return 0;

}

# 复杂度

• 查询是否存在 $u$ 到 $v$ 的边：$O(d^+(u))$.
• 遍历点 $u$ 的所有出边：$O(d^+(u))$.
• 遍历整张图：$O(n+m)$.
• 空间复杂度：$O(m)$.

# 连通性问题

# 并查集算法

对于无向图，可以采用并查集进行判断。但并查集的缺点在于不能将两个合并的集合分离，即不能处理删除边的情况。于是只能用在不断添加边的过程中。

在连通性的判断中，一般需要查找的次数不多，于是并查集的时间复杂度大约为 $O(m\log n)$ 级别。

关于并查集的具体实现，我已经放到单独一篇博文中进行记录。

澹台千儿的并查集笔记

# Kosaraju 算法

# Tarjan 算法

# 最短路径问题

最短路径问题即在图$G$ 中，寻找

# Dijkstra 算法

Dijkstra 算法过程：

复杂度：$m\log n$. $m$ 为边数，$n$ 为顶点数。

# A * 算法

A * 算法：在寻解过程相当有用。

edge list
->
adjacency list (邻接表)

顶点的定义：

vector <Vertex> pool;

边的定义：

map <int, set<int>>;

查找权重时，用

map<pair<*,*>, double>;

此时没有对边进行编号，采用两端点标记边。如果图比较稳定 (不会发生大的变化，则可以编号)。

拉普拉斯矩阵：
$0$ 的特征根重数就是图的连通分支数

可以用十字链表存储稀疏矩阵

并查集的弱点在于，不能处理集合的划分问题，例如图的缩减等。

# 弗洛伊德算法

# Bellman-Ford 算法

# 欧拉图问题

# Fleury 算法

# 最大流问题

在有向图中，每个边$e_{ij}$ 权非负，边权$c_{ij}$ 称为容量即额定最大流量。我们需为每个边$e_{ij}$ 另赋一个权$f(e_{ij})$, 称为边的流量，其中流量$f(e_{ij})$ 应小于容量$c_{ij}$.

网络图中的顶点分为三类， S 称为源， V 称为汇，各仅有一个。其余节点没有存储能力，即流入边权和等于流出边权和，可以表示为$\sum_{e.in.v}f(e) = \sum_{e.out.v}f(e)$.

我们称一个图的总流量为流出源点 (或流入汇点) 的所有流量之和，即$\sum_{e.out.s}f(e) = \sum_{e.in.v}f(e)$.

我们所希望寻找的是从源流出的流量最大的流 (或流入汇的流量最大的流)，称为最大流问题。

# Ford-Fulkerson 方法

Ford-Fulkerson 方法即标号方法，又称增广路方法，是 20 世纪 50 年代福特 (Ford) 和福克逊 (Fulkerson) 提出的方法。之所以称之为方法而不是算法，是因为其仅给出了最基本的想法，但是无法确定最终找到的方式。实际上，下面几种最大流算法几乎都是基于此方法的。

首先，我们引入算法中的一些基本概念。

# 可行路径与增广路径

对一个网络流$G$, 我们对一条从源点 S 到汇点 T 的路径赋流量$f$, 路径上每条边$e_{ij}$ 都满足$f<c_{ij}$, 那么我们称这个路径为一个可行路径。

# 残量网络 (residual network)

该算法的想法是，从某个可行流开始，构建一个残差网络，在网络中寻找可能的增广路径，然后将可能的增广路径添加到原可行流中。当无法找到增广路径时，就得到了最大流。

# 最大流最小割定理

# EK 算法

EK 算法全称 Edmond-Karp 算法，即最短增广路算法，是在 Ford-Fulkerson 算法中，每次沿残量网络的最短增广路进行增广的算法。其复杂度为$O(nm^2)$.

# ISAP 算法

ISAP 算法全称 Improved Shortest Augmenting Path 算法，即改进的最短增广路算法。

# Dinic 算法

算法复杂度为$O(n^2m)$. 在二分匹配中，可以达到$O(m\sqrt{n})$.

算法步骤：

1. BFS 分层
2. DFS 增广
3. 重复 1.2.

# SPFA 算法

# 最小费用最大流问题