数据结构之最⼩⽣成树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中包含了最⼩⽣成树中的所有边。
代码实现
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 ++)
weight的所有形式{
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;
}
}
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. 全部实现
#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 ++)
{
// 读取边的起始顶点和结束顶点
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 ++)
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)
{
return0;
}
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 -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
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论