C++ で Kruskal のアルゴリズムを使用する方法

C での Kruskal アルゴリズムの使用方法

Kruskal アルゴリズムは、最小スパニング ツリー問題を解決するために一般的に使用される貪欲アルゴリズムです。 C を使用したプログラミングでは、簡単なコード例を通じて Kruskal のアルゴリズムを理解し、使用することができます。

クラスカルのアルゴリズムの基本的な考え方は、エッジの重みが最小で、すべての頂点がスパニング ツリーに含まれるまでループを形成しないエッジを継続的に選択することです。以下では、C を使用して Kruskal のアルゴリズムを実装する方法を段階的に紹介します。

ステップ 1: データの準備
まず、問題を表すグラフ データ構造を準備する必要があります。 C では、隣接行列または隣接リストを使用してグラフを表現できます。ここでは、無向グラフを表すために隣接リストを使用することを選択します。

隣接リストは、ベクトルとリンク リストの組み合わせを使用して実装できます。グラフの頂点とエッジを表す 2 つの構造を定義します。

// 图的顶点结构体
struct Vertex {
    int id; // 顶点的唯一标识符
    // ...
};

// 图的边结构体
struct Edge {
    int start; // 边的起始顶点
    int end; // 边的结束顶点
    int weight; // 边的权重
    // ...
};

// 定义一个无向图的类
class Graph {
public:
    // 添加顶点和边的函数
    void addVertex(Vertex v);
    void addEdge(Edge e);
    // ...
private:
    // 保存顶点和边的数据结构
    vector<Vertex> vertices;
    list<Edge> edges;
    // ...
};

ステップ 2: クラスカル アルゴリズムの実装
グラフのデータ構造を準備したら、クラスカル アルゴリズムの実装を開始できます。まず、グラフのエッジを重みの小さいものから大きいものに並べ替える必要があります。次に、Union-Find を使用して、選択したエッジがサイクルを形成するかどうかを判断します。最後に、選択したエッジを最小スパニング ツリーに追加します。

以下は、Kruskal アルゴリズムの具体的な実装コードです:

// 定义并查集结构体
struct UnionFind {
    vector<int> parent;
    // ...
};

// 初始化并查集
void initUnionFind(UnionFind& uf, int n) {
    uf.parent.resize(n);
    // ...
}

// 查找根节点
int findRoot(UnionFind& uf, int x) {
    if (uf.parent[x] != x) {
        uf.parent[x] = findRoot(uf, uf.parent[x]);
    }
    return uf.parent[x];
}

// 合并两个集合
void mergeSets(UnionFind& uf, int x, int y) {
    int rootX = findRoot(uf, x);
    int rootY = findRoot(uf, y);
    if (rootX != rootY) {
        uf.parent[rootX] = rootY;
    }
}

// Kruskal算法主函数
list<Edge> kruskal(Graph& graph) {
    list<Edge> minSpanningTree;
    // 将图的边按照权重从小到大排序
    graph.edges.sort([](const Edge& e1, const Edge& e2) {
        return e1.weight < e2.weight;
    });

    int numVertices = graph.vertices.size();
    UnionFind uf;
    initUnionFind(uf, numVertices);

    for (const Edge& edge : graph.edges) {
        int startRoot = findRoot(uf, edge.start);
        int endRoot = findRoot(uf, edge.end);
        // 如果两个顶点不在同一个集合中，则添加该边到最小生成树中
        if (startRoot != endRoot) {
            minSpanningTree.push_back(edge);
            mergeSets(uf, startRoot, endRoot);
        }
    }
    
    return minSpanningTree;
}

ステップ 3: テスト コード
テスト関数を作成し、グラフを作成し、Kruskal アルゴリズムを呼び出して最小スパニング ツリーを出力します。 :

void testKruskal() {
    Graph graph;
    // 添加顶点和边
    // ...
    
    list<Edge> minSpanningTree = kruskal(graph);
    // 输出最小生成树
    for (const Edge& edge : minSpanningTree) {
        cout << edge.start << " -> " << edge.end << ", weight: " << edge.weight << endl;
    }
}

int main() {
    testKruskal();
    return 0;
}

上記は、C を使用して Kruskal のアルゴリズムを実装する簡単な例です。この例を通じて、クラスカルのアルゴリズムをよりよく理解し、使用して最小スパニング ツリー問題を解決することができます。

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