数据结构之最小生成树Prim算法建议收藏

普里姆算法介绍普里姆(Prim)算法,是用来求加权连通图的最小生成树算法基本思想:对于图G而言,V是所有顶点的集合;现在,设置两个新的集合U和T,其中U用于存放G的最小生成树中的顶点,T存放G的最

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

数据结构之最小生成树Prim算法建议收藏此处内容已经被作者隐藏,请输入验证码查看内容
验证码:
请关注本站微信公众号,回复“”,获取验证码。在微信里搜索“”或者“”或者微信扫描右侧二维码都可以关注本站微信公众号。

普里姆算法介绍

  普里姆(Prim)算法,是用来求加权连通图的最小生成树算法

  基本思想:对于图G而言,V是所有顶点的集合;现在,设置两个新的集合U和T,其中U用于存放G的最小生成树中的顶点,T存放G的最小生成树中的边。 从所有uЄU,vЄ(V-U) (V-U表示出去U的所有顶点)的边中选取权值最小的边(u, v),将顶点v加入集合U中,将边(u, v)加入集合T中,如此不断重复,直到U=V为止,最小生成树构造完毕,这时集合T中包含了最小生成树中的所有边。

数据结构之最小生成树Prim算法建议收藏

代码实现

1. 思想逻辑

  (1)以无向图的某个顶点(A)出发,计算所有点到该点的权重值,若无连接取最大权重值#define INF    (~(0x1<<31))

  (2)找到与该顶点最小权重值的顶点(B),再以B为顶点计算所有点到改点的权重值,依次更新之前的权重值,注意权重值为0或小于当前权重值的不更新,因为1是一当找到最小权重值的顶点时,将权重值设为了0,2是会出现无连接的情况。

  (3)将上述过程一次循环,并得到最小生成树。

2. Prim算法

// Prim最小生成树
void Prim(int nStart)
{
    int i = 0;
    int nIndex=0;         // prim最小树的索引,即prims数组的索引 
    char cPrims[MAX];     // prim最小树的结果数组 
    int weights[MAX];    // 顶点间边的权值
    
    cPrims[nIndex++] = m_mVexs[nStart].data;

    // 初始化"顶点的权值数组",
    // 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。
    for (i = 0; i < m_nVexNum; i++)
    {
        weights[i] = GetWeight(nStart, i);
    }

    for (i = 0; i < m_nVexNum; i ++)
    {
        if (nStart == i)
        {
            continue;
        }
        
        int min = INF;
        int nMinWeightIndex = 0;
        for (int k = 0; k < m_nVexNum; k ++)
        {
            if (weights[k]!= 0 && weights[k] < min)
            {
                min = weights[k];
                nMinWeightIndex = k;
            }
        }

        // 找到下一个最小权重值索引
        cPrims[nIndex++] = m_mVexs[nMinWeightIndex].data;
        // 以找到的顶点更新其他点到该点的权重值
        weights[nMinWeightIndex]=0;
        int nNewWeight = 0;
        for (int ii = 0; ii < m_nVexNum; ii++)
        {
            nNewWeight = GetWeight(nMinWeightIndex, ii);
            // 该位置需要特别注意
            if (0 != weights[ii] && weights[ii] > nNewWeight)
            {
                weights[ii] = nNewWeight;
            }
        }
    }
    // 计算最小生成树的权重值
    int nSum = 0;
    for (i = 1; i < nIndex; i ++)
    {
        int min = INF;
        int nVexsIndex = GetVIndex(cPrims[i]);
        for (int kk = 0; kk < i; kk ++)
        {
            int nNextVexsIndex = GetVIndex(cPrims[kk]);
            int nWeight = GetWeight(nVexsIndex, nNextVexsIndex);
            if (nWeight < min)
            {
                min = nWeight;
            }
        }
        nSum += min;
    }

    // 打印最小生成树 
    cout << "PRIM(" << m_mVexs[nStart].data  <<")=" << nSum << ": "; 
    for (i = 0; i < nIndex; i++) 
        cout << cPrims[i] << " "; 
    cout << endl; 

}

3. 全部实现

数据结构之最小生成树Prim算法建议收藏
数据结构之最小生成树Prim算法建议收藏

