没有用的话 qaq :
Ummmm... 图论的大部分知识本来早就有学过, 只是一直没有写成博文来梳理, 但既然上了 qbxt DP 图论就写一篇来总结下, 主要是来听 DP 的, 但... 由于太菜的原因, DP 听得天花乱坠 QWQ
一个有 n 个结点的连通图的生成树是原图的极小连通子图, 且包含原图中的所有 n 个结点, 并且有保持图连通的最少的边. -- 百度百科
二, 最小生成树算法
顾名思义, 连通图图中求出图中最小生成树的算法叫做最小生成树算法, 分为 Prim 和 Kruskal 两种
1,Prim(普利姆算法)
a. 将所有点分为两个集合, 一个集合代表已加入最小生成树点的集合 S, 另一个集合代表没有加入最小生成树的点的集合 T
b. 计算 T 集合中的点到达 S 集合的最短距离, du =min<u,v>∈E,v∈S{wu,v}
c. 选取集合 T 中到达 S 集合中距离最小的一个点, 加入 S 集合, 并更新 T 集合中其它点到 S 集合的距离.
d. 重复上述过程, 直到所有点都被选入了最小生成树, 每次加入的边即是最小生成树的边
正确性证明:
Prim 是一个基于贪心的算法, 可以采用归纳法和反证法证明其正确性.
首先证明第一条选中的边 e1 一定包含在某最优解方案中, 如果最优解中不包含边 e1, 则加入 e1 一定会出现环, 且环上存在比 e1 大的边, 用 e1 替换之答案更优, 假设最优解包含前 k 个选中的边, e1, e2, . . . , ek, 则类似地可证明 ek+1 存在于最优解中
运用归纳法, Prim 算法得到的 n ? 1 条边构成最优解(摘自 yousiki 课件).
简单来说就是每次选择一条最短的边保证了最小生成树距离最短, 并且不产生环.
朴素算法的复杂度较劣, 我们可以采取在选择最短边时可以采用堆优化(优先队列), 将其复杂度优化为 O((n+m)logn).
带堆优化代码
- inline void prim(int s)
- {
- for(int i=1;i<=n;i++)
- dist[i]=INF,vis[i]=false;
- heap.push(make_pair(0,s));
- vis[s]=true;
- while(!heap.empty())
- {
- int p=heap.top().second;
- if(!vis[p]) ans+=-1*heap.top().first;
- heap.pop();
- if(vis[p]) continue;
- vis[p]=true;
- for(int i=first[p];i;i=edge[i].nxt)
- {
- int e=edge[i].ed,d=edge[i].len;
- if(dist[e]>dist[p]+d)
- {
- dist[e]=dist[p]+d;
- heap.push(make_pair(-dist[e],e));
- }
- }
- }
- }
在堆优化后, prim 的复杂度仍较高, 一般不采用, 但 Prim 在一类给定 N 个点 (N 的范围较大) 没有给边, 求从某点出发经过所有点后的最短距离的题目中占优, 若要采用 Kruskal 算法就需要建成一个完全图, 建图的时间复杂度为 O(n^2), 显然不优, Prim 的优势在于, 不需要建成一个完全图, 可以边做边在更新集合 T 到集合 S 的距离时计算边的距离.
2,Kruskal(克鲁斯卡尔算法)
其主要采用了贪心的思想和并查集的维护, 我们如果想在图中找出一个最小生成树的话, 贪心的想, 肯定要先选择最短的边(显然, 因为最小生成树嘛), 但就这样一条一条选择最短的边知道选到 n-1 一条为止吗, 显然不对, 因为我们选择的三条边可能形成环, 有环显然不优, 所以我们就用并查集维护一下, 如果一条边的起点和终点的祖宗一样, 即已经联通, 我们就不能加, 因为显然对于联通的两个点之间再加一条边就会形成环, 否则, 这条边就可以选择.
不懂并查集戳这里
算法复杂度 O(mlogm)
代码实现比 Prim 要简单
- #include<cstdio>
- #include<iostream>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- struct node
- {
- int s,e,d;
- };
- node edge[2333];
- int ans,f[2333],n,m,cnt;
- inline bool cmp(node x,node y)
- {
- return x.d<y.d;
- }
- inline int find(int k)
- {
- if(f[k]==k) return f[k];
- return f[k]=find(f[k]);
- }
- inline void kruskal()
- {
- for(int i=1;i<=m;i++)
- {
- int f1=find(edge[i].s);
- int f2=find(edge[i].e);
- if(f1!=f2)
- {
- cnt++;
- ans+=edge[i].d;
- f[f1]=f2;
- }
- if(cnt==n-1) break;
- }
- return;
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=m;++i)
- scanf("%d%d%d",&edge[i].st,&edge[i].ed,&edge[i].d);
- for(int i=1;i<=n;++i)
- f[i]=i;
- sort(edge+1,edge+m+1,cmp);
- kruskal();
- printf("%d",ans);
- return 0;
- }// 看看就好, 打了打而已, 不保证能过编译 Orz QwQ
图论最小生成树算法中, 我们经常采用 Kruskal, 因为它的效率较高
三, 最大生成树: 反过来就好
写在最后, Yousiki Orz Orz
最小生成树
来源: http://www.bubuko.com/infodetail-3152700.html