了解最小生成树Prim算法 麻烦你看看谢谢
如果不对，请指出哪里错了，谢谢
//**************************定义数据结构***********************
typedef struct{
int from, to, weithg;
}MinTree //存得到的最小生成树节点和权值
int InNode[Max]; //Max 为节点的个数
int Mark[Max][Max]; //标记节点是否被访问倒 初始值为Mark[i][j]=0
check(int InNode[],int count,int j ) //判断j是不是已经被访问过，即是否再U中
{ int i;
for(i=0;i<count;i++)
if(InNode[i]==j)return 0;
else return 1;
}
//*****************************主程序*****************
Prim(int G[][],int rt) //G是邻接矩阵存图
{ int v,i,j,count;
InNode[0]=rt;
count=1;
MinTree tree [Max-1];
while(num<Max-1){
for(v=0;v<count;v++)
{
i=InNode[v];
min= MaxWeight; //MaxWeight为图中最大的权值＋1
for(j=0;j<n;j++)
if(check(int InNode[],int count,int j )//判断j是不是已经被访问过，即是否再U中
{
if(G[i][j]<min&&Mark[i][j]!=1)
{
min=G[i][j];
start=i;
end=j;
}//end if
}//end if
//for 结束
if(min==MaxWeigh)exit(0)// 此时图有问题，不连通
InNode[++count]=j;
Tree[++num].from=start;
Tree[num].to=end;
Tree[num].w=min;
Mark[i][j]=1;
}//end while
}//end prim
问题点数：100、回复次数：7Top
1 楼du51（郁郁思扬）回复于 2006-02-28 18:59:43 得分 0
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_NAME 5
#define MAX_VERTEX_NUM 20
typedef char Vertex[MAX_NAME];/*顶点名字串*/
typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接距阵*/
struct MGraph/*定义图*/
{
Vertex vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
};
typedef struct
{
Vertex adjvex; /*当前点*/
int lowcost; /*代价*/
}minside[MAX_VERTEX_NUM];
int LocateVex(MGraph G,Vertex u)//定位
{
int i;
for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vexs[i])==0)return i;
return -1;
}
void CreateGraph(MGraph &G)
{
int i,j,k,w;
Vertex va,vb;
printf("请输入无向网G的顶点数和边数(以空格为分隔)\n");
scanf("%d %d",&G.vexnum,&G.arcnum);
printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME);
for(i=0;i<G.vexnum;++i) /* 构造顶点集*/
scanf("%s",G.vexs[i]);
for(i=0;i<G.vexnum;++i) /*初始化邻接矩阵*/
for(j=0;j<G.vexnum;++j)
G.arcs[i][j]=0x7fffffff;
printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): \n",G.arcnum);
for(k=0;k<G.arcnum;++k)
{
scanf("%s%s%d%*c",va,vb,&w);
i=LocateVex(G,va);
j=LocateVex(G,vb);
G.arcs[i][j]=G.arcs[j][i]=w; /*对称*/
}
}
int minimum(minside SZ,MGraph G)
{
int i=0,j,k,min;
while(!SZ[i].lowcost)i++;
min=SZ[i].lowcost;
k=i;
for(j=i+1;j<G.vexnum;j++)
if(SZ[j].lowcost>0&&min>SZ[j].lowcost)
{
min=SZ[j].lowcost;
k=j;
}
return k;
}
void MiniSpanTree_PRIM(MGraph G,Vertex u)
{
int i,j,k;
minside closedge;
k=LocateVex(G,u);
for(j=0;j<G.vexnum;++j)
{
strcpy(closedge[j].adjvex,u);
closedge[j].lowcost=G.arcs[k][j];
}
closedge[k].lowcost=0;
printf("最小代价生成树的各条边为:\n");
for(i=1;i<G.vexnum;++i)
{
k=minimum(closedge,G);
printf("(%s-%s)\n",closedge[k].adjvex,G.vexs[k]);
closedge[k].lowcost=0;
for(j=0;j<G.vexnum;++j)
if(G.arcs[k][j]<closedge[j].lowcost)
{
strcpy(closedge[j].adjvex,G.vexs[k]);
closedge[j].lowcost=G.arcs[k][j];
}
}
}
int main()
{
MGraph g;
CreateGraph(g);
MiniSpanTree_PRIM(g,g.vexs[0]);
system("PAUSE");
return 0;
}
/*结果如下
请输入无向网G的顶点数和边数(以空格为分隔)
6 10
请输入6个顶点的值(<5个字符):
v1
v2
v3
v4
v5
v6
请输入10条边的顶点1 顶点2 权值(以空格作为间隔):
v1 v2 6
v1 v3 1
v1 v4 5
v2 v3 5
v2 v5 3
v4 v3 5
v4 v6 2
v3 v5 6
v3 v6 4
v5 v6 6
最小代价生成树的各条边为:
(v1-v3)
(v3-v6)
(v6-v4)
(v3-v2)
(v2-v5)
请按任意键继续. . .
*/Top
2 楼fullmoon525（满月）回复于 2006-02-28 19:45:42 得分 0
dijkstra算最短路径的时候，把dist[j]改为dist[j].start dist[j].end dist[j].weight
是不是相当于完成了一次prim啊Top
3 楼du51（郁郁思扬）回复于 2006-02-28 20:43:09 得分 70
你说得我不是很明白.
但是上面这个算法.就有一点不大好理解.所有,已经有点看成一个点..
typedef struct
{
Vertex adjvex; /*当前点*/
int lowcost; /*代价*/
}minside[MAX_VERTEX_NUM];
如上代价是对于点而言的.
还是那个贴子我回 的.
基本的东西是一样的.只有核心算法不同.
至于,LocateVex之类的,因为用的点不是int所以,存在一个定位.你要是输入int
完全可以不用.Top
4 楼digifish（df）回复于 2006-02-28 22:14:24 得分 30
虽然没有仔细看，但是觉得你得check函数有点不对劲，只循环一次就退出来了，那个count变量根本没有用处。Top
5 楼fullmoon525（满月）回复于 2006-03-01 18:01:10 得分 0
check是一旦发现节点存在就跳出来啊Top
6 楼digifish（df）回复于 2006-03-02 02:14:13 得分 0
for(i=0;i<count;i++)
if(InNode[i]==j)return 0;
else return 1;
等于：
for(i=0;i<count;i++) {
if(InNode[i]==j) {
return 0;
} else {
return 1; }
}
只循环1次，i=0, 然后就退出了。Top
7 楼fullmoon525（满月）回复于 2006-03-02 22:49:47 得分 0
哦。。。对的，这个有问题
应该改为
for(i=0;i<count;i++) {
if(InNode[i]==j) {
return 0;
} else {
continue; }
if(i==count-1)return 1;
}Top
相关问题
关键词
得分解答快速导航
相关链接
广告也精彩
反馈
