育才学习网1.c语言最小生成树怎样写
prim算法/* 函数功能：求图的最小生成树。
函数原形：GraphClass
备注：无。*/ template
函数原形：GraphClass
备注：无。*/ template
2.求我下面程序函数的流程图
普里姆算法
功能：是利用普里姆算法求出无向网所对应的最小生成树.
实现过程：在其函数体中，首先，定义closedge用于存放最小生成树中的顶点，调用函数Locate（)求出起点u在顶点向量表中的位置，初始化U={u}，利用for循环对V-U中的顶点i，初始化，再利用for循环找n-1条边，其中，调用函数Minium（)求出辅助数组中权值最小的边， 并将其在辅助数组中的相应位置返回到主调函数中，最后，输出<；起点->；终点 权值>。
代码如下：
void PRIM(MGraph &G,VertexType u)
{
int i,j,k;
minside closedge;
k=LocateVex(G,u);
for(j=0;j<G.vexnum;++j) // 辅助数组初始化
{
if(j!=k)
{
strcpy(closedge[j].adjvex,u);
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
closedge[k].lowcost=0； // 初始，U={u}
printf("\t\t最小代价生成树的各条边及权值为：\n");
printf("\n");
printf("\t\t<；起点->；终点>\t权值\n");
for(i=1;i<G.vexnum;++i)
{ // 选择其余G.vexnum-1个顶点
k=minimum(closedge,G)； // 求出T的下一个结点：第K顶点
printf("<%s-%s>\t\t%d\n",closedge[k].adjvex,G.vexs[k],closedge[k].lowcost)； // 输出生成树的边
closedge[k].lowcost=0； // 第K顶点并入U集
for(j=0;j<G.vexnum;++j)
if(G.arcs[k][j].adj<closedge[j].lowcost)
{
// 新顶点并入U集后重新选择最小边
strcpy(closedge[j].adjvex,G.vexs[k]);
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
}
(5)子函数int LocateVex(MGraph G,VertexType u)
功能：是求出某个顶点在顶点向量表中的位置。
实现过程：在其函数体中通过for循环将某一顶点与顶点向量表中的所有顶点进行比较，当出现两者相等时，将该顶点在vexs[]数组的下标通过return语句返回，否则返回-1;
代码如下：
int LocateVex(MGraph G,VertexType u) //若G中存在顶点u，则返回该顶点在图中的位置，否则返回-1
{
int i;
for(i = 0; i < G.vexnum; ++i)
if( strcmp(u, G.vexs[i]) == 0)
return i;
return -1;
}
(6)子函数int minimum(minside S,MGraph G)
功能：是求出辅助数组中权值最小的边。
代码如下：
int minimum(minside S,MGraph G) //求closedge.lowcost的最小值
{
int i=0,j,k,min;
while(!S[i].lowcost)
i++;
min=S[i].lowcost； // 第一个不为0的值
k=i;
for(j=i+1;j<G.vexnum;j++)
if(S[j].lowcost>0)
if(min>S[j].lowcost)
{
min=S[j].lowcost;
k=j;
}
return k;
}
3.c语言最小生成树怎样写
prim算法/*函数功能：求图的最小生成树。
函数原形：GraphClass
备注：无。*/template
函数原形：GraphClass
备注：无。*/template
4.最小生成树的定义以及有关算法
Kruskal算法和Prim算法 任何只由G的边构成，并包含G的所有顶点的树称为G的生成树（G连通）.加权无向图G的生成树的代价是该生成树的所有边的代码（权）的和.最小代价生成树是其所有生成树中代价最小的生成树.参考代码：（仅为主程序，更多代码在 /zsb/zsx/zsx07/zsx079/main9/zsx079001.htm Kruskal算法和Prim算法 任何只由G的边构成，并包含G的所有顶点的树称为G的生成树（G连通）. 加权无向图G的生成树的代价是该生成树的所有边的代码（权）的和. 最小代价生成树是其所有生成树中代价最小的生成树. 参考代码： （仅为主程序，更多代码在 /bbs/dispbbs.asp?boardID=1&ID=69&page=1 解压密码： ） #include "Sets.h" #include "themap.h" #include "windows.h" #include 为了避免最小生成树不唯一的问题，可以不妨假设这个图所有的边长都不相等 （注意最小生成树的总长度是原图边长的连续函数，所以可以这样加强条件） 然后用反证法，假定Kruskal算法中的第k步首次出现错误，算法选了E1，但实际上必须选另一条边E2才能得到最小生成树T0 E1连接了两个连通分支，这两个连通分支在最终的T0里是连通的，所以把T0和E1放在一起之后形成的图有一个环，在这个环里一定有k步或之后新选的边（如果没有的话仅凭前k-1条边和E1不会构成环），依照E1的定义，这个环里存在比E1长的边，用E1换掉这条边之后得到的树T1比T0更短，矛盾 将城市看成是点，城市之间的距离看成是点之间的权值。 下面是PRIM算法实现的最小生成树代码。，利用邻接矩阵存储边的信息。 程序已通过编译了，可以直接运行。#include 对无权图，用1（是）或0（否）表示相邻否*/ /*对带全图，则为权值类型*/ InfoType *info； /*该弧相关信息的指针（可无）*/ }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { VertexType vexs[MAX_VERTEX_NUM]； /*顶点向量*/ AdjMatrix arcs； /*邻接矩阵*/ int vexnum,arcnum； /*图的当前顶点数和弧数*/ GraphKind kind； /*图的种类标志*/ }MGraph; int LocateVex(MGraph G,VertexType u) { /*初始条件：图G存在，u和G中顶点有相同特征*/ /*操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1*/ int i; for(i=0;i <1,6>；边长度未知，这里看成无穷大。 历次循环中，选择两端点分别在U,V中的边中长度最小者， 具体如下： 1. 将1加入U中，其余点加入V中。 2. 选择边<1,7>；，将7加入U中，从V中除去该点。 3. 选择边<7,6>；，将6加入U中，从V中除去该点。 4. 选择边<1,2>；，将2加入U中，从V中除去该点。 5. 选择边<2,3>；，将3加入U中，从V中除去该点。 6. 选择边<2,4>；，将4加入U中，从V中除去该点。 7. 选择边<2,5>；，将5加入U中，从V中除去该点。 结束。由上述六条边组成的树为求得的最小生成树。 转载请注明出处育才学习网 » 最小生成树中minium函数怎么写7.如何证明用 Kruskal's 算法生成的树是最小生成树
8.数据结构 Prim和Kruskal最小生成树 的代码怎么写
9.利用普里姆算法求解最小生成树,写出步骤或画图表示过程