当前位置：首页 > article >正文

C++ 算法学习——1.9 Kruskal算法

article 2024/10/21 4:48:23

Kruskal算法是一种用于解决最小生成树（Minimum Spanning Tree）问题的贪婪算法。

Kruskal算法步骤：

初始化：将图中的所有边按照权值从小到大进行排序。
创建并查集：为每个顶点创建一个集合，用于判断两个顶点是否在同一个连通分量中。
遍历排序后的边：从权值最小的边开始遍历。
检查边的两个顶点：
- 如果这两个顶点不在同一个连通分量中，则将它们加入最小生成树中，并合并它们的连通分量。
- 如果这两个顶点已经在同一个连通分量中，则跳过这条边，以避免形成环路。
重复步骤4，直到最小生成树中有V-1条边（V为顶点数），此时最小生成树构建完成。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int src, dest, weight;
    Edge(int a,int b,int c):src(a),dest(b),weight(c){}
};

struct Graph {
    int V, E;
    vector<Edge> edges;
    Graph(int a,int b):V(a),E(b){}
};

int find(vector<int>& parent, int i) {
    while (parent[i] != i) {
        i = parent[i];
    }
    return i;
}

void Union(vector<int>& parent, int x, int y) {
    int xset = find(parent, x);
    int yset = find(parent, y);
    parent[xset] = yset;
}

void KruskalMST(Graph& graph) {
    int V = graph.V;
    vector<Edge> result;
    int e = 0, i = 0;

    sort(graph.edges.begin(), graph.edges.end(), [](const Edge& a, const Edge& b) {
        return a.weight < b.weight;
    });

    vector<int> parent(V);
    for (int v = 0; v < V; v++) {
        parent[v] = v;
    }

    while (e < V - 1 && i < graph.E) {
        Edge next_edge = graph.edges[i++];

        int x = find(parent, next_edge.src);
        int y = find(parent, next_edge.dest);

        if (x != y) {
            result.push_back(next_edge);
            Union(parent, x, y);
            e++;
        }
    }

    //cout << "Edges in the constructed MST:\n";
    for (const Edge& edge : result) {
        cout << edge.src << " -- " << edge.dest << " == " << edge.weight << endl;
    }
}

int main()
{
    int n,m;cin>>n>>m;
    Graph mygraph(n,m);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;cin>>a>>b>>c;
        Edge p(a,b,c);
        mygraph.edges.push_back(p);
    }
    return 0;
}

说明：

e < V - 1：这个条件是用来判断当前已经加入最小生成树的边数是否达到了顶点数减一，即 V - 1。在一个连通的图中，最小生成树的边数必定是顶点数减一。
i < graph.E：这个条件是用来确保遍历完所有的边。graph.E 表示图中边的总数，i 是当前处理到的边的索引。这个条件保证在所有边都遍历完之前继续尝试找到最小生成树的边。

P1. 洛谷p3366最小生成树

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int ans=0;
struct Edge {
    int src, dest, weight;
    Edge(int a,int b,int c):src(a),dest(b),weight(c){}
};

struct Graph {
    int V, E;
    vector<Edge> edges;
    Graph(int a,int b):V(a),E(b){}
};

int find(vector<int>& parent, int i) {
    while (parent[i] != i) {
        i = parent[i];
    }
    return i;
}

void Union(vector<int>& parent, int x, int y) {
    int xset = find(parent, x);
    int yset = find(parent, y);
    parent[xset] = yset;
}

void KruskalMST(Graph& graph) {
    int V = graph.V;
    vector<Edge> result;
    int e = 0, i = 0;

    sort(graph.edges.begin(), graph.edges.end(), [](const Edge& a, const Edge& b) {
        return a.weight < b.weight;
    });

    vector<int> parent(V);
    for (int v = 0; v < V; v++) {
        parent[v] = v;
    }

    while (e < V - 1 && i < graph.E) {
        Edge next_edge = graph.edges[i++];

        int x = find(parent, next_edge.src);
        int y = find(parent, next_edge.dest);

        if (x != y) {
            result.push_back(next_edge);
            Union(parent, x, y);
            e++;
            ans+=next_edge.weight;
        }
    }
    if(e!=V-1) cout<<"orz";
    else cout<<ans; 

    //cout << "Edges in the constructed MST:\n";
    //for (const Edge& edge : result) {
        //cout << edge.src << " -- " << edge.dest << " == " << edge.weight << endl;
    //}
}

int main()
{
    int n,m;cin>>n>>m;
    Graph mygraph(n,m);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;cin>>a>>b>>c;
        Edge p(a-1,b-1,c);
        mygraph.edges.push_back(p);
    }
    KruskalMST(mygraph);
    return 0;
}

P2. 洛谷p1194买礼物

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;
int ans=0;
struct Edge {
    int src, dest, weight;
    Edge(int a,int b,int c):src(a),dest(b),weight(c){}
};

struct Graph {
    int V, E;
    vector<Edge> edges;
    Graph(int a,int b=0):V(a),E(b){}
};

int find(vector<int>& parent, int i) {
    while (parent[i] != i) {
        i = parent[i];
    }
    return i;
}

void Union(vector<int>& parent, int x, int y) {
    int xset = find(parent, x);
    int yset = find(parent, y);
    parent[xset] = yset;
}

int KruskalMST(Graph& graph) {
    int V = graph.V;
    graph.E = graph.edges.size();
    vector<Edge> result;
    int e = 0, i = 0;

    sort(graph.edges.begin(), graph.edges.end(), [](const Edge& a, const Edge& b) {
        return a.weight < b.weight;
    });

    vector<int> parent(V);
    for (int v = 0; v < V; v++) {
        parent[v] = v;
    }

    while (e < V - 1 && i < graph.E) {
        Edge next_edge = graph.edges[i++];

        int x = find(parent, next_edge.src);
        int y = find(parent, next_edge.dest);

        if (x != y) {
            result.push_back(next_edge);
            Union(parent, x, y);
            e++;
            ans+=next_edge.weight;
        }
    }
    return ans;

    //cout << "Edges in the constructed MST:\n";
    //for (const Edge& edge : result) {
        //cout << edge.src << " -- " << edge.dest << " == " << edge.weight << endl;
    //}
}

int main()
{
    int n,m;cin>>n>>m;
    Graph mygraph(m);
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<m;j++)
        {
            int weight;cin>>weight;
            if(weight)
            {
                Edge p(i,j,min(n,weight));
                mygraph.edges.push_back(p);
            }
            if(!weight)
            {
                Edge p(i,j,n);
                mygraph.edges.push_back(p);
            }
        }
    }
    cout<<n+KruskalMST(mygraph);
    return 0;
}

查看全文

http://www.kler.cn/news/358252.html