#include "stdio.h" #include <iostream> using namespace std; #define MAX 100 #define INF (~(0x1<<31)) // 最大值(即0X7FFFFFFF) class EData { public: EData(char start, char end, int weight) : nStart(start), nEnd(end), nWeight(weight){} char nStart; char nEnd; int nWeight; }; // struct ENode { int nVindex; // 该边所指的顶点的位置 int nWeight; // 边的权重 ENode *pNext; // 指向下一个边的指针 }; struct VNode { char data; // 顶点信息 ENode *pFirstEdge; // 指向第一条依附该顶点的边 }; // 无向邻接表 class listUDG { public: listUDG(){}; listUDG(char *vexs, int vlen, EData **pEData, int elen) { m_nVexNum = vlen; m_nEdgNum = elen; // 初始化"邻接表"的顶点 for (int i = 0; i < vlen; i ++) { m_mVexs[i].data = vexs[i]; m_mVexs[i].pFirstEdge = NULL; } char c1,c2; int p1,p2; ENode *node1, *node2; // 初始化"邻接表"的边 for (int j = 0; j < elen; j ++) { // 读取边的起始顶点和结束顶点 c1 = pEData[j]->nStart; c2 = pEData[j]->nEnd; p1 = GetVIndex(c1); p2 = GetVIndex(c2); node1 = new ENode(); node1->nVindex = p2; node1->nWeight = pEData[j]->nWeight; if (m_mVexs[p1].pFirstEdge == NULL) { m_mVexs[p1].pFirstEdge = node1; } else { LinkLast(m_mVexs[p1].pFirstEdge, node1); } node2 = new ENode(); node2->nVindex = p1; node2->nWeight = pEData[j]->nWeight; if (m_mVexs[p2].pFirstEdge == NULL) { m_mVexs[p2].pFirstEdge = node2; } else { LinkLast(m_mVexs[p2].pFirstEdge, node2); } } } ~listUDG() { ENode *pENode = NULL; ENode *pTemp = NULL; for (int i = 0; i < m_nVexNum; i ++) { pENode = m_mVexs[i].pFirstEdge; if (pENode != NULL) { pTemp = pENode; pENode = pENode->pNext; delete pTemp; } delete pENode; } } void PrintUDG() { ENode *pTempNode = NULL; cout << "邻接无向表:" << endl; for (int i = 0; i < m_nVexNum; i ++) { cout << "顶点:" << GetVIndex(m_mVexs[i].data)<< "-" << m_mVexs[i].data<< "->"; pTempNode = m_mVexs[i].pFirstEdge; while (pTempNode) { cout <<pTempNode->nVindex << "->"; pTempNode = pTempNode->pNext; } cout << endl; } } // Prim最小生成树 void Prim(int nStart) { int i = 0; int nIndex=0; // prim最小树的索引,即prims数组的索引  char cPrims[MAX]; // prim最小树的结果数组  int weights[MAX]; // 顶点间边的权值  cPrims[nIndex++] = m_mVexs[nStart].data; // 初始化"顶点的权值数组", // 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。 for (i = 0; i < m_nVexNum; i++) { weights[i] = GetWeight(nStart, i); } for (i = 0; i < m_nVexNum; i ++) { if (nStart == i) { continue; } int min = INF; int nMinWeightIndex = 0; for (int k = 0; k < m_nVexNum; k ++) { if (weights[k]!= 0 && weights[k] < min) { min = weights[k]; nMinWeightIndex = k; } } // 找到下一个最小权重值索引 cPrims[nIndex++] = m_mVexs[nMinWeightIndex].data; // 以找到的顶点更新其他点到该点的权重值 weights[nMinWeightIndex]=0; int nNewWeight = 0; for (int ii = 0; ii < m_nVexNum; ii++) { nNewWeight = GetWeight(nMinWeightIndex, ii); // 该位置需要特别注意 if (0 != weights[ii] && weights[ii] > nNewWeight) { weights[ii] = nNewWeight; } } } // 计算最小生成树的权重值 int nSum = 0; for (i = 1; i < nIndex; i ++) { int min = INF; int nVexsIndex = GetVIndex(cPrims[i]); for (int kk = 0; kk < i; kk ++) { int nNextVexsIndex = GetVIndex(cPrims[kk]); int nWeight = GetWeight(nVexsIndex, nNextVexsIndex); if (nWeight < min) { min = nWeight; } } nSum += min; } // 打印最小生成树  cout << "PRIM(" << m_mVexs[nStart].data <<")=" << nSum << ": "; for (i = 0; i < nIndex; i++) cout << cPrims[i] << " "; cout << endl; } private: // 获取<start, end>的权值,若start和end不是连接的,则返回无穷大 int GetWeight(int start, int end) { if (start == end) { return 0; } ENode *pTempNode = m_mVexs[start].pFirstEdge; while (pTempNode) { if (end == pTempNode->nVindex) { return pTempNode->nWeight; } pTempNode = pTempNode->pNext; } return INF; } // 返回顶点的索引 int GetVIndex(char ch) { int i = 0; for (; i < m_nVexNum; i ++) { if (m_mVexs[i].data == ch) { return i; } } return -1; } void LinkLast(ENode *pFirstNode, ENode *pNode) { if (pFirstNode == NULL || pNode == NULL) { return; } ENode *pTempNode = pFirstNode; while (pTempNode->pNext != NULL) { pTempNode = pTempNode->pNext; } pTempNode->pNext = pNode; } private: int m_nVexNum; // 顶点数目 int m_nEdgNum; // 边数目  VNode m_mVexs[MAX]; VNode m_PrimVexs[MAX]; }; void main() { char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; // EData *edges[] = { // 起点 终点 权  new EData('A', 'B', 12), new EData('A', 'F', 16), new EData('A', 'G', 14), new EData('B', 'C', 10), new EData('B', 'F', 7), new EData('C', 'D', 3), new EData('C', 'E', 5), new EData('C', 'F', 6), new EData('D', 'E', 4), new EData('E', 'F', 2), new EData('E', 'G', 8), new EData('F', 'G', 9) }; int vlen = sizeof(vexs)/sizeof(vexs[0]); int elen = sizeof(edges)/sizeof(edges[0]); listUDG* pG = new listUDG(vexs, vlen, edges, elen); pG->PrintUDG(); // 打印图  pG->Prim(0); for (int i = 0; i < elen; i ++) { delete edges[i]; } return; }

