C++ で最小スパニング ツリー アルゴリズムを使用する方法

C で最小スパニング ツリー アルゴリズムを使用する方法

最小スパニング ツリー (最小スパニング ツリー、MST) は、グラフ理論の重要な概念です。無向接続グラフのすべての頂点のエッジのサブセットであり、これらのエッジの重みの合計が最小になります。プリムのアルゴリズムやクラスカルのアルゴリズムなど、最小スパニング ツリーを解くために使用できるアルゴリズムは数多くあります。この記事では、C を使用して Prim のアルゴリズムと Kruskal のアルゴリズムを実装する方法と、具体的なコード例を紹介します。

Prim のアルゴリズムは貪欲なアルゴリズムで、グラフの頂点から開始し、現在の最小全域木に接続されている最小の重みを持つエッジを徐々に選択し、そのエッジを最小全域木に追加します。以下は、Prim のアルゴリズムの C コード例です:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 1e9;

int prim(vector<vector<pair<int, int>>>& graph) {
    int n = graph.size(); // 图的顶点数
    vector<bool> visited(n, false); // 标记顶点是否已访问
    vector<int> dist(n, INF); // 记录顶点到最小生成树的最短距离
    int minCost = 0; // 最小生成树的总权值

    // 从第一个顶点开始构建最小生成树
    dist[0] = 0;

    // 使用优先队列保存当前距离最小的顶点和权值
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, 0));

    while (!pq.empty()) {
        int u = pq.top().second; // 当前距离最小的顶点
        pq.pop();

        // 如果顶点已访问过，跳过
        if (visited[u]) {
            continue;
        }

        visited[u] = true; // 标记顶点为已访问
        minCost += dist[u]; // 加入顶点到最小生成树的权值

        // 对于顶点u的所有邻接顶点v
        for (auto& edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;

            // 如果顶点v未访问过，并且到顶点v的距离更小
            if (!visited[v] && weight < dist[v]) {
                dist[v] = weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    return minCost;
}

int main() {
    int n, m; // 顶点数和边数
    cin >> n >> m;
    vector<vector<pair<int, int>>> graph(n);

    // 读取边的信息
    for (int i = 0; i < m; ++i) {
        int u, v, w; // 边的两个顶点及其权值
        cin >> u >> v >> w;
        --u; --v; // 顶点从0开始编号
        graph[u].push_back(make_pair(v, w));
        graph[v].push_back(make_pair(u, w));
    }

    int minCost = prim(graph);
    cout << "最小生成树的权值之和为：" << minCost << endl;

    return 0;
}

Kruskal のアルゴリズムは、エッジベースの貪欲アルゴリズムです。グラフのすべてのエッジから最小の重みを持つエッジを選択し、そのエッジがグラフを形成するかどうかを決定します。サイクルです。サイクルが形成されない場合は、最小スパニング ツリーにエッジを追加します。以下は、Kruskal のアルゴリズムの C コード例です。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
    int u, v, weight; // 边的两个顶点及其权值
    Edge(int u, int v, int weight) : u(u), v(v), weight(weight) {}
};

const int MAXN = 100; // 最大顶点数
int parent[MAXN]; // 并查集数组

bool compare(Edge a, Edge b) {
    return a.weight < b.weight;
}

int findParent(int x) {
    if (parent[x] == x) {
        return x;
    }
    return parent[x] = findParent(parent[x]);
}

void unionSet(int x, int y) {
    int xParent = findParent(x);
    int yParent = findParent(y);
    if (xParent != yParent) {
        parent[yParent] = xParent;
    }
}

int kruskal(vector<Edge>& edges, int n) {
    sort(edges.begin(), edges.end(), compare);
    int minCost = 0; // 最小生成树的总权值

    for (int i = 0; i < n; ++i) {
        parent[i] = i; // 初始化并查集数组
    }

    for (auto& edge : edges) {
        int u = edge.u;
        int v = edge.v;
        int weight = edge.weight;

        // 如果顶点u和顶点v不属于同一个连通分量，则将该边加入到最小生成树中
        if (findParent(u) != findParent(v)) {
            unionSet(u, v);
            minCost += weight;
        }
    }

    return minCost;
}

int main() {
    int n, m; // 顶点数和边数
    cin >> n >> m;
    vector<Edge> edges;

    // 读取边的信息
    for (int i = 0; i < m; ++i) {
        int u, v, w; // 边的两个顶点及其权值
        cin >> u >> v >> w;
        edges.push_back(Edge(u, v, w));
    }

    int minCost = kruskal(edges, n);
    cout << "最小生成树的权值之和为：" << minCost << endl;

    return 0;
}

上記のコード例を通じて、Prim のアルゴリズムと Kruskal のアルゴリズムを使用して、C の最小スパニング ツリー問題を解決できます。実際のアプリケーションでは、特定の状況に応じて問題を解決するために適切なアルゴリズムを選択できます。これらのアルゴリズムの時間計算量はそれぞれ O(ElogV) と O(ElogE) です。ここで、V は頂点の数、E はエッジの数です。したがって、大規模なグラフを処理する場合にも、より良い結果を達成できます。

以上がC++ で最小スパニング ツリー アルゴリズムを使用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。