图论基础

· · 算法·理论

图论

小结

存图（2023.6.2

主要有三种方式

注意根据题目要求设置结构体中的变量

数组大小MAXM

也注意这两句的先后

e[cnt].nxt=head[u];
head[u]=cnt;

数组大小MAXM

注意题目的数据范围，一旦n>5000就基本会爆内存，所以大多数情况下都用邻接表存图

数组大小MAXN*MAXN

并查集（2023.6.2

(虽然这好像不是图论的内容，但对于MST相关问题比较有 用)

大家应该都很熟悉，主要注意一些优化

find函数压缩路径

每次搜索时压缩遍历路径，下一次查询时就可以用更短的时间找到所属的集合

int fa[MAXN];
void Create()
{
    for(int i=1;i<=n;i++){fa[i]=i;}
}
int find(int x)
{
    if(fa[x]!=x) x=fa[x]=find(fa[x]);
    return x;
}

merge函数考虑深度

在合并集合时，考虑树结构的深度，矮接高，这样在合并之后深度会尽量小，查询时也就越快

int fa[MAXN];
int d[MAXN];
void Create()
{
    for(int i=1;i<=n;i++){fa[i]=i;d[i]=1;}
}
int find(int x)
{
    if(fa[x]!=x) x=fa[x]=find(fa[x]);
    return x;
}
void merge(int x,int y)
{
    int ux,uy;
    ux=find(x);uy=find(y);
    if(d[ux]>d[uy]){fa[y]=x;d[y]=d[x];}
    if(d[ux]==d[uy]){fa[x]=y;d[y]++;d[x]=d[y];}
    if(d[ux]<d[uy]){fa[x]=y;d[x]=d[y];}
    return;
}

更多见发的资料

最小生成树MST（2023.6.2

个人主要用kruskal算法

这种算法用结构体数组存边，主要思路运用了贪心的思想，并查集，快排。

通过排序来保证贪心，每条加入的边最小，即每条在树里和的边最小

通过并查集来判断任意两点是否联通，即是否在已经树中

由于树的特性，所以生成n-1条边后就已经生成了将所有点联通的最小生成树

//存图 
struct EDGE
{
    int u,v,w;
}edge[MAXM];
//并查集 
int fa[MAXN];
void Create(){for(int i=1;i<=n;i++){fa[i]=i;}}
int find(int x)
{
    if(fa[x]!=x) x=fa[x]=find(fa[x]);
    return x;
}
//cmp
bool cmp(EDGE x,EDGE y){return x.w<y.w;}
int ans=0;//生成树每条边的权值之和
void kruskal()
{
    int tot=0;
    sort(edge+1,edge+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        u=find(edge[i].u);
        v=find(edge[i].v);
        if(u==v) continue;//如果已经联通则继续枚举
        fa[u]=v;
        ans+=edge[i].t;
        if(++tot==n-1) break;//已经生成n-1条边则跳出循环
    }
    return;
}