图论
约 1476 字大约 5 分钟
2026-01-23
警告
本模板为了便于理解,包含了大量的详细注释以及规范的 std:: 命名空间前缀。在您将代码复制并提交至相关竞赛或评测平台前,请务必根据个人的编程习惯进行调整,重点建议删除冗余注释并精简代码风格。保留明显的模板特征极易被系统的查重算法或 AIGC 监测机制误标为“人工智能生成内容”,从而对您的评审进度或最终成绩产生不利影响。
邻接矩阵
使用一个二维数组 adj 来存边,其中 adj[u][v] 为 1 表示存在 u 到 v 的边,为 0 表示不存在。如果是带边权的图,可以在 adj[u][v] 中存储 u 到 v 的边的边权。
adjMatrix.cc
#include <bits/stdc++.h>
using namespace std;
int main()
{
// 初始化 n 行 m 列,所有元素为 0
int n = 3, m = 4;
vector<vector<int>> matrix(n, vector<int>(m, 0));
for (int i = 1; i <= m; ++i)
{
int u, v, p;
cin >> u >> v >> p;
matrix[u][v] = p; // 从 u 到 v 权值为 p
}
}邻接表
由于邻接表在附带信息存图中很有用处,所以后面的算法模板都以邻接表为例(虽然副社长 Timothyst 最喜欢的是链式前向星存图)。
假设给定下面的这个图:

