最小生成树——Prim算法

prim算法简单来说就是加点法，如下图所示：

最小生成树(Prim算法)

用邻接矩阵存放整个图的信息（注意无向图的对称性），用一个整型数组on[]来存放已经加入的点，用一个结构体数组存放每个点的信息，包括与之距离最短的点another，两点的权值weigh，以及flag标记是否已被选取。
先将第一个点放入on[]数组中，每次放入的时候所有未选用的点信息都需要更新（即比较上一次最短距离和与新点之间的距离大小，然后修改weigh和another），然后从中选取weigh最小的点，输出其another与其自身，表示一条新的边，然后将该点存入on[]数组，其flag置为1，重复操作，直到点全部被选完

Code

#include<iostream>
#define MAX 0xfffffff
using namespace std;
typedef struct D {
    int weigh;//与已有点的最短距离
    int flag;
    int another;//最近距离的点
} d;
d dian[100];//存放点的信息
int ok[100];//存放已连接点
int map[100][100];
char str[100];
int n;
int change(char x) {
    for(int i=0; i<n; i++) {
        if(str[i]==x)
            return i;
    }
}
void find(int j) {
    for(int i=0; i<n; i++) {
        if(dian[i].flag ==1)
            continue;
        if(dian[i].weigh >map[i][j]) {
            dian[i].weigh =map[i][j];
            dian[i].another =j;
        }
    }
}
int main() {
    int e;
    cin>>n>>e;
    for(int i=0; i<n; i++)
        cin>>str[i];
    for(int i=0; i<n; i++) {
        dian[i].flag =0;
        dian[i].weigh =MAX;
    }
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            map[i][j]=MAX;
    while(e--) {
        int w;
        char a,b;
        cin>>a>>b>>w;
        map[change(a)][change(b)]=w;
        map[change(b)][change(a)]=w;
    }
    ok[0]=0;
    dian[0].flag =1;//已拿
    int top=0;
    while(top<n) {
        find(ok[top]);//更新剩余点信息
        int min=MAX;
        int p;
        for(int i=0; i<n; i++) {
            if(dian[i].flag ==1)
                continue;
            if(dian[i].weigh <min) {
                min=dian[i].weigh ;
                p=i;
            }
        }
        if(top<n-1)
            cout<<"("<<str[dian[p].another ]<<","<<str[p]<<")";//边比点少一
        top++;
        ok[top]=p;
        dian[ok[top]].flag =1;
    }
    return 0;
}

最小生成树(Prim算法)

prim算法简单来说就是加点法，如下图所示：

Code

相关推荐