Prim算法-最小生成树-创新互联

最小生成树是指一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。

Prim算法：图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点(英语:Vertex (graph theory))，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克(英语:Vojtěch Jarník)发现;并在1957年由美国计算机科学家罗伯特·普里姆(英语:Robert C. Prim)独立发现;1959年，艾兹格·迪科斯彻再次发现了该算法。

思路：将结点分为标记点和未标记点，任取一个初始点作为标记点，依次从未标记点中找到里标记点最短的一条路径，并将该未标记点纳入标记点内，依次重复执行，直至所有点均为标记点。

分析：

1、以0作为初始点，记为第一个标记点。从未标记点中寻找离0最近的一点1，将1纳入标记点。

2、再以0、1位对象，寻找离0或1最近的未标记点2，将2纳入标记点。

3、同理，再以0、1、2为对象，寻找到未标记点4。

4、依次类推，得到5。

5、最后一点3。

代码实现(C语言)：

#include#include#define N 10000


typedef struct Ver {
    char id;
    struct Ver *father;
    int minLength;
    int flag;//1 标记，0未标记
} Ver,*Vertex;

//初始化结构体指针数组
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;
}

//寻找李标记点最短的未标记点
int FindVer(Vertex vertex[],int matrix[][6]) {
    int M=10000;
    int order;//接收未标记点下标
    //遍历未标记点
    for(int i=0; i<6; i++) {
        if(vertex[i]->flag==0) {
            //遍历标记点
            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);//接受未标记点
        vertex[order]->flag=1;//将未标记点转化为标记点
        printf("第%d次，选择的结点为%c,路径长度为%d,连接关系为(%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;
}

代码实现(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 };
        // 建立标记点集合
        Listmarked = new ArrayList();
        // 默认使0作为初始点
        marked.add(new Vertexs(0, null, 0));
        // 建立未标记点集合
        ListunMarked = new ArrayList();
        // 将其他结点作为未标记点添加到集合中
        for (int i = 1; i<= 5; i++) {
            unMarked.add(new Vertexs(i, null, N));
        }
        int count=1;
        
        //将未标记点集合中的点转移到已标记点集合
        while (!unMarked.isEmpty()) {        
            Vertexs ver = findVer(marked, unMarked);
            marked.add(ver);
            unMarked.remove(ver);
            System.out.println("第"+(count++)+"次，选择的结点为"+ver.id+",路径长度为"+ver.minLength+",连接关系为("+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;
    }
}

一言：

不是每一场雨都有彩虹，但是晴天总会到来。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