存图
邻接表:
// 对于每个点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);
BFS 队列维护
==“最短路”==
DP:无环最短路
所有边权为1——>BFS
void bfs(int root){
queue<int>q;
vis[root]=1;//已被遍历
q.push(root);
while(!q.empty()){
int t=q.front();
q.pop();
//扩展
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(!vis[j])
vis[j]=1,q.push(j);
}
}
}
DFS :递归
空间要求高,思路难想
不具有最短路性
回溯:回复状态
剪枝:判断不合法,断后路
bool st[N]; // 标记是否用过
int h[N], ne[N];
int dfs(int u)
{
if (...) {...; return;} // 输出结果,记得加return语句(或者后边部分用else括起)
st[u] = true; // st[u] 表示点u已经被遍历过
for (int p = h[u]; p != -1; p = ne[p])
{
int v = e[p];
if (!st[v]) dfs(v);
}
st[u] = false; // 恢复现场
}
树和拓扑排序
邻接表模板:
int e[N],ne[N],h[N],w[N],idx;
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void add(int a, int b, int c) // 添加一条边a->b,边权为c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
树的遍历
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);
}
}
queue<int> 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);
}
}
}
拓扑:
读入边的时候同时记录每个点的入度
topsort()函数内,先将所有入度为0的点入队
取出队头元素,将队头元素的临边入度减1,如果为0,就入队。这么做知道队列为空
这样,出队的元素,按照顺序就是拓扑排序的结果,如果出队元素数量小于结点总数,那么拓扑序列不存在。注意,拓扑
序列是不唯一的
int d[N]; // 入度
bool topsort()
{
int hh = 0, tt = -1;
// d[i] 存储点i的入度
for (int i = 1; i <= n; i ++ )
if (!d[i])
q[ ++ tt] = i;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (-- d[j] == 0)
q[ ++ tt] = j;
}
}
// 如果所有点都入队了,说明存在拓扑序列;否则不存在拓扑序列。
return tt == n - 1;
}
有向无环图又称拓扑图
有向无环图一定至少存在一个入度为0的点(反证法 + 抽屉原理证明)
当循环结束后,若队列的长度为n,则拓扑排序存在
在添加边时,可以顺便统计入度
可以使用其它数据结构存储结果(例如线性表,栈等,甚至是集合)
时间复杂度是O(n+m)
为了省事,我们采用模拟队列,因为模拟队列的删除是懒惰删除,所以其实拓扑序列是保存在数组的,最后存在直接输出就好了
最短路
据数据范围判算法,看复杂度
有负权回路不一定存在最短路
抽象建图
找最短的最短路
1. 从起点出发,找最短的路(直达)
2. 找次短路(直达或经1.转)
单源最短路
所有边权都是正数
朴素版dijkstradijkstra : 适用于稠密图 O(n2)
图用邻接矩阵存储
1.将dist[ ]初始化为正无穷,起点的dist设置为0
2.迭代n次,首先找出当前没有确定最短距离点中距离起点最近的点
3.随后,将它纳入集合,用它来更新别的点到起点的最短距离。
int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定
// 求1号点到n号点的最短路,如果不存在则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist); // 0x3f3f3f3f作为距离的“最大值”
dist[1] = 0; // 自己到自己的距离为0
for (int i = 0; i < n - 1; i ++ ) // 执行n-1次(自己到自己的距离已经确定)
{
int t = -1; // 在还未确定最短路的点中,寻找距离最小的点
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
// 用t更新其他点的距离
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if (dist[n] == 0x3f3f3f3f) return -1; // 不可达
return dist[n];
}
堆优化的dijkstra : 适用于稀疏图 O(mlogn)
整体思路与朴素版一样,唯一区别是找最短距离的时候,我们是取得堆顶而不是遍历数组查找
图的存储:邻接表
typedef pair<int, int> PII;
int n; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储所有点到1号点的距离
bool st[N]; // 存储每个点的最短距离是否已确定
// 求1号点到n号点的最短距离,如果不存在,则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> 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算法 O(mn) –边存在负数
边的存储:结构体
我们对每一个边都要进行一次松弛操作,迭代n次代表中间经过不超过n条边的最短路,迭代是有实际意义的
因为这里会更新不可达的点而且边存在负权,所以判断能否到达的条件是大于一个很大的数
int n, m, k; // n表示点数,m表示边数,k是路径的最大边数
int dist[N], backup[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, 0x7f, sizeof dist);
dist[1] = 0;
// 如果第n次迭代仍然会松弛三角不等式(存在更新),就说明存在一条长度是n+1的最短路径,由抽屉原理,路径中至少存在两个相同的点,说明图中存在负权回路。
for (int i = 0; i < k; i ++ ) // 如果没有k,则用n代替k
{
memcpy(backup, dist, sizeof dist); // 备份,防止读后写
for (int j = 0; j < m; j ++ )
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
dist[b] = min(dist[b], dist[a] + w)
}
}
if (dist[n] > 0x7f7f7f7f / 2) return -1;
return dist[n];
}
1.除了可以用邻接矩阵和邻接表外,还可用三元组存储图
2.允许存在负权边,而Dijkstra算法不允许
3.外循环次数决定最小路径的最大边数
4.若第n次迭代有修改,根据容斥原理知道,一定存在负权环(整个环的权重和为负数)
5.实际应用:换乘不超过k次的最短路径(限制路径的边数)
6.backup用于保存上次迭代的结果,避免“写后读”。Dijkstra算法不存在这种情况
7.由于存在负权回路(注意不是负权边),因此负权回路有可能把自定义的无穷大0x7f7f7f7f变小,由于最多修改10000×0000=10810000×10000=108,而0x7f7f7f7f>2×108>2×108,故0x7f7f7f7f / 2依旧是“无穷大”,故可用dist[n] > 0x7f7f7f7f / 2判断是否是无穷大
8.时间复杂度为O(mn)
spfa算法 一般是线性的,最坏O(mn),容易被卡
图的存储:邻接表(要遍历出边)
松弛操作中,只有起点的dist[]
变化才能引起终点distdist变化,所以不会更新不可达的点,最后判断是是否等于0x3f3f3f3f0x3f3f3f3f
起点的dist[ ] 为0, 并将起点入队
取出队头结点(它不在队列里面了),遍历它的临点,如果最短距离更新,并且它还不在队列中(剪枝)就入队
队列为空后,就求出起点到其它个点的最短距离了
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中
// 求1号点到n号点的最短路距离,如果从1号点无法走到n号点则返回-1
int spfa()
{
memset(dist, 0x7f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while (q.size())
{
auto t = q.front();
q.pop();
st[t] = false; // 已出队,因此队列不再包含顶点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] == 0x7f7f7f7f) return -1; // 如果题目保证不存在负权回路(不是指负权边),则可这么写
return dist[n];
注意:
用队列优化更新最短距离的过程,核心思想是
dist[u]发生改变,dist[u] + w才有可能满足< dist[u]
用队列保存最短距离发生改变的顶点(其它数据结构也可以,不一定是队列)
用st记录在队列中的顶点,避免重复更新
由于每次只更新与出队顶点相关的边,因此不会出现“写后读”现象,故改进的bellman-ford算法不需要额外的数组保存上次迭代的结果
SPFA算法有点像堆优化的Dijkstra算法,但后者依赖优先队列,而前者不需要
大多数情况下,Dijkstra算法能解决的问题,SPFA都比它更好,而且适用负权边,因此如果没有限制路径最大边数的情况下,优先考虑SPFA算法,如果过不了就考虑堆优化的Dijkstra算法
平均时间复杂度为O(m),最坏时间复杂度为O(mn)
若要判断负环,则需要额外维护一个数组cnt,用于记录各个最短路径的边数,当边数≥顶点数n时,则一定存在负环
Floyd算法
const int INF = 1E9;
// 初始化:
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i == j) d[i][j] = 0;
else d[i][j] = INF;
// 算法结束后,d[a][b]表示a到b的最短距离
void floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
原理可以想想DP
最短距离需要把d[i][i] = 0;
时间复杂度为O(n3)
最小生成树
稠密图用朴素prim,稀疏图用Kruskal
//prim算法
cosnt int INF = 0x3f3f3f3f;
int n; // n表示点数
int g[N][N]; // 邻接矩阵,存储所有边
int dist[N]; // 存储其他点到当前最小生成树的距离(集合到点u的距离)
bool st[N]; // 存储每个点是否已经在生成树中
// 如果图不连通,则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
memset(dist, 0x3f, sizeof dist);
int res = 0;
for (int i = 0; i < n; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
if (i && dist[t] == INF) return INF; // 非首次遍历时,出现集合到其它点都是无穷大的情况,则图为非连通图
if (i) res += dist[t]; // 第1次迭代得到的dist为无穷大,没意义
st[t] = true;
for (int j = 1; j <= n; j ++ )
if(!st[j]) dist[j] = min(dist[j], g[t][j]); // 可不加if,集合内点的dist应失去意义(受自环影响)
}
return res;
}
图的存储:邻接矩阵
集合:当前构成最小生成树的所有点
我们每次从集合外选出一个距离集合距离最近的点,将它纳入集合(最短距离对应的边就是构成最小生成树的边)并以此点去更新其他集合外的点到集合的最短距离,直到找完当前连通块内的所有点
如果不存在最小生成树,就是(非第一个点)集合外距离集合最近的点到集合距离为正无穷
每次迭代,确定一个点,所以迭代n次
//kruskal算法
int n, m; // n是点数,m是边数
int p[N]; // 并查集的父节点数组
struct Edge // 存储边
{
int a, b, w;
bool operator< (const Edge &W)const // 运算符重载
{
return w < W.w;
}
}edges[M];
int find(int x) // 查询祖宗结点 + 路径压缩
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int kruskal()
{
sort(edges, edges + m);
for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集
int res = 0, cnt = 0;
for (int i = 0; i < m; i ++ )
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if (a != b) // 如果两个连通块不连通,则将这两个连通块合并
{
p[a] = b; // 合并集合
res += w;
cnt ++ ; // 记录边数
}
}
if (cnt < n - 1) return INF; // 边数小于 n - 1,不存在最小生成树
return res;
}
图的存储:结构体,由于要对边排序,需要重载小于号
先对边按边权值排序,从小到大选边,如果这个边的两个点不全在当前生成树的集合,那么就把他们加入到当前生成
树的集合内,对应的边构成最小生成树
由于需要查询集合,所以要使用并查集
二分图的判断:染色法
二分图存在当且仅当不存在奇数环
我们用color[ ]数组记录每一个点它染得颜色,对于任意一个连通块来说,只要其中一个点的颜色确认了,那么其他点
的颜色都可以确认。
我们染色时(遍历),如果该点没被染色,那我们就去染色。如果染色了,就看是不是存在冲突,如果冲突了,染色失败
不存在二分图,反之存在二分图。
因为给的图不一定是一个连通块,所以我们要对每个点都要遍历一遍(遍历过的进行标记,防止二次遍历)
int n; // n表示点数
int h[N], e[M], ne[M], idx; // 邻接表存储图
int color[N]; // 表示每个点的颜色,-1表示未染色,0表示白色,1表示黑色
// 参数:u表示当前节点,c表示当前点的颜色
bool dfs(int u, int c)
{
color[u] = c;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (color[j] == -1)
{
if (!dfs(j, !c)) return false;
}
else if (color[j] == c) return false;
}
return true;
}
bool check()
{
memset(color, -1, sizeof color);
bool flag = true;
for (int i = 1; i <= n; i ++ )
if (color[i] == -1)
if (!dfs(i, 0))
{
flag = false;
break;
}
return flag;
}
匈牙利算法
用于二分图的最大匹配
1. 对于任何一个男孩(对于每一个左半部的点执行findfind操作)
- 依次看看和他相互有好感值的女生(遍历它的临边), 如果在当前这个男生还没有考虑过这个女生(没有判断是否可以配对),
(1) 如果女生还没有找到配对的男生(matchmatch[ ]为0),那么好,他们可以凑成一对
(2) 如果女生找到了配对的男生(match[]不为0)
那么我们看看那个男生可不可以换一个女生配对,给当前这个男生一个机会
如果原来配对的男生可以换一个下家(递归尝试原来配对的男生),那么当前这个女生就和当前的男生进行配对
通过以上步骤,我们就可以让这么多男生女生里面获得最多的人成双成对(也就是达到二分图的最大匹配)
int n1, n2; // n1表示第一个集合中的点数,n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx; // 邻接表存储所有边,匈牙利算法中只会用到从第一个集合指向第二个集合的边,所以这里只用存一个方向的边
int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过
bool find(int x)
{
for (int i = h[x]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true; // 标记已遍历
if (!match[j] || find(match[j])) // j未被匹配,或j已经匹配但其配对对象可选其它的匹配
{
match[j] = x;
return true;
}
}
}
return false;
}
// 求最大匹配数,依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{
memset(st, false, sizeof st);
if (find(i)) res ++ ;
}