真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯(lián)網(wǎng)站制作重慶分公司

Prim算法-最小生成樹-創(chuàng)新互聯(lián)

最小生成樹是指一個有 n 個結(jié)點的連通圖的生成樹是原圖的極小連通子圖,且包含原圖中的所有 n 個結(jié)點,并且有保持圖連通的最少的邊。

創(chuàng)新互聯(lián)堅持“要么做到,要么別承諾”的工作理念,服務(wù)領(lǐng)域包括:成都網(wǎng)站設(shè)計、成都網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù),滿足客戶于互聯(lián)網(wǎng)時代的浦江網(wǎng)站設(shè)計、移動媒體設(shè)計的需求,幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴!

Prim算法:圖論中的一種算法,可在加權(quán)連通圖里搜索最小生成樹。意即由此算法搜索到的邊子集所構(gòu)成的樹中,不但包括了連通圖里的所有頂點(英語:Vertex (graph theory)),且其所有邊的權(quán)值之和亦為最小。該算法于1930年由捷克數(shù)學(xué)家沃伊捷赫·亞爾尼克(英語:Vojtěch Jarník)發(fā)現(xiàn);并在1957年由美國計算機(jī)科學(xué)家羅伯特·普里姆(英語:Robert C. Prim)獨立發(fā)現(xiàn);1959年,艾茲格·迪科斯徹再次發(fā)現(xiàn)了該算法。

思路:將結(jié)點分為標(biāo)記點和未標(biāo)記點,任取一個初始點作為標(biāo)記點,依次從未標(biāo)記點中找到里標(biāo)記點最短的一條路徑,并將該未標(biāo)記點納入標(biāo)記點內(nèi),依次重復(fù)執(zhí)行,直至所有點均為標(biāo)記點。

分析:

1、以0作為初始點,記為第一個標(biāo)記點。從未標(biāo)記點中尋找離0最近的一點1,將1納入標(biāo)記點。

2、再以0、1位對象,尋找離0或1最近的未標(biāo)記點2,將2納入標(biāo)記點。

3、同理,再以0、1、2為對象,尋找到未標(biāo)記點4。

4、依次類推,得到5。

5、最后一點3。

代碼實現(xiàn)(C語言):

#include#include#define N 10000


typedef struct Ver {
    char id;
    struct Ver *father;
    int minLength;
    int flag;//1 標(biāo)記,0未標(biāo)記
} Ver,*Vertex;

//初始化結(jié)構(gòu)體指針數(shù)組
void InitialVertex(Vertex vertex[]) {
    //讓0作為初始點
    vertex[0]=(Vertex)malloc(sizeof(Ver));
    vertex[0]->id='0';
    vertex[0]->father=NULL;
    vertex[0]->minLength=0;//無所謂
    vertex[0]->flag=1;
    for(int i=1; i<6; i++) {
        vertex[i]=(Vertex)malloc(sizeof(Ver));
        vertex[i]->id=i+'0';
        vertex[i]->minLength=N;
        vertex[i]->flag=0;
    }
    return;
}

//尋找李標(biāo)記點最短的未標(biāo)記點
int FindVer(Vertex vertex[],int matrix[][6]) {
    int M=10000;
    int order;//接收未標(biāo)記點下標(biāo)
    //遍歷未標(biāo)記點
    for(int i=0; i<6; i++) {
        if(vertex[i]->flag==0) {
            //遍歷標(biāo)記點
            for(int j=0; j<6; j++) {
                if(vertex[j]->flag!=0) {
                    int all_p=matrix[i][j];
                    //尋找最短路徑
                    if(all_pfather=vertex[j];
                        vertex[i]->minLength=all_p;
                        order=i;
                        M=all_p;
                    }
                }
            }
        }
    }
    return order;
}

//建立最小生成樹
void BuildMinTree(Vertex vertex[],int matrix[][6]) {
    //一共要尋找5次
    for(int i=0; i<5; i++) {
        int order=FindVer(vertex,matrix);//接受未標(biāo)記點
        vertex[order]->flag=1;//將未標(biāo)記點轉(zhuǎn)化為標(biāo)記點
        printf("第%d次,選擇的結(jié)點為%c,路徑長度為%d,連接關(guān)系為(%c,%c)\n",i+1,vertex[order]->id,vertex[order]->minLength,vertex[order]->id,vertex[order]->father->id);
    }
}

int main() {
    int matrix[6][6]= {
        { N, 3, 5, N, N, N },
        { 3, N, 2, 7, 4, N },
        { 5, 2, N, N, 3, N },
        { N, 7, N, N, N, 2 },
        { N, 4, 3, N, N, 1 },
        { N, N, N, 2, 1, N }
    };
    Vertex vertex[6];
    InitialVertex(vertex);
    BuildMinTree(vertex,matrix);
    return 0;
}

代碼實現(xiàn)(Java):

import java.util.ArrayList;
import java.util.List;

public class Prim {

    final static int N = 10000;
    static int[][] matrix = new int[6][6];

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        matrix[0] = new int[] { N, 3, 5, N, N, N };
        matrix[1] = new int[] { 3, N, 2, 7, 4, N };
        matrix[2] = new int[] { 5, 2, N, N, 3, N };
        matrix[3] = new int[] { N, 7, N, N, N, 2 };
        matrix[4] = new int[] { N, 4, 3, N, N, 1 };
        matrix[5] = new int[] { N, N, N, 2, 1, N };
        // 建立標(biāo)記點集合
        Listmarked = new ArrayList();
        // 默認(rèn)使0作為初始點
        marked.add(new Vertexs(0, null, 0));
        // 建立未標(biāo)記點集合
        ListunMarked = new ArrayList();
        // 將其他結(jié)點作為未標(biāo)記點添加到集合中
        for (int i = 1; i<= 5; i++) {
            unMarked.add(new Vertexs(i, null, N));
        }
        int count=1;
        
        //將未標(biāo)記點集合中的點轉(zhuǎn)移到已標(biāo)記點集合
        while (!unMarked.isEmpty()) {        
            Vertexs ver = findVer(marked, unMarked);
            marked.add(ver);
            unMarked.remove(ver);
            System.out.println("第"+(count++)+"次,選擇的結(jié)點為"+ver.id+",路徑長度為"+ver.minLength+",連接關(guān)系為("+ver.father.id+","+ver.id+")");
        }    
        
    }

    public static Vertexs findVer(Listmarked, ListunMarked) {
        int M = 10000;
        Vertexs v = null;
        for (Vertexs ve : unMarked) {
            for (Vertexs vr : marked) {
                int all_p = matrix[vr.id][ve.id];
                if (all_p< M) {
                    ve.minLength = all_p;
                    ve.father = vr;
                    M=all_p;
                    v=ve;
                }
            }
        }
        return v;
    }

}

class Vertexs {
    public int id;
    public Vertexs father;
    public int minLength = 10000;

    public Vertexs(int id, Vertexs father, int minLength) {
        this.id = id;
        this.father = father;
        this.minLength = minLength;
    }
}

一言:

不是每一場雨都有彩虹,但是晴天總會到來。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商?創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源,準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性,企業(yè)級服務(wù)器適合批量采購,新人活動首月15元起,快前往官網(wǎng)查看詳情吧


分享題目:Prim算法-最小生成樹-創(chuàng)新互聯(lián)
本文鏈接:http://weahome.cn/article/ddpsjs.html

其他資訊

在線咨詢

微信咨詢

電話咨詢

028-86922220(工作日)

18980820575(7×24)

提交需求

返回頂部