鱼C论坛

 找回密码
 立即注册
查看: 2690|回复: 1

[技术交流] 最小生成树prim算法

[复制链接]
发表于 2018-2-22 19:02:44 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
#include <iostream>
using namespace std;
#define MAXSIZE 100
#define INFINITY 65535
typedef int ElemType;
typedef char VertexType;
typedef struct MGraph{
    VertexType vertex[MAXSIZE];///顶点表
    ElemType arc[MAXSIZE][MAXSIZE];///邻接矩阵,可看作边表
    ElemType vertexNum, arcNum;///vertexNum是顶点数,arcNum是边数
};
void CreateMGraph(MGraph *G) {
    int i, j, k ,w ;
    cout << "输入边数和顶点数:";
    cin >> G->arcNum >> G->vertexNum;
    //输入顶点
    cout << "输入顶点" << endl;
    for (i = 0; i < G->vertexNum; i++) {
        cin >> G->vertex[i];
    }
    //初始化矩阵
    for (i = 0; i < G->vertexNum; i++) {
        for (j = 0; j < G->vertexNum; j++) {
            G->arc[i][j] = INFINITY;
            G->arc[i][i] = 0;
        }

    }
    ///输入由顶点构成的边
    for (k = 0; k < G->arcNum; k++) {
        cout << "请输入与边关联的两个顶点的序号和权值,例如( 1 2 34):" << endl;
        cin >> i >> j>>w;
        G->arc[i][j] = w;
        G->arc[j][i] = G->arc[i][j];
    }
}
void MinSpanTree_Prim(MGraph G){
    int min,i, j, k;
    int adjvex[MAXSIZE];//存放相关顶点的下标
    int lowest[MAXSIZE];//存放相关顶点权值的下标
    lowest[0] = 0;
    adjvex[0] = 0;//初始化
    //初始化
    for( i = 0;i < G.vertexNum; i++)
    {
        adjvex[i] = 0;//初始化
        lowest[i] =G.arc[0][i];//存放与V0有联系的边的权值

    }
    //构造最小生成树
    for ( i = 1 ;i < G.vertexNum;i++)
    {
        min = INFINITY;
        k = 0;
        //找到与起点相关的边的最小权值
        for(j =1 ;j < G.vertexNum ; j++)
        {
            if(lowest[j] != 0 && lowest[j] < min)
            {
                min = lowest[j];
                k=j;//将当前最小权值的下表存放给k
            }

        }
        cout<<adjvex[k]<<"\t"<<k<<endl;//打印最小权值的边,adjvex[k]在遍历第二次时,存放的是上一个顶点,而k是此次的顶点
        lowest[k] = 0;
        //开始遍历与这个顶点有关的边+
        for( j = 1;j < G.vertexNum; j++ )
        {
            if(lowest[j] != 0 && G.arc[k][j] < lowest[j] )
            {
                lowest[j] = G.arc[k][j];  //此时lowest【j】是最小权值,且其他都为0或者无穷大,所以这个是最小的,下次循环用
                adjvex[j] = k;//将下标为k的顶点放入adjvex
                        
            }
        }
    }
}
void print(MGraph *G){
    int i , j;
    cout<<"输出邻接矩阵:"<<endl;
    //输出矩阵
    for(i = 0;i < G->vertexNum; i++)
    {
        for(j = 0; j <G->vertexNum; j++)
        {
            cout<<G->arc[i][j]<<"\t";
        }
        cout<<endl;
    }
}
int main() {
    MGraph G;
    CreateMGraph(&G);
    MinSpanTree_Prim(G);
    print(&G);
    return 0;
}
这个代码是我已经调试过没问题的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-11-21 21:09:35 | 显示全部楼层
&#128077;
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 19:30

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表