1333 字
7 分钟
图有关算法
这里搬运acwing的模板，感觉还不错~
树与图的存储 树是一种特殊的图，与图的存储方式相同。 对于无向图中的边ab，存储两条有向边a->b, b->a。 因此我们可以只考虑有向图的存储。
(1) 邻接矩阵：g[ a ] [ b ]存储边a->b
(2) 邻接表：
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;// 添加一条边a->b
void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;}// 初始化
idx = 0;memset(h, -1, sizeof h);树与图的遍历 时间复杂度 O(n+m)O(n+m), nn 表示点数，mm 表示边数 (1) 深度优先遍历 —— 模板题 AcWing 846. 树的重心
int dfs(int u){ st[u] = true; // st[u] 表示点u已经被遍历过
for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) dfs(j); }
}(2) 宽度优先遍历 —— 模板题 AcWing 847. 图中点的层次
queue q;st[1] = true; // 表示1号点已经被遍历过q.push(1);
while (q.size()){ int t = q.front(); q.pop();
for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { st[j] = true; // 表示点j已经被遍历过 q.push(j); } }
}拓扑排序 —— 模板题 AcWing 848. 有向图的拓扑序列 时间复杂度 O(n+m)O(n+m), nn 表示点数，mm 表示边数
bool topsort(){ int hh = 0, tt = -1;
// d[i] 存储点i的入度 for (int i = 1; i dist[j])) t = j;
// 用t更新其他点的距离 for (int j = 1; j PII;
int n; // 点的数量int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边int dist[N]; // 存储所有点到1号点的距离bool st[N]; // 存储每个点的最短距离是否已确定int dijkstra(){ memset(dist, 0x3f, sizeof dist); dist[1] = 0; priority_queue, greater> heap; heap.push({0, 1}); // first存储距离，second存储节点编号
while (heap.size()) { auto t = heap.top(); heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue; st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > distance + w[i]) { dist[j] = distance + w[i]; heap.push({dist[j], j}); } } }
if (dist[n] == 0x3f3f3f3f) return -1; return dist[n];
}Bellman-Ford算法 —— 模板题 AcWing 853. 有边数限制的最短路 时间复杂度 O(nm)O(nm), nn 表示点数，mm 表示边数 注意在模板题中需要对下面的模板稍作修改，加上备份数组，详情见模板题。
int n, m; // n表示点数，m表示边数int dist[N]; // dist[x]存储1到x的最短路距离
struct Edge // 边，a表示出点，b表示入点，w表示边的权重{ int a, b, w;}edges[M];// 求1到n的最短路距离，如果无法从1走到n，则返回-1。int bellman_ford(){ memset(dist, 0x3f, sizeof dist); dist[1] = 0;
// 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。 for (int i = 0; i dist[a] + w) dist[b] = dist[a] + w; } }
if (dist[n] > 0x3f3f3f3f / 2) return -1; return dist[n];
}spfa 算法（队列优化的Bellman-Ford算法） —— 模板题 AcWing 851. spfa求最短路 时间复杂度 平均情况下 O(m)O(m)，最坏情况下 O(nm)O(nm), nn 表示点数，mm 表示边数
int n; // 总点数int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边int dist[N]; // 存储每个点到1号点的最短距离bool st[N]; // 存储每个点是否在队列中// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1int spfa(){ memset(dist, 0x3f, sizeof dist); dist[1] = 0;
queue q; q.push(1); st[1] = true;
while (q.size()) { auto t = q.front(); q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; if (!st[j]) // 如果队列中已存在j，则不需要将j重复插入 { q.push(j); st[j] = true; } } } }
if (dist[n] == 0x3f3f3f3f) return -1; return dist[n];
}spfa判断图中是否存在负环 —— 模板题 AcWing 852. spfa判断负环 时间复杂度是 O(nm)O(nm), nn 表示点数，mm 表示边数
int n; // 总点数int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数bool st[N]; // 存储每个点是否在队列中// 如果存在负环，则返回true，否则返回false。bool spfa(){ // 不需要初始化dist数组 // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。
queue q; for (int i = 1; i dist[t] + w[i]) { dist[j] = dist[t] + w[i]; cnt[j] = cnt[t] + 1; if (cnt[j] >= n) return true; // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环 if (!st[j]) { q.push(j); st[j] = true; } } } }
return false;
}floyd算法 —— 模板题 AcWing 854. Floyd求最短路 时间复杂度是 O(n3)O(n3), nn 表示点数 初始化：
for (int i = 1; i dist[j])) t = j;
if (i && dist[t] == INF) return INF;
if (i) res += dist[t]; st[t] = true;
for (int j = 1; j