文章来源: http://thunderfyc.wordpress.com.cn
图
多个节点和多个节点之间的关系
无向图 边可以双向行走
有向图 边只能单向行走
边集数组 存储边的数组
邻接矩阵 g[i][j]表示i和j之间连边
邻接表 g[i][j]表示i的第j个邻居
DFS
从一个节点开始 沿着一条路径走 走不通退回 然后走另外一条
BFS
从一个节点开始 访问每一个后继 然后再每个后继继续访问 用队列
Euler
所有点的出度等于入度才存在 任意一个点 找后继插入 走一条边删一条边
直到回到这个点 这条路径记录下来 继续重复 直到没有边为止
拓扑排序
有向图中 到达某个点 先要到达所有前驱 求访问顺序
DFS的时候 从某个点的递归层中 记录离开递归层的顺序 将顺序逆向输出
强连同分量
有向图中 任意两个点都能连通的子图
先DFS 记录下离开递归层的顺序 然后边全部反向 从最后一个开始 依次DFS 所得到的每一棵DFS树都是一个强连同分量
关节点/割顶
去掉之后 图就不连同的节点
DFS之后 如果根有2个以上的孩子 那么根是关节点
记录和当前节点相连的被访问到的节点中 非自己父亲 的深度最小的 记录下来 如果和当前节点相连的一个节点没有被访问过 进行访问 访问完后
如果和孩子相连的祖先深度不比他小 这个节点就是关节点
桥
去掉后 图就不连同的边
同求关节点 如果相连的祖先深度比父亲要大 这条边为桥
最小生成树 将所有点连接起来的无根树 边为图的边 边权和最小
Kruskal 每次找不在同一个集合的两个节点 连边最小 用并查集实现
Prim 在没有被连接到的节点里找到一个和已经被连接的节点边权最小的 加入 用堆实现
次小生成树
Prim同时记录max[u][v]表示从u到v路径中最大的边权 枚举不在MST中的g[u][v]必然大于max[u][v]替换之 找到g[u][v]-max[u][v]最小的即可
Kruskal后枚举MST中的边 去掉后重新求MST 找其中最小的一个
最短路
单源最短路径
Bellman-ford
不停的选择d[i]+g[i][j]<d[j]是否可行 作n次迭代 可判断是否存在负环
Dijkstra
每次找到某个点最近的点d[i] 然后做修改d[i]+g[i][j]<d[j]
任意点对最短路径
Floyd
本质是矩阵乘法 Mi是经过长度为i的最短路径 Mi*M0 = M(i+1) 其中的操作i j k为Mi[i][k]+M0[k][j] < Mi+1[i][j]就更改
差分约束系统
满足若干大小关系xi-xj<=bk
建图 T到所有点射出权为0的边 如果xi-xj<=bk则j到i射出bk 最后0到其他节点的最短距离为一组解
0到i的距离要小于等于到j的距离加上边的权值 显然是最短路
文章来源: http://thunderfyc.wordpress.com.cn
==============================================================================
DFS
p = 1;
DFS(k, dad, dep:int)
{
Ck = Grey; Dk = dep;
//Ak = dep; tot = 0;
for i <- 1 to n
{
// if (g[i][k] and i <> dad and Ci = Grey)
// Ak = min{Ak, Di}
if (g[i][k] and Ci = White)
{
DFS(i, k, dep+1);
//tot+1; Ak = min{Ak, Ai};
//if ((k=root and tot>1) or (k<>root and Ai >= Dk))
// Cut_k = true
//if (Ai > Dk)
// Bridge[k][i] = true
}
post[i] = p;
p1;
Ck = Black;
}
Topsort
for i <- n downto 1
which post[j] = i;
Kruskal
{
sort all edges;
for i <- 1 to m
{
if (find(a[i]) <> find(b[i]))
{
tree[i] = true;
union(a[i], b[i]);
}
}
}
Prim
{
for i <- 1 to n
{
for j <- 1 to n
{
if (ok[j] = false)
heap_ins(g[i][j]);
}
ok[heap[1]] = true;
tree[pre[1]][heap[1]] = true;
}
}
Bellman-Ford
for i <- 1 to n+1
{
ok = false;
for j <- 1 to n
for k <- 1 to n
if (d[j] + g[j][k] < d[k])
{
d[k] = d[j]+g[j][k];
ok = true;
}
if (ok = false)
break;
if (i = n+1 and ok = true)
return neg-cycle;
}
Dijkstra
for i <- 1 to n
{
min = inf; oper = -1;
for j <- 1 to n
if (d[j] < min)
{
min = d[j]; oper = j;
}
if (oper = -1)
return;
for j <- 1 to n
if (d[j] > d[oper] + g[oper][j])
{
d[j] = d[oper] + g[oper][j];
pre[j] = oper;
}
}
Floyd
Floyd
{
for k <- 1 to n
for i <- 1 to n
for j <- 1 to n
if (d[i][j] > d[i][k]+d[k][j])
{
d[i][j] = d[i][k] + d[k][j];
p[i][j] = k;
}
}
GetPath(i, j): string
{
if (p[i][j] = 0)
return ij;
s = GetPath(i, p[i][j]);
s - p[i][j];
s + GetPath(p[i][j], j);
return s;
}
Matrix Floyd
{
M[1] = G;
for x <- 2 to n
{
for i <- 1 to n
for j <- 1 to n
for k <- 1 to n
if (M[x][i][j] > M[x-1][i][k] + G[k][j])
M[x][i][j] = M[x-1][i][k] + G[k][j];
}
}
