图论
树和图的存储
`
- 树是特殊的图, 无环的联通图
- 图分为有向图和无向图, 无向图是一种特殊的有向图
`
邻接矩阵
存稠密图, 空间复杂度 \(O(n ^ 2)\)
g[u][v] = w;
邻接表
void init() {
for (int i = 0; i < N; i++)
h[i] = -1;
}
void add(int a, int b) { // 在链表头插入 b
e[idx] = b, nt[idx] = h[a], h[a] = idx, idx++;
}
树和图的遍历
深度优先遍历
void dfs(int u) {
vis[u] = 1; // 标记被搜过了
for (int i = h[u]; i != -1; i = nxt[i]) { // 遍历出边
int j = e[i];
if(!vis[j]) dfs(j);
}
}
宽度优先遍历
void init() {
for (int i = 1; i <= N; i++)
h[i] = -1;
}
void init_() {
for (int i = 1; i <= N; i++)
vis[i] = -1;
}
void add(int a, int b) {
e[idx] = b, nxt[idx] = h[a], h[a] = idx, idx++;
}
int bfs() {
init_();
queue <int> q;
vis[1] = 0; q.push(1);
while (q.size()) {
int t = q.front(); q.pop();
for (int i = h[t]; i != -1; i = nxt[i]) {
int j = e[i];
if (vis[j] == -1) {
vis[j] = vis[t] + 1;
q.push(j);
}
}
}
return vis[n];
}
拓扑排序
适用于 \(DAG\), 一个 \(DAG\) 至少存在一个入度为 \(0\) 的点, 拓扑序不唯一
/*
把所有入度为 0 的点入队
每次循环取队头 t, 枚举 t 的出边 t -> j
删掉 t -> j, j 的入度--, d[j]--
如果 j 的入度为 0, 将 j 入队
*/
bool topo() {
for (int i = 1; i <= n; i++) {
if (!d[i]) q.push(i);
}
while (q.size()) {
int t = q.front(); q.pop();
qp[++cnt] = t;
for (int i = h[t]; i != -1; i = nxt[i]) {
int j = e[i]; d[j]--;
if (d[j] == 0) q.push(j);
}
}
return cnt == n;
}
最短路
源点 : 起点
汇点 : 终点
Dijkstra
计算从一个点到其他所有点的最短路,
单源最短路径算法, 不能处理存在负边权的情况,
朴素 : 稠密图, 堆优化 : 稀疏图,
\(O(n^2)\)
/*
1. 初始化距离 : dis[1] = 0, dis[i] = inf;
2. 循环, 找到未确定最短距离的最近的点 t, 将 t 压进集合里, 用 t 更新其他点的距离 : dis[i] > dis[t] + w ? dis[t] + w : dis[i];
*/
void init() {
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
e[i][j] = inf;
for (int i = 1; i <= N; i++)
dis[i] = inf;
dis[1] = 0;
}
void dij() {
for (int i = 1; i <= n; i++) {
int t = -1;
for (int j = 1; j <= n; j++)
if (!vis[j] && (t == -1 || dis[t] > dis[j]))
t = j; // 更新未确定最短路的最近的点
vis[t] = 1;
if (t == n) break;
for (int j = 1; j <= n; j++)
dis[j] = min(dis[j], dis[t] + e[t][j]);
}
}
堆优化-Dijkstra
\(O(mlogn)\)
void init() {
for (int i = 0; i <= N; i++)
h[i] = -1;
for (int i = 0; i <= N; i++)
dis[i] = inf;
}
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, nxt[idx] = h[a], h[a] = idx, idx++;
}
void dij() {
dis[1] = 0;
q.push({0, 1});
while (q.size()) {
int ver = q.top().second, diss = q.top().first; q.pop();
if (vis[ver]) continue;
vis[ver] = 1;
for (int i = h[ver]; i != -1; i = nxt[i]) {
int j = e[i];
if (dis[j] > dis[ver] + w[i]) {
dis[j] = dis[ver] + w[i];
q.push({dis[j], j});
}
}
}
}
Bellman-Ford
单源最短路, 可以处理存在负边权的情况, 不能处理负环, 可以判断负环,
有边数限制时用 \(Bellman-Ford\),
\(O(nm)\)
/*
1. 循环 n 次
2. 遍历所有边 a -> b, 权值为 w : dis[b] = min(dis[b], dis[a] + w); (松弛操作)
3. dis[b] <= dis[a] + w (三角不等式)
*/
void init() {
for (int i = 1; i <= N; i++)
dis[i] = inf;
}
void bellman_ford() {
dis[1] = 0;
for (int i = 1; i <= k; i++) {
memcpy(backup, dis, sizeof(dis)); // 备份上一次迭代结果
for (int j = 1; j <= m; j++) {
int u = e[j].u, v = e[j].v, w = e[j].w;
dis[v] = min(dis[v], backup[u] + w); // 用上一次迭代结果更新距离
}
}
}
Spfa
单源最短路, 可以处理存在负边权的情况, 不能处理负环,
一般 \(O(m)\), 最坏 \(O(nm)\)
/*
1. 取出队头 t
2. 更新 t 的所有出边
*/
void init() {
for (int i = 1; i <= N; i++)
h[i] = -1;
for (int i = 1; i <= N; i++)
dis[i] = inf;
}
void add(int u, int v, int w) {
e[idx] = v, w[idx] = w, nxt[idx] = h[u], h[u] = idx, idx++;
}
void spfa() {
dis[1] = 0;
q.push(1); vis[1] = 1;
while (q.size()) {
int t = q.front(); q.pop();
vis[t] = 0;
for (int i = h[t]; i != -1; i = nxt[i]) {
int j = e[i];
if (dis[j] > dis[t] +w[i]) {
dis[j] = dis[t] + w[i];
if (!vis[j]) {
q.push(j); vis[j] = 1;
}
}
}
}
}
Spfa 判负环
bool spfa() {
for (int i = 1; i <= n; i++)
vis[i] = 1, q.push(i);
while (q.size()) {
int t = q.front(); q.pop();
vis[t] = 0;
for (int i = h[t]; i != -1; i = nxt[i]) {
int j = e[i];
if (dis[j] > dis[t] + w[i]) {
dis[j] = dis[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n)
return true;
if (!vis[j])
q.push(j), vis[j] = true;
}
}
}
return false;
}
Floyed
可求出任意两点间的最短路径,
适用于出现多源汇最短路的情况, 可以处理负边权
\(O(n^3)\)
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);