Question

数据结构 最小生成树问题

#include<stdio.h>#include<stdlib.h>#include<string.h>#define maxvexnum 100#define infinite 65535 /* ∞设为双字节无符号整数的最大值65535*/typedef char vextype;typedef struct Graph{ int arc[maxvexnum][maxvexnum]; int vexnum,arcnum; } graph;void CreatGraph(graph *G)//无向图 { int i,j; scanf ("%d",&G->vexnum); for (i=0;i<G->vexnum;i++)//初始化邻接矩阵 for (j=0;j<G->vexnum;j++) G->arc[i][j]=infinite; for (i=0;i<G->vexnum;i++) for (j=0;j<G->vexnum;j++) { scanf ("%d",&G->arc[i][j]); G->arc[j][i]=G->arc[i][j]; if(G->arc[i][j]) G->arcnum++; } }int prim(graph *G){ int locate=0,i=0,j=0,k=0,l=0,min=infinite; int exist[100],count=0,totalmin=0,exchange=0,now=0;//将exist分成两块 count之前的为已经纳入最小生成树中的节点 （包括count），count之后的为不在最小生成树中的节点 for(i=0;i<G->vexnum;i++) exist[i]=i; while(count!=G->vexnum-1)//直到count的值等于总节点的值 { min=infinite; for(k=0;k<=count;k++) { for(j=G->vexnum-1;j>count;j--) { if(G->arc[exist[k]][exist[j]]<min&&G->arc[exist[k]][exist[j]]!=0)//如果有更小的权值，将现在j的值付给now { min=G->arc[exist[k]][exist[j]]; now=j; } } } exchange=exist[count+1];//将现在的now纳入最小生成树中（即交换后将count值+1） exist[count+1]=exist[now]; exist[now]=exchange; count++; totalmin=totalmin+min; } return totalmin;}int main(void){ graph G; int min; CreatGraph(&G); min=prim(&G); printf("%d",min); return 0;}/*输入： 40 4 9 21 4 0 21 179 21 0 1621 17 16 0输出：28*/ 请问我这样写有错误吗？ 为什么poj过不去？





Answer 1

该算法以贪心为基础，每次保证了添加生成的树一定是最小生成树