【五一qbxt】day5 图论
- 图论
学好图论的基础:
必须意识到图论hendanteng
xuehuifangqi(雾
- 图
G = (V,E)
一般来说,图的存储难度主要在记录边的信息
无向图的存储中,只需要将一条无向边拆成两条即可
- 存图:
1.邻接矩阵(经典):代码连接
用一个二维数组 edg[N][N] 表示
edg[i][j] 就对应由 i 到 j 的边信息
edg[i][j] 可以记录 Bool,也可以记录边权
举个栗子:
0 0 1 0
0 0 1 1
1 1 0 1
0 1 1 0
首先这是个无向图(因为它是对称的),其次,图如下:
缺点:如果有重边有时候不好处理
空间复杂度 O(V2)
点度等额外信息也是很好维护的
关于利用邻接矩阵存图及遍历:
#include <bits/stdc++.h> using namespace std; const int N = ; int ideg[N]/*记录入度*/, odeg[N]/*记录出度*/, n, m, edg[N][N]/*邻接矩阵*/;
bool visited[N];//标记某个点是否被遍历过 void travel(int u, int distance/*边权*/)//遍历
{
cout << u << " " << distance << endl; visited[u] = true;
for (int v = ; v <= n; v++)//遍历u的所有出边
if (edg[u][v] != - && !visited[v])
travel(v, distance + edg[u][v]); //if there is an edge (u, v) and v has not been visited, then travel(v)
}
int main()
{
cin >> n >> m;//n点数,m边数
memset(edg, -, sizeof edg);//先初始化数组为-1(这里定没有负边权)
memset(visited, false, sizeof visited);
for (int u, v, w, i = ; i <= m; i++)//疑似有向图
cin >> u >> v >> w, edg[u][v] = w, odeg[u]++,/*出度*/ ideg[v]++;//入度
for (int i = ; i <= n; i++)
cout << ideg[i] << " " << odeg[i] << endl;
for (int i = ; i <= n; i++)
if (!visited[i]) travel(i, );
} /*
Given a graph with N nodes and M unidirectional edges.
Each edge e_i starts from u_i to v_i and weights w_i
Output a travelsal from node 1 and output degree of each node.
输出从1开始的遍历 并且 输出每个点的度数
*/
2.邻接表:
对每一个点 u 记录一个 List[u],包含所有从 u 出发的边
手写链表(前向星/指针)
指针:
(我的内心os只剩下这个了)(真的没看懂啊)
前向星:
这个之前介绍过了,嗯。详情见:【图论】最短路问题之spfa
wyx的和上面介绍的差不多,至少思路是一样的qwq:
#include <bits/stdc++.h> using namespace std; const int N = ; struct edge {
int u, v, w, next;
}edg[N];
int head[N]; //List[u] stores all edges start from u
int ideg[N], odeg[N], n, m, cnt; //cnt: numbers of edges
bool visited[N]; void add(int u, int v, int w)
{
int e = ++cnt;
edg[e] = (edge){u, v, w, head[u]};
head[u] = e;
}
void travel(int u, int distance)
{
cout << u << " " << distance << endl; visited[u] = true;
for (int e = head[u]; e ; e = edg[e].next)
if (!visited[edg[e].v])
travel(edg[e].v, distance + edg[e].w); //if there is an edge (u, v) and v has not been visited, then travel(v)
}
int main()
{
cin >> n >> m; cnt = ;
memset(visited, false, sizeof visited);
memset(head, , sizeof head);
for (int u, v, w, i = ; i <= m; i++)
cin >> u >> v >> w, add(u, v, w), odeg[u]++, ideg[v]++;
for (int i = ; i <= n; i++)
cout << ideg[i] << " " << odeg[i] << endl;
for (int i = ; i <= n; i++)
if (!visited[i]) travel(i, );
} /*
Given a graph with N nodes and M unidirectional edges.
Each edge e_i starts from u_i to v_i and weights w_i
Output a travelsal from node 1 and output degree of each node.
*/
邻接矩阵中会有很多空余的空间,为了实现变长的数组:
用 STL 中的 vector 实现变长数组
只需要 O(V + E) 的空间就能实现图的存储
关于vector:
vector 本质就是 c++ 模板库帮我们实现好的变长数组
向一个数组 a 的末尾加入一个元素 x a:push_back(x)
询问数组 a 的长度 a:size()
注意: vector 中元素下标从 0 开始
代码实现(存储+遍历):
#include <bits/stdc++.h> using namespace std; const int N = ; struct edge {
int u, v, w;
};
vector<edge> edg[N];//edg[1],edg[2]……都是变长数组 //vector<edge> edg表示edg是一个变长数组
int ideg[N], odeg[N], n, m, cnt; //cnt: numbers of edges
bool visited[N]; void add(int u, int v, int w)//加边
{
edg[u].push_back((edge){u, v, w});
}
void travel(int u, int distance)
{
cout << u << " " << distance << endl; visited[u] = true;
for (int e = ; e < edg[u].size(); e++)//从0开始枚举直到数组长度 (也就是枚举u的所有出边)
if (!visited[edg[u][e].v])
travel(edg[u][e].v, distance + edg[u][e].w); //if there is an edge (u, v) and v has not been visited, then travel(v)
}
int main()
{
cin >> n >> m; cnt = ;
memset(visited, false, sizeof visited);
for (int u, v, w, i = ; i <= m; i++)
cin >> u >> v >> w, add(u, v, w), odeg[u]++, ideg[v]++;
for (int i = ; i <= n; i++)
cout << ideg[i] << " " << odeg[i] << endl;
for (int i = ; i <= n; i++)
if (!visited[i]) travel(i, );
} /*
Given a graph with N nodes and M unidirectional edges.
Each edge e_i starts from u_i to v_i and weights w_i
Output a travelsal from node 1 and output degree of each node.
*/
- 生成树
给定一个连通无向图 G = (V; E)
E′⊂ E
G′= (V, E′) 构成一棵树
G′就是 G 的一个生成树
我们发现:生成树的数量是很多很多的(指数级别的qwq)
所以,引出————
- 最小生成树:
给定一个 n 个点 m 条边的带权无向图,求一个生成树,使得生成树中最大边权的最小?
数据范围: n; m ≤ 106(不过这真的确定不是瓶颈生成树吗qwq)
解决算法:
1.Kruskal
2.Prim
3.Kosaraju
写在算法之前:
并查集:
生成树的本质:选取若干条边使得任意两点联通;
维护图中任意两点的连通性
查询任意两点连通性
添加一条边,使两个端点所在连通块合并
Kruskal:
算法流程:
1.将原图无向边按照边权从小到大排序;
2.找到当前边权最小的边e(u,v);
如果u和v已经连通,则直接删除这条边
(判断是否连通:利用并查集来判断,如果在连接之前已经在一个并查集中,则为环,不能加入)
如果u和v未连通,将之加入生成树;
3.重复上述过程;
感性证明:
显然我们最后要把两个连通块连起来,现在找最小的连起来,比以后连起来和要小(不严谨qwq)
something amazing:
Rigorous proof:
消圈算法:在图上找到一个圈,删掉权值最大的一条
理性代码(这是我见到的第一个用万能头的老师)
#include <bits/stdc++.h> using namespace std; const int maxn = ;
struct edge {
int u, v, w;
}edg[maxn];
int n, m, p[maxn], ans = ; bool cmp(edge a, edge b)//cmp
{return a.w < b.w;}
int findp(int t) //找“父亲”
{return p[t] ? p[t] = findp(p[t]) : t;}
bool merge(int u, int v)//并查集的过程 (即判断是否形成了环)
{
u = findp(u); v = findp(v);
if (u == v) return false;
p[u] = v; return true;
}
int main()
{
cin >> n >> m;
for (int i = , u, v, w; i <= m; i++)
cin >> u >> v >> w, edg[i] = (edge){u, v, w};//因为只需要访问边,所以只记下来边
sort(edg + , edg + m + , cmp);//排序 for (int i = ; i <= m; i++)//从最小到最大进行枚举
if (merge(edg[i].u, edg[i].v))
ans = max(ans, edg[i]. w);
cout << ans << endl;
}
prim:
先选择1号点,连接所有与1相连的边中最小的连上去,组成一个连通块,然后找到和当前组成的连通块相连的点中最小的加进去松弛;
Kosaraju:
先认为每个点都是孤立的连通块,然后对于每个点,找到和它相连的最小的边,将这两个“连通块”连成一个,重复多次;
- 路径:
P = p0,……, pn 为 u 到 v 的路径
p0 = u, pn = v
对于任意i 属于 [1, n]; 存在e : (pi−1; pi) 属于 E
P 的长度:
length(P) = ∑e∈P length(e)
- 简单路径:
简单来说就是不要闲着没事在图里绕圈圈的路径;
树中的简单路径是唯一的,图中的简单路径不一定是唯一的;
负权环
如果存在一个环,其边权和为负数,则称为负全环;
u=>v存在一个负全环,d(u,v)= −∞
- 最短路径问题(SSP):
给定一个有向图 G,询问 u 到 v 之间最短路径长度
记 d(u, v) 表示 u 到 v 的最短路径长度
为方便起见,不妨规定 u 和 v 不连通时, d(u, v) = +∞
Algorithms for Shortest Path Problem
floyd
Bellman-Ford
SPFA
Dijkstra
四种算法都要掌握qwq因为每一种算法都有各自的优势和缺点,都不能互相替代啊qwq
松弛操作(SSP 算法的本质思想就是不断进行松弛操作):
对于最短路d(u, v),满足:
d(u, v)(注意这里是指最短路径了已经) ≤ d(u, w) + d(w, v)
松弛:记当前算出一个d(u,v)(或许它不是最短的),所以枚举找到更短的,即取min;
- floyd:
开始时,d(u, v)表示从u到v的边权;
用邻接矩阵的形式记录d;
设u和c没有边,d(u, v)=+∞;
u和v有重边,保留最小边权;
三层循环枚举 k; i; j,执行松弛操作:
d(i, j) = min{d(i,j),d(i,k) + d(k, j)};
证明bulabula的:
为什么三层循环完了以后就都是最短值了???:
假设3=>5的最短路径为3=>2=>4=>1=>7=>5
那么4=>7min路:4=>1=>7
k=1的时候,d(4,7)一定是真实值
k=2的时候,d(3,4)一定是真实值
k=3的时候,没有什么影响
k=4的时候,d(2,1)为真实值,那么d(3,7)就为真实值
k=5的时候,没有什么影响
k=6的时候,没有什么影响
k=7的时候,d(1,5)为真实值,那么d(3,5)就为真实值
floyd总结:
大约只能跑n=500
不断枚举松弛操作的中间点k(注意必须先枚举k)
算法时间复杂度O(n^3);
优势:处理出 d 之后,任意两点 SP 能 O(1) 询问;
floyd判负环:
完成floyd后检查是否存在d(u,u)<0;
#include <bits/stdc++.h> using namespace std; const int N = ;
const int inf = << ; int d[N][N], n, m;
int main()
{
cin >> n >> m;
for (int i = ; i <= n; i++)
for (int j = ; j <= n; j++){
if(i==j) d[i][j]=;//自己到自己为0
else d[i][j] = inf;//先全都设成无穷大
}
for (int u, v, w, i = ; i <= m; i++)
cin >> u >> v >> w, d[u][v] = min(d[u][v], w);//取最小的边(min主要针对重边) for (int k = ; k <= n; k++)//先枚举中间点
for (int i = ; i <= n; i++)
for (int j = ; j <= n; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
- 单源最短路:
不需要知道图中任意两个点的SP
只需要知道某一点u到其他点的SP
u 称为源点,单源最短路就是求从 u 出发的最短路
为方便,下面记源点为 S
- Bellman-ford:
将 d(S,u) 简写为 d(u),初始 d(S) = 0, d(u) = +∞
执行 n 次全局松弛操作
枚举图中每条边 e : (u,v,w)
松弛 d(v) = min{d(v),d(u) + w}(思想:DP+贪心)
why?
优势:算法很直观(并不觉得它直观qwq)
算法时间复杂度 O(nm)
判负权环:
再多进行一次全局松弛,如果有 d 被更新,一定有负权环
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + ;
const int inf = << ; struct edge{
int u, v, w;
}edg[N];
int d[N], n, m, S;
int main()
{
cin >> n >> m >> S;
for (int i = ; i <= n; i++) d[i] = inf;//初始化为inf
for (int u, v, w, i = ; i <= m; i++)
cin >> u >> v >> w, edg[i] = (edge){u, v, w};//输入,加边 d[S] = ;//源点到源点的单源最短路显然为0
for (int i = ; i <= n; i++)
for (int j = ; j <= m; j++)
{
int u = edg[j].u, v = edg[j].v, w = edg[j].w;
d[v] = min(d[v], d[u] + w);//emmm只可意会不可言传怎么办qwq
}
}
- SPFA简单介绍(因为已经专门写过博客了qwq):
(Bellman Ford的优化)
没有必要把所有点的出边全部更新,可以只用一部分的点来更新(用来更新的点是上一次被更新的,因为它的值发生了改变,所以需要更新qwq);
算法何时终止?
记录每个点加入 Queue 的次数
u 被加入 Queue 一次,意味着 d(u) 被更新了一次
u 最多进入队列 n − 1 次,否则肯定有负权环
时间复杂度肯定不劣于 Bellman-ford,实际远不到 O(nm)
(毒瘤数据还是会达到O(nm)(网格图类型),最优可以到O(2m))
网格图会炸掉=>我们可以在做题时利用它来判断是不是网格图。如果使用SPFA跑某个图很慢的话,八九不离十是网格图;
我爱spfa
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + ;
const int inf = << ; struct edge{
int u, v, w;
};
vector<edge> edg[N];
int d[N], n, m, S; queue<int> Queue;
bool inQueue[N];
int cntQueue[N]; void add(int u, int v, int w)
{
edg[u].push_back((edge){u, v, w});
}
int main()
{
cin >> n >> m >> S;
for (int i = ; i <= n; i++) d[i] = inf;
for (int u, v, w, i = ; i <= m; i++)
cin >> u >> v >> w, add(u, v, w); d[S] = ; inQueue[S] = true; Queue.push(S);
while (!Queue.empty())
{
int u = Queue.front(); Queue.pop(); inQueue[u] = false;
for (int e = ; e < edg[u].size(); e++)
{
int v = edg[u][e].v, w = edg[u][e].w;
if (d[v] > d[u] + w)
{
d[v] = d[u] + w;
if (!inQueue[v])
{
Queue.push(v); ++cntQueue[v]; inQueue[v] = true;
if (cntQueue[v] >= n) {cout << "Negative Ring" << endl;/*判断负权环*/ return ;}
}
}
}
}
for (int i = ; i <= n; i++)
cout << d[i] << endl;
}
- dijkstar:
适用于无负权边的图
在Queue中的点d不会再更新
detail:怎么找到不在Queue中最下的u???
法1:
暴力扫描:
从原点s开始,找权值最小的一条边,它的对应点为i,加入队列,松弛与i相连的点。再找离点i权值最小的点……以此循环往复。
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + ;
const int inf = << ; struct edge{
int u, v, w;
};
vector<edge> edg[N];//表示每一个edg[i]都是一个动态数组
int d[N], n, m, S; bool relaxed[N];//表示一个点是否在队列里 1不在 0在
/*struct Qnode {
int u, du;
bool operator<(const Qnode &v)
const {return v.du < du;}
};
priority_queue<Qnode> PQueue;*/ void add(int u, int v, int w)
{
edg[u].push_back((edge){u, v, w});
}
int main()
{
cin >> n >> m >> S;
for (int i = ; i <= n; i++) d[i] = inf;
for (int u, v, w, i = ; i <= m; i++)
cin >> u >> v >> w, add(u, v, w); d[S] = ;
for (int i = ; i <= n; i++)
{
int u = ; while (relaxed[u]) ++u;//找到第一个编号不在队列中的u
for (int j = ; j <= n; j++)
if (!relaxed[j] && d[j] < d[u]) u = j; //找到距离最小的一个还未被松弛的点
//find a node u not relaxed yet with least(smallest) d(u)
relaxed[u] = true;//放进队列
for (int e = ; e < edg[u].size(); e++)
{
int v = edg[u][e].v, w = edg[u][e].w;
d[v] = min(d[v], d[u] + w);//枚举u所有出边,松弛
}
}
for (int i = ; i <= n; i++)
cout << d[i] << endl;
}
法2:
优先队列
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + ;
const int inf = << ; struct edge{
int u, v, w;
};
vector<edge> edg[N];
int d[N], n, m, S; bool relaxed[N];
struct Qnode {//堆内的元素
int u, du;
bool operator<(const Qnode &v)//重载emm显然我不会写
const/*划重点不能少*/ {return v.du < du;}//表示每次取堆顶的最小值
};
priority_queue<Qnode> PQueue;//类型 Qnode void add(int u, int v, int w)
{
edg[u].push_back((edge){u, v, w});
}
int main()
{
cin >> n >> m >> S;
for (int i = ; i <= n; i++) d[i] = inf;
for (int u, v, w, i = ; i <= m; i++)
cin >> u >> v >> w, add(u, v, w); d[S] = ; PQueue.push((Qnode){S, });//存储需要更新的点d最小的
while (!PQueue.empty())
{
int u = PQueue.top().u; PQueue.pop();
if (relaxed[u]) continue;//已经松弛过
//if edges staring from u are already relaxed, no need to relax again.
relaxed[u] = true;
for (int e = ; e < edg[u].size(); e++)//枚举u所有出边
{
int v = edg[u][e].v, w = edg[u][e].w;
if (d[v] > d[u] + w)
{
d[v] = d[u] + w;//更新松弛
PQueue.push((Qnode){v, d[v]});
//if d(v) is updated, push v into PQueue
}
}
}
for (int i = ; i <= n; i++)
cout << d[i] << endl;
}
- DAG(有向无环图):
DAG不要求弱联通:
弱联通:把有向图改为无向图后连通
- 拓扑排序:
有拓扑序的一定是DAG,是DAG的一定有拓扑序
算法??
代码:
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + ;
const int inf = << ; struct edge{
int u, v;
};
vector<edge> edg[N];
int n, m, outdeg[N]/*记录出边数*/, ans[N]/*储存答案的*/; queue<int> Queue;//度数为0的点
void add(int u, int v)
{
edg[u].push_back((edge){u, v});
}
int main()
{
cin >> n >> m;
for (int u, v, i = ; i <= m; i++)
cin >> u >> v, add(v, u),/*反着记边(记录某个点的入边)这样可以保证删除时容易删除*/ outdeg[u]++; for (int i = ; i <= n; i++)
if (outdeg[i] == ) Queue.push(i);
for (int i = ; i <= n; i++)
{
if (Queue.empty())//如果没有度数为0的点,说明不是DAG
{printf("Not DAG"); return ;}
int u = Queue.front(); Queue.pop(); ans[n - i + ] = u;//因为拓扑最先剔除的应该是最后的,所以倒着存储
for (int e = ; e < edg[u].size(); e++)
{
int v = edg[u][e].v;
if (--outdeg[v] == ) Queue.push(v);
}
}
}
如何利用拓扑排序求单源最短路?
已知拓扑排序:3 1 2 7 4 6 5(1为源点)(图片from yy)
https://blog.csdn.net/zzran/article/details/8926295
怎么算一个图的拓扑排序有多少个???不可能,做不了;
- 最近公共祖先LCA:
O(n)做法:
先跳到同一高度,再同时向上跳直到相遇;
只讲树上倍增;
算是递归吧:x的2j层的祖先,等于x的2j-1的祖先的2j-1的祖先
:=赋值的意思(区分前面qwq)
从log2n开始向0枚举(2^j的枚举),如果相遇,则不动,如果未相遇,就向上跳,直到跳的长度为1,那么此时答案就是他们的父亲。
证明:
(MST最小生成树)
最新文章
- 关于click和submit的笔记
- maya的卡通渲染
- mysql与mysqld
- PAT-乙级-1052. 卖个萌 (20)
- Centos之LAMP环境搭建
- Oracle 如何让别人能够连接到你的数据库
- Oracle 性能优化 — 统计数据收集[Z]
- SimpleDateFormat 的线程安全问题与解决方式
- poj 2769 Reduced ID Numbers(memset使用技巧)
- GetStdHandle 函数--获取标准设备的句柄
- python 1-100的数相加的和
- [20181214]open file using O_DIRECT.txt
- Linux下执行Oracle的sql脚本
- C# 一般处理程序生成验证码
- The Doors
- shell 变量介绍
- GTID的相关特性
- Django 模板继承extend 标签include block
- nginx分发请求的2种方式:1、指明server_name;2、通过location过滤uri来分发请求;
- outline详解