Question

构造可以使n个城市连接的最小生成树（要求实现以下功能）

1、功能给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。
2、数据a） 城市间距离用邻接矩阵表示，其存储结构用教材定义表示，若城市间不存在道路，则将相应边的权值用自己定义的无穷大表示，要求在屏幕上显示得到的最小生成树中包括了那些城市间的道路，并显示出得到的最小生成树的代价。b） 表示城市间的距离的邻接矩阵至少6个城市10条道路。c） 最小生成树中包括边及其权值，并显示出得到的最小生成树的代价。
3、操作输出最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。
4、要求界面友好，提示信息完整。
复制搜索复制搜索

Answer 1

MST-PRIM(G, wm r) /* 图G，边权w，出发定点r */
{
图G的所有顶点进入优先队列Q;
ans <- 0;
for each u 属于 Q do key[u] <- 无穷;
key[r] <- 0; pi[r] <- NIL;
while Q不为空 do
取出Q中key值最小的顶点u;
for each 与u相连的顶点v do
if v属于Q and w(u,v) < key[v] then
{
pi[v] <- u; key[v] <- w(u,v); ans <- w(u,v);
}
}
输出权和ans;
}

注意的一点是：如果你要用邻接矩阵表示图，队列Q用二叉堆实现，效率会比较高

这都是基础知识，买本书看下就好了