ACM培训第三发 简单图论 主讲人—— 陈星毅.

Presentation on theme: "ACM培训第三发 简单图论 主讲人—— 陈星毅."— Presentation transcript:

1 ACM培训第三发 简单图论 主讲人—— 陈星毅

2 上节课你们正昊学长给你们讲了一些图的概念，比如说树、有向图、无向图；如何以代码形式表示图；图的存储方式：邻接表和邻接矩阵。并且他还讲了两个搜索（据说训练题没什么人做。。
。） 正昊一脸幽怨地表示不开心。 So upset。。。

3 （啊不对，那是你们祝♂叶学长的表情，不是正昊的，发错了2333
（啊哈祝叶在不在这里啊，不管啦hhhhh

4 为了复习一下，我们从一道水题开始—— 给出n个点m条边，问有多少个连通分量。
输入：第一行两个整数n和m(n<=m<=1000)，点从1到n开始编号。从第二行开始的m行，每一行为两个整数a和b，表示点a和点b之间有一条边。 输出：连通分量的数目。 连通分量是shenmegui？有没有人知道？

5 显然可以用深搜的方法写。 首先是存图，为了明显我们先用邻接矩阵表示。（也就是二维数组） const int N=1010;
int n, m, g[N][N], vis[N], cnt; //先把要用的东西都声明，cnt表示联通分量的数目，g数组用来存图，vis数组用来标记是否访问过。