View Code

数据结构之最小生成树Prim算法建议收藏

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/120149.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 动态规划之0-1背包问题(详解+分析+原码)

    动态规划之0-1背包问题(详解+分析+原码)本篇文章将介绍算法专题之动态规划中的背包问题,更准确的说是背包问题中最简单的一种类型,即0-1背包问题,就是给你一定容量的背包和若干物品,每种物品只能选一次,告诉你每件物品的价值和体积,求背包里面物品的最大总价值。

  • 软件安全之动态链接库的使用 Libzplay 播放音乐「建议收藏」

    实验1动态链接库的使用实验说明Libzplay是遵循GPL协议的开源库,它集成了mp3、flac、ac3、aac、wav等多种音频格式的解码器和编码器,提供了面向C/C++、C#、Delphi等多种编程语言的接口,仅需3行代码(创建播放资源,打开文件,开始播放)便可实现音乐播放功能。实验目的本实验通过Libzplay提供的C语言接口,实现简单的音乐播放器,以此学习DLL的隐式和显式加载方式。实验原理课程第2讲基础知识实验环境Windows

  • Sublime Text 3安装及常用插件安装

    Sublime Text 3安装及常用插件安装欢迎访问我的个人博客http://xiaolongwu.cn/一、Sublime3下载1.百度搜索Sublime3download,选择进入下载页面2.我选择下载Win64位安装程序二、Sublime3安装傻瓜式安装,一直点下一步即可。三、Sublime3插件配置1.直接安装安装Sublimetext3插件很方便,可以直接下载安装…

  • python编程100例_python典型异常

    python编程100例_python典型异常异常模块下面介绍python常用的异常模块AttributeError异常AttributeError试图访问一个类中不存在的成员(包括:成员变量、属性和成员方法)而引发的异常Attribut

  • JAVA实现文件预览功能

    JAVA实现文件预览功能(PS前阵子发现图片没了,CSDN也没修复好,只好重新上传)近期做的项目要求实现文件在线预览功能,可支持多种文件类型,TXT,DOC,PDF,XLS,最好支持压缩包的预览功能.没办法,只能网上找啊.看了个遍,都是些不靠谱的,转来转去的一个能用的都没有,付费的产品有什么永中啊,OFFICE365啊,这些大概一搜都能搜到,价格也不是很贵但俗话说的好,能不用钱解决问题,就尽…

  • mybatis逆向工程是什么意思_长话短说的方法

    mybatis逆向工程是什么意思_长话短说的方法目录Mybatis逆向工程一、通过Eclipse插件完成Mybatis逆向工程1.在线安装Eclipse插件2.新建一个JavaProject项目3.编写配置文件4.使用插件运行二、通过Java代码完成Mybatis逆向工程1.新建一个JavaProject项目2.编写配置文件3.编写生成代码程序三、通过Maven完成Mybatis逆向工程1…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号