qq_39188235 2017-06-22 14:11 采纳率: 66.7%
浏览 830

新手求图的最小生成树,求指点.

#include
#include
#define Infinity 32768
#define OK 1
#define Error -1
#define True 1
#define False 0
#define MAX_VERTEX_NUM 10
typedef enum{DG,DN,UDG,UDN}GraphKind; /*图的种类分别为有向图,有向网,无向图,无向网*/
typedef char VertexData;

typedef struct ArcNode
{int adj;

}ArcNode;
typedef struct
{VertexData vertex[MAX_VERTEX_NUM];
ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum,arcnum; /*图的顶点数和弧数*/
GraphKind kind;
}AdjMatrix;
struct Record{
char adjvex; // U集中的顶点
int lowcost; // 边的权值
}closedge[MAX_VERTEX_NUM];
int LocateVertex(AdjMatrix G,VertexData v)/求顶点位置函数*/
{int j=Error,k;
for(k=0;kvexnum;k++)
if(G->vertex[k]==v)
{j=k;break;
}
return(j);
}
int CreateDN(AdjMatrix G) /创建一个有向网*/
{int i,j,k,weight;VertexData v1,v2;
printf("请输入两个数字表示弧数和顶点数\n");
fflush(stdin); /*清空输入缓冲区*/
scanf("%d,%d",&G->arcnum,&G->vexnum);
for(i=0;ivexnum;i++) /*初始化邻接矩阵*/
for(j=0;jvexnum;j++)
G->arcs[i][j].adj=Infinity;
for(i=0;ivexnum;i++)
{
printf("请输入图的顶点\n");
fflush(stdin);
scanf("%c",&G->vertex[i]);
}
for(k=0;karcnum;k++)
{printf("请输入一条弧的两个顶点及权值\n");
fflush(stdin);
scanf("%c,%c,%d",&v1,&v2,&weight);
i=LocateVertex(G,v1);
j=LocateVertex(G,v2);
G->arcs[i][j].adj=weight; /*建立弧*/
}
return(OK);
}
int Minimum (Record closedge[])
{int reserve=Infinity;
int min;
for(int i=1;i {
if(closedge[i].lowcost0)//没有访问过但是存路径
{
reserve=closedge[i].lowcost;
min=i;
}

}
return min;
}
void Print(AdjMatrix G,char u,char v)
{int start,end;
start=LocateVertex(G,u);
end=LocateVertex(G,v);
printf("%c到%c的权值为%d",u,v,G->arcs[start][end]);
}
void MiniSpanTree_Prim(AdjMatrix &gn,char u)/
从顶点u出发,按普里姆算法构造连通网gn的最小生成树,并输出生成树的每条边*/
{int i,e;
closedge[u].lowcost=0; /*初始化,U={u}*/
for(i=0;i<gn.vexnum;i++)
if(i!=u) /*对V-U中的顶点i,初始化closedge[i]*/
{closedge[i].adjvex=u;
closedge[i].lowcost=gn.arcs[u][i].adj;
}
for(e=1;e<=gn.vexnum-1;e++) /*找n-1条边(n=gn.vexnum*/
{int v=Minimum(closedge); /*closedge[v]中存有当前最小边(u,v)的信息*/
u=closedge[v].adjvex; /*u属于U*/
Print(&gn,u,v); /*输出生成树的当前最小边(u,v)*/
closedge[v].lowcost=0; /*将顶点v纳入U的集合*/
for(i=0;i<gn.vexnum;i++) /*在顶点v并入U之后,更新closedge[i]*/
if(gn.arcs[v][i].adj<closedge[i].lowcost)
{closedge[i].lowcost=gn.arcs[v][i].adj;
closedge[i].adjvex=v;
}
}
}
int main()
{AdjMatrix G;
CreateDN(&G);
char first;
printf("请输入第一个访问的结点\n");
scanf("%c",&first);

MiniSpanTree_Prim(G,first);
return 0;
}
Print函数和那个MiniSpanTree_Prim函数有问题谁帮忙看下。

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 多电路系统共用电源的串扰问题
    • ¥15 slam rangenet++配置
    • ¥15 有没有研究水声通信方面的帮我改俩matlab代码
    • ¥15 对于相关问题的求解与代码
    • ¥15 ubuntu子系统密码忘记
    • ¥15 信号傅里叶变换在matlab上遇到的小问题请求帮助
    • ¥15 保护模式-系统加载-段寄存器
    • ¥15 电脑桌面设定一个区域禁止鼠标操作
    • ¥15 求NPF226060磁芯的详细资料
    • ¥15 使用R语言marginaleffects包进行边际效应图绘制