数据结构之最小生成树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)


相关推荐

  • ARP欺骗原理_ARP欺骗实验

    ARP欺骗原理_ARP欺骗实验一.arp欺骗的原理 以太网设备(比如网卡)都有自己全球唯一的MAC地址,它们是以MAC地址来传输以太网数据包的,但是以太网设备却识别不了IP数据包中的IP地址,所以要在以太网中进行IP通信,就需要一个协议来建立IP地址与MAC地址的对应关系,使IP数据包能够发送到一个确定的主机上。这种功能是由arp(AddressResolutionProtocol)来完成的。 arp被设计成用来实现

    2022年10月25日
  • Cisco三层交换机的配置详解

    Cisco三层交换机的配置详解

  • python 制作淘宝秒杀脚本

    python 制作淘宝秒杀脚本1. 安装pycharm。网上教程很多。2. 安装Selenium库。Selenium支持很多浏览器,我选择的是Firefox浏览器。因为我这里是Python3环境,自带的又pip,所以安装selenium直接使用pip安装安装方法:–打开cmd;–输入命令进入Python36/Scripts(找到下图的目录)目录下;–输入命令pipinstalls…

  • 一文看懂25个神经网络模型

    一文看懂25个神经网络模型1.引言在深度学习十分火热的今天,不时会涌现出各种新型的人工神经网络,想要实时了解这些新型神经网络的架构还真是不容易。光是知道各式各样的神经网络模型缩写(如:DCIGN、BiLSTM、DCGAN……还有哪些?),就已经让人招架不住了。因此,这里整理出一份清单来梳理所有这些架构。其中大部分是人工神经网络,也有一些完全不同的怪物。尽管所有这些架构都各不相同、功能独特,当我在画它们的节点图时……其中潜在

  • 关于java类加载正确的是_java类什么时候被加载

    关于java类加载正确的是_java类什么时候被加载注意我们当在另一个类中引用其他类的final静态值的时候,编译器把其他类的final符号引用存储在自己类的常量池中了

  • 注册网页_dubbo服务注册

    注册网页_dubbo服务注册大概在去年的时候发现生产环境使用eureka经常会发现服务假死eureka没有给踢掉的情况,然后就衍生了要不就换个注册中心试试,然后就了解到了nacos,正好他还融合了配置中心,但是后来碍于切换时怕生产环境不稳定,丢数据等问题就一直没有换,但后续的项目的注册中心都换成了nacos,这篇文章我就来模拟一下如何将eureka平滑切换成nacos………………

发表回复

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

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