下面是具体代码实现过程,使用 class 封装,简单的添加信息在 createGraph() 函数内。如果使用 class 建图,参照 main 函数。
adjTable.cc
#include <bits/stdc++.h>
using namespace std;
// 竞赛用图的简化实现
class Graph
{
private:
int n; // 顶点数
vector<vector<pair<int, int>>> adj; // 邻接表 (to, weight)
vector<bool> directed; // 标记边是否有向
public:
// 构造函数:初始化n个顶点
Graph(int size) : n(size), adj(size), directed(size) {}
// 添加有向边
void addDirectedEdge(int u, int v, int w = 1)
{
adj[u].push_back({v, w});
directed[u] = true;
}
// 添加无向边
void addUndirectedEdge(int u, int v, int w = 1)
{
adj[u].push_back({v, w});
adj[v].push_back({u, w});
directed[u] = false;
directed[v] = false;
}
// 获取邻接表
const vector<vector<pair<int, int>>> &getAdj() const
{
return adj;
}
// 获取顶点数
int getSize() const
{
return n;
}
// 打印图(调试用)
void print()
{
for (int i = 0; i < n; i++)
{
if (!adj[i].empty())
{
cout << i << " -> ";
for (auto [v, w] : adj[i])
{
cout << "(" << v << ", " << w << ") ";
}
cout << endl;
}
}
}
vector<tuple<int, int, int>> sortAdjByWeight()
{
vector<tuple<int, int, int>> vtiii;
for (int i = 0; i < n; i++)
{
for (auto j : adj[i])
{
tuple<int, int, int> tmp(i, j.first, j.second);
vtiii.push_back(tmp);
}
}
sort(vtiii.begin(), vtiii.end(),
[](const tuple<int, int, int> &a, const tuple<int, int, int> &b)
{
return get<2>(a) < get<2>(b);
});
return vtiii;
}
bool operator==(const Graph &b)
{
if (b.getAdj() == adj)
return true;
return false;
}
};
vector<vector<pair<int, int>>> createGraph()
{
// 创建4个顶点的图(对应A=0, B=1, C=2, D=3)
int n = 4;
vector<vector<pair<int, int>>> adj(n);
// 添加边(按照题目图示)
// A(0)-B(1) 无向边,权重1
adj[0].push_back({1, 1});
adj[1].push_back({0, 1});
// A(0)->C(2) 有向边,权重4
adj[0].push_back({2, 4});
// B(1)->D(3) 有向边,权重2
adj[1].push_back({3, 2});
// C(2)->D(3) 有向边,权重3
adj[2].push_back({3, 3});
return adj;
}
int main()
{
Graph g(4); // 4个顶点
g.addUndirectedEdge(0, 1, 1); // A-B 无向
g.addDirectedEdge(0, 2, 4); // A->C 有向
g.addDirectedEdge(1, 3, 2); // B->D 有向
g.addDirectedEdge(2, 3, 3); // C->D 有向
g.print();
}搜索
dfs.cc
void dfs(int u, const vector<vector<pair<int, int>>> &adj, vector<bool> &visited)
{
visited[u] = true;
cout << u << " ";
for (auto [v, w] : adj[u])
{
if (!visited[v])
{
dfs(v, adj, visited);
}
}
}bfs.cc
void bfs(int start, const vector<vector<pair<int, int>>> &adj)
{
int n = adj.size();
vector<bool> visited(n, false);
queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty())
{
int u = q.front();
q.pop();
cout << u << " ";
for (auto [v, w] : adj[u])
{
if (!visited[v])
{
visited[v] = true;
q.push(v);
}
}
}
cout << endl;
}Dijkstra 最短路
采用优先队列最短路,复杂度 O((n+m)logn),但是边权不能为负。
dijkstra.cc
vector<int> dijkstra(int start, const vector<vector<pair<int, int>>> &adj)
{
int n = adj.size();
vector<int> dist(n, INT_MAX);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty())
{
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u])
continue;
for (auto [v, w] : adj[u])
{
if (dist[v] > dist[u] + w)
{
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
return dist;
}SPFA 算法
SPFA 可以用来算带有负权值的最短路,但是不能用于负环最短路,如下图所示,E→A 权值为 −20 如果 A→C→D→E→A 这样循环走,负环上的最短路应当为无穷小。

spfa.cc
vector<int> spfa(int start, const vector<vector<pair<int, int>>> &adj)
{
int n = adj.size();
vector<int> dist(n, INT_MAX);
vector<bool> inQueue(n, false);
vector<int> cnt(n, 0); // 记录入队次数,用于检测负环
dist[start] = 0;
queue<int> q;
q.push(start);
inQueue[start] = true;
cnt[start]++;
while (!q.empty())
{
int u = q.front();
q.pop();
inQueue[u] = false;
for (auto [v, w] : adj[u])
{
if (dist[u] != INT_MAX && dist[v] > dist[u] + w)
{
dist[v] = dist[u] + w;
// 如果v不在队列中,则加入队列
if (!inQueue[v])
{
q.push(v);
inQueue[v] = true;
cnt[v]++;
// 检测负环:如果一个节点入队超过n次,说明存在负环
if (cnt[v] > n)
{
// 存在负环,返回空vector或特殊标记
return vector<int>();
}
}
}
}
}
return dist;
}最小生成树
请先学会并查集与图形建立后再解决这个问题。
最小生成树解决的问题就是选择边使其权和最小的生成树,也就是说要满足 2 点:
- 生成的图是一颗树(不存在环);
- 边权总和最小。

prim.cc
Graph prim(Graph g, int &weight)
{
using tiii = tuple<int, int, int>;
DSU dsu(g.getSize());
auto cmp = [](const tiii &a, const tiii &b)
{
return get<2>(a) > get<2>(b);
};
priority_queue<tiii, vector<tiii>, decltype(cmp)> pq(cmp);
Graph newg(g.getSize());
auto adj = g.getAdj();
// 可以从 1 开始
int cur = 0;
for (auto j : adj[cur])
{
tiii tmp(cur, j.first, j.second);
pq.push(tmp);
}
while (!pq.empty())
{
tiii top = pq.top();
pq.pop();
if (!dsu.same(get<0>(top), get<1>(top)))
{
dsu.merge(get<0>(top), get<1>(top));
newg.addUndirectedEdge(get<0>(top), get<1>(top), get<2>(top));
weight += get<2>(top);
cur = get<1>(top);
for (auto j : adj[cur])
{
tiii tmp(cur, j.first, j.second);
pq.push(tmp);
}
}
}
return newg;
}