数据结构回顾及展望（二）（3.22更新）
事在人为，盛衰之理，虽曰天命，岂非人事哉！原庄宗之所以得天下，与其所以失之者，可以知之矣。------------《伶官传序》
你选择的方向和你决定付出的努力决定你达到的高度和广度。----------引言
预备知识（默认已掌握）
连通图：在无向图中，若任意两个顶点与都有路径相通，则称该无向图为连通图。
强连通图：在有向图中，若任意两个顶点与都有路径相通，则称该有向图为强连通图。
连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；
权代表着连接连个顶点的代价，称这种连通图叫做连通网。
生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。
在学习最小生成树之前，还有一个重要的工具要学习，就是
- 并查集
为了形象地说明这是什么玩意，我找了好久大佬对此题独到的理解：
话说江湖上散落着各式各样的大侠，有上千个之多。他们没有什么正当职业，整天背着剑在外面走来走去，碰到和自己不是一路人的，就免不了要打一架。但大侠们有一个优点就是讲义气，绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”，只要是能通过朋友关系串联起来的，不管拐了多少个弯，都认为是自己人。这样一来，江湖上就形成了一个一个的帮派，通过两两之间的朋友关系串联起来。而不在同一个帮派的人，无论如何都无法通过朋友关系连起来，于是就可以放心往死了打。
在江湖上，有非常多的英雄，我们不妨用一个f数组来保存每位英雄的掌门。
int f[x]; //x为要处理元素个数在帮派中，有掌门和弟子，那么刚刚开始肯定都是一个人行走江湖，所以在程序初始化的时候，每个人的掌门都是他们自己。
void set(){for(int i = 1;i <= X;i++){ f[i] = i;} }我们在判断两位英雄是否师出同门的时候，要用到查找掌门的函数。
这里我们用了记忆化，俗称“压缩路径”;
int find(int x){ x==f[x]?x:f[x]=find(f[x]); }一行高能代码 献上 不成敬意
感兴趣的做做并查集裸题 洛谷p3367,我的个人题解仅供参考
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,f[10005];
int find(int x){ return x==f[x]?x:f[x]=find(f[x]); }
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
if(a==1) f[find(b)]=find(c);
else find(b)==find(c)?cout<<"Y"<<endl:cout<<"N"<<endl;
}
return 0;
}介绍完毕，正式开始最小生成树的学习
- 最小生成树
Kruskal 算法
用并查集优化后时间复杂度：O(mlogm+mα(n))，α(n)是一次并查集的复杂度。//这个真不会分析
贪心算法，它是将边按权值排序，每次从剩下的边集中选择权值最小且两个端点不在同一集合的边加入生成树中，反复操作，直到加入了n-1条边。
（1）将G中的边按权值从小到大快排。
（2）按照权值从小到大依次选边。若当前选取的边加入后使生成树T形成环，则舍弃当前边，否则标记当前边并计数。
（3）重复（2）的操作，直到生成树T中包含n-1条边，否则当遍历完所有边后，选取不到n-1条边，表示最小生成树不存在。
算法的关键在于如何判定新加入的边会不会使图G'产生环，在这里用并查集，如果新加入的边的两个端点在并查集的同一集合中，说明存在环，需要舍弃这条边，否则保留当前边，并合涉及的两个集合。
有图啥都好说
具体实现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,ans,f[5005];
struct brim
{
int begin,end,val;
}edge[200005];
bool cmp(brim a,brim b)
{
return a.val<b.val;
}
int find(int x)
{
if(f[x]==x)return x;
else
{
f[x]=find(f[x]);
return f[x];
}
}
void kruskal()
{
int cnt=0;
for(int i=1;i<=m;i++)
{
if(find(edge[i].begin)==find(edge[i].end))continue;
ans+=edge[i].val;
f[find(edge[i].begin)]=find(edge[i].end);
cnt++;
if(cnt==n-1)break;
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++)
{
cin>>edge[i].begin>>edge[i].end>>edge[i].val;
}
sort(edge+1,edge+1+m,cmp);
kruskal();
cout<<ans;
return 0;
}Prim 算法
Prim算法是一种贪心算法，它最初将无向连通图G中所有顶点V分成两个顶点集合VA和VB。在计算过程中VA中的点为已经选好连接入生成树的点，否则属于VB。最开始的时候VA只包含任意选取的图G中的一个点u，其余的点属于VB，每次添加一个VB中的点到VA，该点是集合VB到集合VA中距离最小的一个点。直到V个顶点全部属于VA，算法结束。显然出发点不同，最小生成树的形态就不同，但边权和的最小值是唯一的。
在代码里给出进一步的解释吧
模板题 P3366 【模板】最小生成树
#include<bits/stdc++.h>
#define maxn 5005
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,ans,dis[maxn],mapp[maxn][maxn],tot;//需要n（点），m（边），dis用来记录当前所在点到其他点的边权值，mapp[i][j]表示i到j的边权值，tot为当前加入生成树的点数
bool visit[maxn];//true表示点已经加入生成树，false为没有
void prim()
{
int pos;//记录最小的边连向的点的编号
visit[1]=true;//将1号顶点加入//用true比较好，因为bool数组初始化是false
tot++;
while(tot<=n-1)//到n的时候就不能再进行加点操作了，因为都进入了
{
int findmin=INF;
for(int i=1;i<=n;i++)
{
if(!visit[i]&&dis[i]<findmin)findmin=dis[i],pos=i;//注意对book的判断啊，加入最小生成树的不能再去判断
}
visit[pos]=true;//，找到这个最小权值边所连的点，置为标记过
tot++;
ans+=dis[pos];
for(int i=1;i<=n;i++)
{
if(!visit[i]&&dis[i]>mapp[pos][i])dis[i]=mapp[pos][i];//重要！：更新当前所在点到其他点（当然是未加入生成树的）的边值
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)//初始化map
{
for(int j=1;j<=n;j++)
{
if(i==j)continue;
mapp[i][j]=INF;
}
}
for(int i=1,b,e,v;i<=m;i++)
{
cin>>b>>e>>v;
if(v<mapp[b][e])mapp[b][e]=v,mapp[e][b]=v;//去重边，维持其最小的边
}
for(int i=1;i<=n;i++)mapp[i][i]=0;//去自环
for(int i=1;i<=n;i++)dis[i]=mapp[1][i];//初始不如从1点开始找
prim();
cout<<ans;
return 0;
}3.22更新：补充
之前写的prim比较朴素，补充两个优化
- 链式前向星
1 结构体数组edge存边，edge[i]表示第i条边,
2 head[i]存以i为起点的第一条边(在edge中的下标)
struct edge
{
int v;//这条边的终点
int next;//下一条边的存储下标(默认0)
int w;//权值
}e[200005<<1];//无向图边数*2若以点i为起点的边新增了一条，在edge中的下标为j.
那么edge[j].next=head[i];然后head[i]=j.
inline void add(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}即每次新加的边作为第一条边，最后倒序遍历
3.遍历
遍历以st为起点的边
for(int i=head[st]; i!=0; i=edge[i].next)i开始为第一条边，每次指向下一条(以0为结束标志)
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
int v;//这条边的终点
int next;//下一条边的存储下标(默认0)
int w;//权值
}e[200005<<1];//无向图边数*2
int n,m,ans,cnt,tot,head[5005],now=1,dis[5005];
bool visit[5005];
inline void add(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
inline void prim()
{
for(int i=2;i<=n;i++)dis[i]=INF;
for(int i=head[1];i;i=e[i].next)dis[e[i].v]=min(dis[e[i].v],e[i].w);
while(++tot<n)
{
int minn=INF;
visit[now]=1;
for(int i=1;i<=n;i++)
{
if(!visit[i]&&minn>dis[i])minn=dis[i],now=i;
}
ans+=minn;
for(int i=head[now];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]>e[i].w&&!visit[v])dis[v]=e[i].w;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1,u,v,w;i<=m;i++)
{
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
prim();
cout<<ans;
}- 优先队列（堆优化）
堆，又称优先队列，可自动返回队列里的极端值。
头文件：queue（#include<bits/stdc++.h>)
还需要using namespace std;
返回值：q.top()
出队：q.pop()
入队：q.push(something)
队列个数：q.size()
判断队列空：q.empty()
大根堆 priority_queue<int>q;
此时q.top()返回的是队列里的最大值
小根堆 priority_queue<int,vector<int>,greater<int> >q;
此时q.top()返回的是队列里的最小值
和之前prim算法大体相同，只是采用pair<int,int>这种数据结构
如何取值？？
第一个值： q.top().first
第二个值: q.top().second
排序方式，根据第一个值来排，所以要把dis放在第一个，下标放在第二个
入堆：q.push(make_pair(第一个值，第二个值));
第一个值表示dis[i],当前点到第i个点距离，第二个值则为i
具体区别可以和上面的最朴素prim算法对比，其实就差一个堆的变化
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int n,m,ans,dis[5005],w[5005][5005];
bool b[5005];
priority_queue< pair<int ,int>, vector <pair<int ,int > > ,greater<pair<int,int > > >q;
void prim()
{
for(int i=2;i<=n;i++)dis[i]=INF;
dis[1]=0,q.push(make_pair(0,1));
while(q.size())
{
int f=q.top().first, k=q.top().second;
q.pop();
if(b[k])continue;
b[k]=true;
ans+=f;
for(int i=1;i<=n;i++)
{
if(!b[i]&&dis[i]>w[k][i])dis[i]=w[k][i],q.push(make_pair(dis[i],i));
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j)w[i][j]=0;
else w[i][j]=w[j][i]=INF;
}
}
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
w[x][y]=w[y][x]=min(w[x][y],z);
}
prim();
cout<<ans;
}腾讯云开发者
