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

来源：学生作业帮助网编辑：作业帮时间：2024/11/15 14:08:25

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

请问如何用最小堆实现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