prim(普里姆)算法（c++，有图，邻接矩阵)

prim算法


- [1 ]

在上图中我们事先选取v1作为起始点，将v1放入集合T中。选取集合T中的v1（按放入顺序），由图，它的邻接边中选取权值最小的的一条也就是（v1-->v2）将v2放入集合T中，并将v1,v2标记使以后的节点不能以它们作为终点。

- [ 2] 现在集合中有v1，v2。找到v1,v2的邻接边中权值最小的边也就是（v1-->v4）将v4放入集合T中，并将v4标记。

- [3 ] 按顺序遍历集合T，重复上述步骤。

- [4 ] ......

- [ 5] 最终使每个节点都在集合T中，结束操作。

过程如图所示：

1. 

2. 

3. 

4. 

5. 

代码如图所示：

（这里使用邻接矩阵储存信息）

#include"bits/stdc++.h"

using namespace std;

#define MAX 24

#define INFINITE 201201

typedef char VertexType;

typedef int EdgeType;

typedef struct{//储存头节点信息 

    VertexType vertex;

}AdjMatrix[MAX],AdjMat;

typedef struct{//储存邻接矩阵信息 

    EdgeType map[MAX][MAX];//矩阵 

    AdjMatrix adjmatrix;

    int numsVertex,numsEdge;//节点和边的数量 

}MGraph;

void Initlize(MGraph *test){//初始化 

    for(int i=0;i<test->numsVertex;i++){

        for(int j=0;j<test->numsVertex;j++){

            if(i==j){

                test->map[i][j]=0;

            }

            else{

                test->map[i][j]=INFINITE;

            }

        }

    }

}

void CreateMat(MGraph *test){//输入边的信息，创建矩阵 

    for(int i=0;i<test->numsEdge;i++){

        char x,y;

        int weight,k,z,j=0;

        cin>>x>>y;

        while(test->adjmatrix[j].vertex!=x){

            j++;

        }

        k=j,j=0;        

        while(test->adjmatrix[j].vertex!=y){

            j++;

        }

        z=j;//j和节点对应 

        cin>>weight;

        test->map[k][z]=test->map[z][k]=weight;//赋权 

    }

}

void Prim(MGraph *test,bool visited[]){//普里姆算法 

    int min; 

    int min_x,min_y;// 最小权值对应边的信息 

    int i,j;

    queue <int> flag,temp;//flag相当于集合T ,temp用来找最小权值 

    flag.push(0);//将第一个节点放入flag中 

    visited[0]=true;//将第一个节点标记 

    while(flag.size()!=test->numsVertex){//当节点全部标记后结束 

        temp=flag;//将flag的信息传给temp 

        min=INFINITE;

        while(!temp.empty()){//依次拿出temp中存储的节点 

            i=temp.front();//i相当于节点对应的行 

            for(j=0;j<test->numsVertex;j++){//j对应列 

                if(test->map[i][j]>0&&min>test->map[i][j]&&!visited[j]){//找最小权值 

                    min=test->map[i][j];

                    min_x=i;

                    min_y=j;

                }

            }

            temp.pop();

        }

        visited[min_y]=true;

        flag.push(min_y);//将终节点放入flag中 

        test->map[min_y][min_x]=INFINITE;

        test->map[min_x][min_y]=INFINITE;//将查过的边赋值为INF 

        cout<<"("<<test->adjmatrix[min_x].vertex<<","<<test->adjmatrix[min_y].vertex<<")";

    }

}

int main(){

    MGraph test;

    bool visited[MAX]={false};//初始化visited 

    cin>>test.numsVertex>>test.numsEdge;

    for(int i=0;i<test.numsVertex;i++){

        cin>>test.adjmatrix[i].vertex;//输入头节点信息 

    }

    Initlize(&test);

    CreateMat(&test);

    Prim(&test,visited);

    return 0;

}

第一次写博客，有不足请留言

>_<

date 2020/4/22 修改一处错误