本文分类：news发布日期：2025/11/1 18:20:48
相关文章
缩点（Tarjan 算法）
缩点（Tarjan 算法）
（有向图）强连通分量缩点
强连通分量缩点后的图称为 SCC。以 \(\mathcal O (N + M)\) 的复杂度完成上述全部操作。性质：缩点后的图拥有拓扑序 \(color_{cnt}, color_{cnt-1},…,1\) ，可以不需再…
建站知识
2025/11/1 18:16:18
平面图最短路（对偶图）
平面图最短路（对偶图）
对于矩阵图，建立对偶图的过程如下（注释部分为建立原图），其中数据的给出顺序依次为：各 \(n(n+1)\) 个数字分别代表从左向右、从上向下、从右向左、从下向上的边。
for (int i = 1; i <=…
建站知识
2025/10/24 12:08:23
多源汇最短路（APSP问题）
多源汇最短路（APSP问题）
使用邻接矩阵存图，可以处理负权边，以 \(\mathcal{O}(N^3)\) 的复杂度计算。注意，这里建立的是单向边，计算双向边需要额外加边。
const int N = 210;
int n, m, d[N][N];void floyd() {fo…
建站知识
2025/10/24 12:08:21
最小生成树（MST问题）
最小生成树（MST问题）
（稀疏图）Prim算法
使用邻接矩阵存图，以 \(\mathcal{O}(N^2+M)\) 的复杂度计算，思想与 \(\tt djikstra\) 基本一致。
const int N = 550, INF = 0x3f3f3f3f;
int n, m, g[N][N];
int d[N], v…
建站知识
2025/10/24 12:08:17
单源最短路径（SSSP问题）
单源最短路径（SSSP问题）
（正权稀疏图）动态数组存图+Djikstra算法
使用优先队列优化，以 \(\mathcal O(M\log N)\) 的复杂度计算。
vector<int> dis(n + 1, 1E18);
auto djikstra = [&](int s = 1) ->…
建站知识
2025/10/24 12:06:01
CNCF项目记录2025-10
毕业项目持续集成与交付：argo、flux
安全与规范：cert-manager、Falco、in-toto、Open Policy Agent、tuf
云原生网络：cilium
流式消息：cloudevents
容器运行时：containerd、cri-o
服务发现：CoreDNS、etcd
云原生…
建站知识
2025/10/24 12:03:36
