鱼C论坛

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

仿照数据结构的读书笔记写prim算法的代码,结果运行时却错误,还看不出拿错了,求解!

[复制链接]
最佳答案
0 
发表于 2020-5-22 19:53:21 | 显示全部楼层 |阅读模式
1鱼币
#define MAXVEX 100        //最大顶点数
#define INFINITY        0x7fffffff  //最大值0x7fffffff表示为无穷大,表示不可通


typedef struct
{
        int vexs[MAXVEX];        //顶点向量,顶点表
        int arc[MAXVEX][MAXVEX];        //邻接矩阵
        int numVertexes, numEdges;        //图中当前的顶点数和边数
}MGraph;

//建立无向网图的邻接矩阵
void CreateMGraph(MGraph *G)
{
        int i, j, k, w;

        printf("请输入顶点数和边数:\n");
        scanf_s("%d %d", &G->numVertexes, &G->numEdges);

        printf("请输入顶点名称:\n");
        for (i = 0; i < G->numVertexes; i++)
        {
                scanf_s("%d ", &G->vexs[i]);
        }

        for (i = 0; i < G->numVertexes; i++)
        {
                for (j = 0; j < G->numVertexes; j++)
                {
                        G->arc[i][j] = INFINITY;                //邻接矩阵初始化
                }
        }

        for (k = 0; k < G->numEdges; k++)
        {
                printf("请输入边(vi,vj)上的下标i,下标j和对应的权w:\n");
                scanf_s("%d %d %d", &i, &j, &w);
                G->arc[i][j] = w;
                G->arc[j][i] = G->arc[i][j];
        }
}//CreateMGraph


// Prim算法生成最小生成树
void MiniSpanTree_Prim(MGraph G)
{
        int min, i, j, k,sum = 0;
        int adjvex[MAXVEX];                // 保存相关顶点下标
        int lowcost[MAXVEX];        // 保存相关顶点间边的权值

        lowcost[0] = 0;                        // V0作为最小生成树的根开始遍历,权值为0
        adjvex[0] = 0;                        // V0第一个加入

        // 初始化操作
        for (i = 1; i < G.numVertexes; i++)
        {
                lowcost[i] = G.arc[0][i];        // 将邻接矩阵第0行所有权值先加入数组
                adjvex[i] = 0;                   // 初始化全部先为V0的下标
        }

        // 真正构造最小生成树的过程
        for (i = 1; i < G.numVertexes; i++)
        {
                min = INFINITY;                // 初始化最小权值为0x7fffffff等不可能数值
                k = 0;

                // 遍历全部顶点
                for (j = 1;j < G.numVertexes;j++)
                {
                        // 找出lowcost数组已存储的最小权值
                        if (lowcost[j] != 0 && lowcost[j] < min)
                        {
                                min = lowcost[j];          //找出权值最小的路径长度
                                k = j;                // 将发现的最小权值的下标存入k,以待使用。
                        }
                }

                // 打印当前顶点边中权值最小的边及其权值
                printf("V%d - V%d = %d\n", adjvex[k], k,min);
                sum += min;                                                //求和
                lowcost[k] = 0;                // 将当前顶点的权值设置为0,表示此顶点已经完成任务,进行下一个顶点的遍历

                // 邻接矩阵k行逐个遍历全部顶点
                for (j = 1; j < G.numVertexes; j++)
                {
                        if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j])        //对这一点直达的顶点进行路径更新
                        {
                                lowcost[j] = G.arc[k][j];
                                adjvex[j] = k;
                        }
                }
        }

        printf("最小权值之和 = %d\n",sum);
}//MiniSpanTree_Prim



int main()
{
        MGraph T;

        CreateMGraph(&T);
        MiniSpanTree_Prim(T);

        return 0;
}

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
 楼主| 发表于 2020-5-22 19:58:09 | 显示全部楼层
file:///C:/Users/ASUS/Desktop/%E6%8D%95%E8%8E%B7.PNG
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

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

GMT+8, 2020-6-2 19:21

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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