请问如何用最小堆实现prim算法来求最小生成树权值?

来源：学生作业帮编辑：搜狗做题网作业帮分类：综合作业时间：2024/07/09 03:27:50

请问如何用最小堆实现prim算法来求最小生成树权值?
如题.求详细思路,尤其是在取了最小堆的顶点后,如何再次更新最小堆.当然,如果可以附上C语言的实现程序的话最好不过.
万分感激.

用邻接矩阵存储图.
#include
#include
using namespace std;
typedef pairP;//无序对,堆中存的是无序对,第一个表示节点,第二个表示节点对应的最短路径值
const int MAX=100;
int mind[MAX];//最短距离
const int MAXN=1000000;
int path[MAX];//路径
int s,t,n,m;
int vis[MAX];//是否已经遍历过
int g[MAX][MAX];
class Heap
{
public:
P elem[MAX];
\x05int n;
\x05Heap(){n=0;}
\x05void ins(P e);
\x05P del();
\x05int num();
\x05
};
void Heap::ins(P e)
{
int p;
\x05for(p=++n;p>1&&e.second>1].second;elem[p]=elem[p>>1],p>>=1);//与父结点比较,父结点大的话交换
\x05elem[p]=e;
}
P Heap::del()//删除一个元素,并保持最小堆的性质
{
\x05int i=1,j;
P e=elem[1];
\x05for(j=2;jn>>m)
\x05{//分别是边的个数和顶点的个数
\x05\x05vectorv(m);//保存各个点的连接情况,每个一维向量是与该点的各个相连的边
\x05\x05int i,j;
\x05\x05for(i=0;i>b>>c;
\x05\x05\x05g[a][b]=c;
\x05\x05\x05g[b][a]=c;
\x05\x05}
\x05\x05Heap h;
\x05\x05h.n=0;
\x05\x05P e;
\x05\x05for(i=0;i

利用Prim（普里姆）算法构造最小生成树程序求带权图的最小生成树一、实验目的熟练理解求最小生成的Prim算法；锻炼程序设计能力.二、实验内容编程实现求无向带权图的最如图所示为一个无向带权图,请分别按照Prim算法和Kruskal算法求最小生成树 Kruskal算法和Prim算法构造它的一棵最小代价生成树的过程求一个源代码要求显示图的邻接矩阵图的邻接表,深度广度优先遍历最小生成树PRIM算法KRUSCAL算法图的连通分用普里姆（Prim）或克鲁斯卡尔（Kruskal）算法画出下列无向网的最小生成树对于以下无向带权图.利用Prim算法,从V1出发,得到最小生成树的过程中, 最小生成树普里姆算法,求指错使用普里姆算法求最小生成树. 急求KRUSKAL算法求最小生成树过程演示用普里姆算法求最小生成树（C++）数据结构课程设计用Kruskal 算法求最小生成树