#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函数有问题谁帮忙看下。