Cara menggunakan algoritma Kruskal dalam C++

Cara menggunakan algoritma Kruskal dalam C++

Algoritma Kruskal ialah algoritma tamak yang biasa digunakan untuk menyelesaikan masalah pokok rentang minimum. Dalam pengaturcaraan dalam C++, kita boleh memahami dan menggunakan algoritma Kruskal melalui contoh kod mudah.

Idea asas algoritma Kruskal adalah untuk terus memilih tepi dengan pemberat tepi terkecil yang tidak membentuk gelung sehingga semua bucu dimasukkan ke dalam pokok rentang. Di bawah ini kita akan memperkenalkan langkah demi langkah cara menggunakan C++ untuk melaksanakan algoritma Kruskal.

Langkah Pertama: Penyediaan Data
Pertama, kita perlu menyediakan struktur data graf untuk mewakili masalah. Dalam C++, graf boleh diwakili menggunakan matriks bersebelahan atau senarai bersebelahan. Di sini kami memilih untuk menggunakan senarai bersebelahan untuk mewakili graf tidak terarah.

Senarai bersebelahan boleh dilaksanakan menggunakan gabungan vektor dan senarai terpaut. Kami mentakrifkan dua struktur untuk mewakili bucu dan tepi graf.

// 图的顶点结构体
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;
    // ...
};

Langkah 2: Laksanakan algoritma Kruskal
Selepas menyediakan struktur data graf, kita boleh mula melaksanakan algoritma Kruskal. Mula-mula, kita perlu mengisih tepi graf daripada kecil kepada berat yang besar. Kemudian, kami menggunakan Union-Find untuk menentukan sama ada tepi yang dipilih akan membentuk kitaran. Akhir sekali, kami menambah tepi yang dipilih pada pokok rentang minimum.

Berikut ialah kod pelaksanaan khusus algoritma 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;
}

Langkah 3: Kod ujian
Tulis fungsi ujian, buat graf dan panggil algoritma Kruskal, output Pokok rentang minimum:

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;
}

Di atas ialah contoh mudah menggunakan C++ untuk melaksanakan algoritma Kruskal. Melalui contoh ini, anda boleh lebih memahami dan menggunakan algoritma Kruskal untuk menyelesaikan masalah pokok rentang minimum.

Atas ialah kandungan terperinci Cara menggunakan algoritma Kruskal dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!