Java怎么實(shí)現(xiàn)最小生成樹MST

本篇內(nèi)容介紹了“Java怎么實(shí)現(xiàn)最小生成樹MST”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

簡(jiǎn)單講解

圖的定義時(shí) 我們規(guī)定一個(gè)連通圖的生成樹是一個(gè)極小連通子圖 含有N個(gè)頂點(diǎn)N-1個(gè)邊   我們把圖中帶權(quán)的邊  最小代價(jià)生成的樹成為最小生成樹。   

普里姆(Prim)算法  prim算法適合稠密圖，其時(shí)間復(fù)雜度為O(n^2)，其時(shí)間復(fù)雜度與邊得數(shù)目無關(guān)以頂點(diǎn)找頂點(diǎn) 考慮權(quán)值 

            存儲(chǔ)方式為鄰接矩陣

基本思想：假設(shè)G＝(V，E)是連通的，TE是G上最小生成樹中邊的集合。算法從U＝{u0}（u0∈V）、TE＝{}開始。重復(fù)執(zhí)行下列操作：

   在所有u∈U，v∈V－U的邊(u，v)∈E中找一條權(quán)值最小的邊(u0,v0)并入集合TE中，同時(shí)v0并入U(xiǎn)，直到V＝U為止。

   此時(shí)，TE中必有n-1條邊，T=(V，TE)為G的最小生成樹。

   Prim算法的核心:始終保持TE中的邊集構(gòu)成一棵生成樹。

注意：prim算法適合稠密圖，其時(shí)間復(fù)雜度為O(n^2)，其時(shí)間復(fù)雜度與邊得數(shù)目無關(guān)，

為了更好理解我們?cè)谶@里舉一個(gè)例子，示例如下：

（1）圖中有6個(gè)頂點(diǎn)v1-v6，每條邊的邊權(quán)值都在圖上；在進(jìn)行prim算法時(shí)，我先隨意選擇一個(gè)頂點(diǎn)作為起始點(diǎn)，當(dāng)然我們一般選擇v1作為起始點(diǎn)，好，現(xiàn)在我們?cè)O(shè)U集合為當(dāng)前所找到最小生成樹里面的頂點(diǎn)，TE集合為所找到的邊，現(xiàn)在狀態(tài)如下：

U={v1}； TE={}；

（2）現(xiàn)在查找一個(gè)頂點(diǎn)在U集合中，另一個(gè)頂點(diǎn)在V-U集合中的最小權(quán)值，如下圖，在紅線相交的線上找最小值。

通過圖中我們可以看到邊v1-v3的權(quán)值最小為1，那么將v3加入到U集合，（v1，v3）加入到TE，狀態(tài)如下：

U={v1，v3}； TE={（v1，v3）}；

（3）繼續(xù)尋找，現(xiàn)在狀態(tài)為U={v1，v3}； TE={（v1，v3）}；在與紅線相交的邊上查找最小值。

我們可以找到最小的權(quán)值為（v3，v6）=4，那么我們將v6加入到U集合，并將最小邊加入到TE集合，那么加入后狀態(tài)如下：

U={v1，v3，v6}； TE={（v1，v3），（v3，v6）}； 如此循環(huán)一下直到找到所有頂點(diǎn)為止。

（4）下圖像我們展示了全部的查找過程：

#include<iostream>
#include<fstream>
using  namespace std;
#define MAX 100
#define MAXCOST 65535
int graph[MAX][MAX];
int Prim(int graph[][MAX], int m)//m 是點(diǎn)數(shù)
{
    int lowcost[m];
    int mst[m];
    int i, j, min, k, sum = 0;
    mst[1] = 0;
    lowcost[1]=0;
    for (i = 2; i <= m; i++)
    {
        lowcost[i] = graph[1][i];
        mst[i] = 1;
    }
    for (i = 2; i <= m; i++)
    {
        min = MAXCOST;
        k = 0;
        for (j = 2; j <= m; j++)
        {
            if (lowcost[j] < min && lowcost[j] != 0)
            {
                min = lowcost[j];
                k = j;//找到最小值下標(biāo)
            }
        }
        cout << "V" << mst[k] << "-V" << k << "=" << min << endl;
        sum += min;
        lowcost[k] = 0;//到達(dá)k的距離為0 說明這個(gè)頂點(diǎn)完成了任務(wù)
        for (j = 2; j <= m; j++) // 更新lowcost 數(shù)組
        {
            if (lowcost[j] != 0 && graph[k][j] < lowcost[j])
            {
                lowcost[j] = graph[k][j];/本來到達(dá)不了 由于k的引入 可以到達(dá)了
                mst[j] = k; //這是不能總是從V1開始去別的點(diǎn) 把 現(xiàn)在能找到的近距離類似  mst[k]
            }
        }
    }
    return sum;
}
int main()
{
    int i, j, k, m, n;
    int cost;
    cout<<"please input V and E:";
    cin >> m >> n;//m=頂點(diǎn)的個(gè)數(shù)，n=邊的個(gè)數(shù)
    //初始化圖G
    for (i = 1; i <= m; i++)
    {
        for (j = 1; j <= m; j++)
        {
            graph[i][j] = MAXCOST;
        }
    }
    //構(gòu)建圖G
    cout<<"please intput i j and cost:"<<endl;
    for (k = 1; k <= n; k++)
    {
        cin >> i >> j >> cost;
        graph[i][j] = cost;
        graph[j][i] = cost;
    }
    //求解最小生成樹
    cost = Prim(graph, m);
    //輸出最小權(quán)值和
    cout << "最小權(quán)值和=" << cost << endl;
    return 0;
}

測(cè)試數(shù)據(jù) V E

6 10

1 2 6 

1 3 1 

1 4 5 

2 3 5 

2 5 3 

3 4 5 

3 5 6 

3 6 4 

4 6 2 

5 6 6

結(jié)果

V1-V3=1 

V3-V6=4 

V6-V4=2 

V3-V2=5 

V2-V5=3 

最小權(quán)值和=15 

請(qǐng)按任意鍵繼續(xù). . .

“Java怎么實(shí)現(xiàn)最小生成樹MST”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！