6 然后是递归函数 void dfs(int u){ if(vis[u]) return; else{ vis[u]=1;
for(int i=1;i<=n;i++) if(g[u][i]) dfs(i); }

7 int main(){ while(~scanf(“%d%d”,&n,&m){ cnt=0; memset(g,0,sizeof(g)); memset(vis,0,sizeof(vis)); for(int i=0;i<m;i++){ scanf(“%d%d”,&a,&b); g[a][b]=g[b][a]=1; } solve(); return 0;

8 void solve(){ for(int i=1;i<=n;i++) if(!vis[i]){ cnt++; dfs(i); } printf(“%d\n”,cnt); 问题解决了。 那么如果，需要输出同一个联通分量的所有点呢？ 比如说和编号为1的点同一个联通分量的点。

9 不难想到，属于同一个联通分量的点，除了第一个被访问到的点外，其它的点的联通分量编号都与上一个访问的点的所属联通分量编号相同。
则只需要将递归函数改一个小地方就可以了。

10 void dfs(int u){ if(vis[u]) return; else{ vis[u]=cnt; for(int i=1;i<=n;i++) if(g[u][i]) dfs(i); } 然后vis值相同的点即属于同一个联通分量。

11 然后复习下邻接表 通常用4个数组： 假定最多有N个点，M条边 int head[N], nxt[M], to[M], cost[M];
head[i]表示以 i 为源点的第一条边的编号。 nxt[j]表示编号为 j 的边的下一条边的编号。 to[j]表示编号为 j 的边指向的点。 cost[i]表示编号为 j 的边的权值或者说边长 以tot表示边的总数，初始化为0。 初始化以memset(head,-1,sizeof(head));即可

12 void dfs(int u){ if(vis[u]) return; else{ else vis[u]=cnt; for(int i=head[u];~i;i=nxt[i]) dfs(to[i]); } void addedge(int u,int v){ to[tot]=v; nxt[tot]=head[u]; head[u]=tot++;

13 除了用dfs，还有一个方法 并查集！

14 它的作用是模拟出一种集合，并提供合并不同集合、查询几个点是否属于相同集合的功能。
是一种树形结构的东西。 具体怎么操作呢？

15 其实实现的原理非常简单。 我们定义数组father[N]，表示编号为 i 的结点的父亲。 每次查询到两个点之间有我们要的联系的话，将其中一个结点设为另一个结点的父亲。 一次类推，那么只要这些点的“祖先结点”是同一个，则为同一个集合。 我们定义当 father[i]==i 时，i 即为祖先结点。

16 以刚才的连通分量为例 首先是初始化： for(int i=0;i<=n;i++) father[i]=i; 查询一个结点的祖先结点：
int Find(int x){ return x==father[x]? x : Find(father[x]); } 合并集合： void uni(int x,int y){ father[find(x)]=find(y);

17 然后我们只需要把所有边访问一遍，若这条边的两端 x 和 y 不属于同一个集合（即祖先结点不一样），则合并，否则跳过即可。
为了方便访问所有边，我们定义一个结构体： struct edge{ int u,v; }E[M];

18 然后，存图的时候—— for(int i=0;i<m;i++){ scanf(“%d%d”,&a,&b); E[i].u=a,E[i].v=b; } 然后遍历访问—— for(int i=0;i<m;i++) if(Find(E[i].u)!=Find(E[i].v)) uni(E[i].u,E[i].v); 然后有多少个联通分量呢？

19 set<int>all; all.clear(); for(int i=1;i<=n;i++) all.insert(Find(i)); printf(“%d\n”,all.size()); 即可。 并且，Find值相同的，即属于同一个集合，或者说，同一个联通分量。 这就是并查集。

20 我们重新回顾一下： 并查集的要点： 初始化：将所有的父亲结点设为自己 Find函数，递归查找祖先结点 uni函数，将不同结合合并

21 并查集的压缩路径优化 我们注意到一点： 如果当前有两个集合 12->1->3->4->5->6（6为祖先结点）
11->2->7->8->9->10（10为根节点） 然后要把11和12合并，那么就需要调动 12次Find函数， 然后如果来一发13->14 要把13和11合并，又要调用6次Find函数 效率太低

22 优化很简单 改一下Find函数就好 int Find(int x){ return x==f[x]? x : Find(f[x]); }
加一点东西—— int Find(int x){ return x==f[x]? x : f[x]=Find(f[x]);

23 12->1->3->4->5->6（6为祖先结点）
11->2->7->8->9->10（10为根节点） 调用Find(12)，得到6，并且—— 12->6, 1->6, 3->6, 4->6, 5->6 调用Find(11)，得到10，并且—— 11->10, 2->10, 7->10, 8->10, 9->10 然后合并，6->10。 这样再度合并相关点的时候，路径大大缩短

24 但需要注意两点： 一个是，压缩路径后，原有的“父子关系”就没了。 另一个是——举个例子 5->6->7, 1->2->3->4, 然后合并7和4，就得到 5->6->7->4, 1->2->3->4。 这个时候其实是没有压缩到路径的。 所以在看有多少个集合的时候，即使是用了压缩路径，也依然需要遍历Find(i)而不是father[i]。

25 并查集的用处不小，而且也不难掌握。 记住令不同元素变成同一个集合的因素是由我们决定的，而不仅仅是图里面的边。

26 最小生成树 我们知道树是指，所有结点连通、无环的图。
最小生成树则是，给出一些点一些边，以及边权——在总边权最小的情况下，取一些边使得这些点构成一棵树。 解决最小生成树的算法一般有prim算法、以及kruskal算法。时间关系只讲kruskal。至于前者有兴趣的同学可以自行了解。

27 先说kruskal算法 核心是我们刚介绍的并查集。
与求连通块个数时一样，定义当点连通（即相互可达）时，在同一个集合（即并查集中的同一个父亲）内。 然后，只需要对所有边按边权从小到大排序，每次不在同一个集合的点合并，已在同一个集合的跳过。这样到最后得出来的就是最小生成树。

28 正确性的证明 我百度了下好长好长…………你们有兴趣的自己去看，，，，，
易证，对于一个无向加权连通图，总是存在一棵或以上的有限课生成树，而这些生成树肯定存在至少一棵最小生成树。下面证明Kruskal算法构造的生成树是这些最小生成树中的一棵。 设T为Kruskal算法构造出的生成树，U是G的最小生成树。如果T==U那么证明结束。如果T != U，我们就需要证明T和U的构造代价相同。由于T != U，所以一定存在k > 0条边存在于T中，却不在U中。接下来，我们做k次变换，每次从T中取出一条不在U中的边放入U，然后删除U一条不在T中的边，最后使T和U的边集相同。每次变换中，把T中的一条边e加入U，同时删除U中的一条边f。e、f按如下规则选取：a). e是在T中却不在U中的边的最小的一条边；b). e加入U后，肯定构成唯一的一个环路，令f是这个环路中的一条边，但不在T中。f一定存在，因为T中没有环路。 这样的一次变换后，U仍然是一棵生成树。 　我们假设e权值小于f，这样变换后U的代价一定小于变换前U的代价，而这和我们之前假设U是最小生成树矛盾，因此e权值不小于f。 　再假设e权值大于f。由于f权值小于e，由Kruskal算法知，f在e之前从E中取出，但被舍弃了。一定是由于和权值小于等于f的边构成了环路。但是T中权值小于等于f（小于e）的边一定存在于U中，而f在U中却没有和它们构成环路，又推出矛盾。所以e权值不大于f。于是e权值等于f。 　　这样，每次变换后U的代价都不变，所以K次变换后，U和T的边集相同，且代价相同，这样就证明了T也是最小生成树。由证明过程可以知道，最小生成树可以不是唯一的。 无向图G的所有最小生成树的边权集合相同

29 struct edge{ int u,v,cost; bool operator < (const edge e) const{ return cost<e.cost; } }E[M]; int main(){ //读入数据存图 sort(E,E+m); for(int i=0;i<m;i++) if(Find(E[i].u)!=Find(E[i].v)) uni(E[i].u,E[i].v);

30 最短路算法 最短路问题可抽象为给出一些点一些边，找出从一个点（起点）到某一个点（终点）的最短路径长度。 最短路又分单源最短路和多源最短路。

31 单源最短路 即问的都是最短路都是从同一个起点，到其它某一个点的最短路径距离。
常用的有Dijkstra算法、bellman-ford算法以及spfa算法。

32 Dijkstra

33 怎么代码实现呢？ 我猜你们的表情： 就是要大小不一逼死强迫症！

34 const int inf=21e8; int g[N][N], d[N], vis[N]; int dijkstra(int s, int t){ memset(vis,0,sizeof(vis)); for(int i=0;i<=n;i++) d[i]=inf; d[s]=0; for(int i=0;i<n;i++){ int u=-1; for(int j=0;j<n;j++) if(!vis[j]) if(u==-1||d[u]>d[j]) u=j; vis[u]=1; for(int j=0;j<n;j++) if(!vis[j]&&g[u][j]) d[j]=min(d[j],g[u][i]+d[u]); } return d[t];

35 时间复杂度分析 显然可以看出来，该dijkstra的时间复杂度为O(n^2)，（假定n为点数），感觉有点不尽如人意，但大多数时候都够用了。
稀疏图下，用优先队列优化可以快很多，但只能得到由源点到终点的最短路，但稠密图下，则并没有，尤其若很多重边的时候，可能会比朴素实现还慢。 还可以用堆实现，可将复杂度优化到O((n+m)logn)。嗯。。。。这个我等你们来教我2333

36 bellman-ford 一条边(u,v)称为紧的，如果 dis[u] + gra[u][v] < dis[v] 松弛：
if( dis[u] + gra[u][v] < dis[v] ) dis[v] = dis[u] + gra[u][v]; 算法：每次对所有边进行松弛，直到某一轮迭代没有边可以松弛。可以证明最多需要松弛n-1次，n为顶点数。

37 spfa算法 用队列优化的bellman-ford算法 算法： 把起点s加入队列 取出队首，松弛以队首为起点的边
当一条边被松弛，则把该边的终点加入队列 当队列为空，算法结束

38 int spfa(int s,int t){ memset(inq,0,sizeof(inq)); for(int i=0;i<n;i++) d[i]=inf; d[s]=0,inq[s]=1; queue<int>q; q.push(s); while(!q.empty()){ int u=q.front(); inq[u]=0; q.pop(); for(int i=head[u];~i;i=nxt[i]){ int v=to[i]; if(d[v]>d[u]+cost[i]){ d[v]=d[u]+cost[i]; if(!inq[v]){ q.push(v); inq[v]=1; } return d[t];

39 要注意的是： dijkstra不能用于计算负权图，而spfa可以。
虽然看起来是spfa比较6，单有时用spfa算法TLE了用dijkstra却能过——dijkstra在对各种图进行最短路计算的时候，其平均复杂度是低于spfa的。 还碰到过用queue会TLE而用stack能a，这个，，原因还没搞清。 除了手写栈或队列，spfa还有两个方法优化，分别是SLF和LLL。有兴趣的可以自行了解。

40 多源最短路 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]); d[i][j]为任意i到任意j的最短距离。 但注意到复杂度是O(n^3)的，所以点数为100数量级的时候才好考虑使用。

41 今天的内容也比较多，我们回顾一下： 最开始的时候先讲了个求连通块数量的水题，用dfs一遍，用并查集一遍，并复习了下邻接矩阵和邻接表的使用。 然后是： 并查集——并查集压缩路径优化 最小生成树——kruskal算法 最短路—— 单源最短路：dijkstra和spfa 多源最短路：floyd

42 希望大家回去好好总结好好消化，训练题已群邮，大家好好刷哈~
有问题的可以留下来讨论 今天的培训就到这里，谢谢大家~

43 下一节内容预告： 是祝叶叶的专题，详情见部门专业或者群邮咯~ 再来一发祝叶叶 的表情2333