图论（4）

DuskDawn · 2022-11-13 20:02:06 · 个人记录

废话不多说。

上次答案

因为如果图中有环，则环上结点的入度不可能为 0。
可以用并查集判环。遇到一个点就把它和它的出边指向的点都合并，如果根节点相同，说明出现环。当然也可以遍历图判环，这里不再赘述。
假设并查集中有 n 个元素，则其时间复杂度如下：

无优化：平均 O(\log n)，最坏 O(n)。

路径压缩：平均 O(\alpha(n))，最坏 O(\log n)。

按秩合并：平均 O(\log n)，最坏 O(\log n)。

路径压缩+按秩合并：平均 O(\alpha(n))，最坏 O(\alpha(n))。

这里 \alpha 表示反阿克曼函数，在宇宙可观测的 n 内（例如宇宙中包含的粒子总数），\alpha(n) 不会超过 5。~~好恐怖的函数~~

最小生成树

生成树

一个连通图的生成树生成树（Spannning Tree）是一个极小的连通子图，它包含图中所有的顶点，但只有构成一棵树的 |V|-1 条边。例如：

性质

一个连通图中可以有多个生成树。
移除生成树中的任意一条边都会导致树的不连通，多加一条边就会构成环。
对于包含 n 个节点的连通图，生成树包含 n 个顶点与 n-1 条边。

最小生成树

一个带权图的最小生成树就是原图中边的权值之和最小的生成树。例如：

Prim 算法

Prim（普利姆）算法是一种求最小生成树的算法。

算法步骤

其算法本质是一种贪心。

选择一个起点，把它加入最小生成树。
定义一个 dis 数组存储最小生成树中的结点到其他结点的最小边权。扫描周围与起点相连的边，比较 dis 的最小值寻找下一个结点。
将最后找到的结点加入最小生成树，把它作为下一个起点，并且更新 dis 内的元素。重复 2、3 直到所有节点都加入最小生成树。

其算法本质是一种贪心。每次寻找与生成树内结点相连的权值最小的边，并将边的终点加入最小生成树。

可能有点抽象，结合着代码看吧。

Code:

#include <iostream>
using namespace std;
int n,m,a[11][11],ans;
bool vis[11];
int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (i==j)
            {
                a[i][j]=0;
            }else
            {
                a[i][j]=0x7fffffff;//不同于最短路，这里可以设大一些，判断的时候没有运算不会溢出。
            }
    for (int i=1;i<=m;i++)
    {
        int p,q,t;
        cin>>p>>q>>t;
        a[p][q]=a[q][p]=t;
    }
    int dis[11]={};
    for (int i=1;i<=n;i++)
    {
        dis[i]=a[1][i];//更新与起点相连的点的 dis 值
    }
    vis[1]=1;//起点加入最小生成树
    for (int i=1;i<n;i++)
    {
        int minn=0x7ffffff,minx;
        for (int j=1;j<=n;j++)//寻找下一个结点
        {
            if (dis[j]<minn&&!vis[j])
            {
                minn=dis[j];
                minx=j;
            }
        }
        vis[minx]=1;
        ans+=minn;//加入最小生成树
        for (int j=1;j<=n;j++)
        {
            if (a[minx][j]<dis[j]&&!vis[j])//更新 dis 值
            {
                dis[j]=a[minx][j];
            }
        }
    }
    cout<<ans;
    return 0;
}

有没有觉得和 Dijkstra 算法有点相似呢？不过这里的 dis 数组表示的是其他结点与最小生成树中的结点的最短距离，而 Dijkstra 算法中的 dis 数组表示的是结点与起点的最短距离，不要混淆了。

该算法的时间复杂度是 O(|V|^2)，在 |V| 较大时容易超时，我们看看有没有可以优化的地方。类似 Dijkstra 算法，其中“找权值最小的边”这一部分可以用小根堆优化，时间复杂度可以提升至 O((|V|+|E|)\log|E|)。

Code:

#include <iostream>
#include <queue>
using namespace std;
struct Edge{
    int p,w;
    bool operator<(const Edge &b)const{
        return w>b.w;
    }
};
int n,m,a[11][11],ans;
bool vis[11];
priority_queue<Edge> q;
int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (i==j)
            {
                a[i][j]=0;
            }else
            {
                a[i][j]=0x7fffffff;
            }
    for (int i=1;i<=m;i++)
    {
        int p,q,t;
        cin>>p>>q>>t;
        a[p][q]=a[q][p]=t;
    }
    int dis[11]={};
    for (int i=1;i<=n;i++)
    {
        dis[i]=a[1][i];
        q.push({i,dis[i]});
    }
    while (!q.empty())
    {
        Edge now=q.top();
        q.pop();
        if (vis[now.p]){
            continue;
        }
        vis[now.p]=1;
        ans+=now.w;
        for (int j=1;j<=n;j++)
        {
            if (a[now.p][j]<dis[j]&&!vis[j])
            {
                dis[j]=a[now.p][j];
                q.push({j,dis[j]});
            }
        }
    }
    cout<<ans;
    return 0;
}

Kruskal 算法

Kruskal（克鲁斯卡尔）算法是一种利用并查集解决最小生成树的算法。我们把无向图中相互连通的点称为处于同一个连通块中，Kruskal 算法将每个连通块看成一个集合。

算法步骤

将边从小到大排序，并认为每个点是相互孤立的。
按顺序枚举每一条边，如果当前变得两个点属于同一个集合就跳过，否则合并它们，并将这条边加入最小生成树，直到选出 |V|-1 条边为止。

该算法同样运用贪心，每次选择的都是当前未选边中最小的一条。

Code:

#include <iostream>
#include <algorithm>
using namespace std;
struct Edge{
    int s,t,w;
    bool operator<(const Edge &b)const{
        return w<b.w;
    }
}e[1001];
int n,m,ans,k;
int fa[1001];
void init(){
    for (int i=1;i<=n;i++){
        fa[i]=i;
    }
}
inline int find(int u){
    return fa[u]==u?u:(fa[u]=find(fa[u]));
}
inline void merge(int u,int v){
    fa[find(u)]=find(v);
}
int main(){
    cin>>n>>m;
    init();
    for (int i=1;i<=m;i++){
        cin>>e[i].s>>e[i].t>>e[i].w;
    }
    sort(e+1,e+m+1);
    for (int i=1;i<=m;i++){
        if (k==n-1){
            cout<<ans;
            return 0;
        }
        if (find(e[i].s)==find(e[i].t)){
            continue;
        }
        merge(e[i].s,e[i].t);
        ans+=e[i].w;
        k++;
    }
}

该算法的时间复杂度是 O(|E|\log|E|+|E|\alpha(n))。

练习

请思考两种用于求最小生成树的算法分别适用于哪种情况。

答案下节公布。比较简单，所以没有太多练习。