基本思想

1. 每次從所有邊中選取權(quán)值最小的一條邊，將首尾節(jié)點(diǎn)加入集合T,剩余節(jié)點(diǎn)集合為G

2. 從剩余節(jié)點(diǎn)組成的所有邊中再選擇一條權(quán)值最小的邊，將首尾節(jié)點(diǎn)加入集合T,剩余節(jié)點(diǎn)集合為G
3. 重復(fù)2并且保證已選出的邊不構(gòu)成回路，直到G中沒(méi)有節(jié)點(diǎn)。

和prim的區(qū)別

kruskal的計(jì)算是基于邊的，在邊比較少的情況下會(huì)比較快，邊比較多時(shí)，prim會(huì)更好。

例子為

最小生成樹(shù).jpg --圖來(lái)自慕課網(wǎng)視頻

代碼

void MyGraph::kruskalTree() {
    //1、將連接矩陣轉(zhuǎn)換為邊集合
    int n,m;
    vector<MyEdge> edge_vector = transformMatrixToEdge();
    //用于判斷便于邊是否形成環(huán)路，下標(biāo)為邊的起始點(diǎn)，值為邊的結(jié)束點(diǎn)
    int parent[this->num];

    for(int i = 0;i<this->num;i++){
        parent[i] = 0;
    }

    for (int j = 0; j < edge_vector.size(); ++j) {
        n = this->Find(parent,edge_vector[j].start);
        m = this->Find(parent,edge_vector[j].end);
        if(n!=m){
            parent[n] = m;
            cout<<this->node_array[edge_vector[j].start].data<<"--->"<<this->node_array[edge_vector[j].end].data<<" value: "<<edge_vector[j].value<<endl;
        }
    }
}

vector<MyEdge> MyGraph::transformMatrixToEdge() {
    vector<MyEdge> edges;
    for (int i = 0; i < this->num; ++i) {
        for (int j = i+1; j < this->num; ++j) {
            if(this->array[i*this->num+j]!=this->max_value) {
                MyEdge edge = MyEdge(i,j,this->array[i*this->num+j]);
                edges.push_back(edge);
            }
        }
    }
    for (int k = 0; k < edges.size(); ++k) {
        for (int i = k+1; i < edges.size(); ++i) {
            if(edges[k].value>edges[i].value){
                MyEdge edge = MyEdge(edges[k].start,edges[k].end,edges[k].value);
                edges[k] = edges[i];
                edges[i] = edge;
            }
        }
    }
    return edges;
}

int MyGraph::Find(int *parent, int f) {
    while(parent[f]>0){
        f = parent[f];
    }
    return f;
}

運(yùn)行結(jié)果

kruskal結(jié)果.png