首页 > 代码库 > 校园导游图的课程设计(三)
校园导游图的课程设计(三)
两天和作一天吧
只要是作 prime 算法的实现，作用是找一个图的最小生成树，用的是列表
void Prim( ListMatrix *G, int start )/* * 寻找一某一点为核心的最佳布线 * 即使用prime最小生成树 */ { struct{ int adjvex; int lowcost; }closedge[NUMMAX]; int i,j,k,m,min; ArcNode * p; closedge[start].lowcost = 0; for( i=1; i<=G->vexnum; i++ ) { if( i != start ) { closedge[i].adjvex = start; closedge[i].lowcost = INFNITY; } }//初始化，无穷大 p = G->vertex[start].next; while( p != NULL ) { closedge[p->adjvex].lowcost = p->weight; p = p->next; }//复制 for( j=1; j<=G->vexnum; j++ ) { min = INFNITY; for( k=1; k<=G->vexnum; k++ ) { if( closedge[k].lowcost!=0 && closedge[k].lowcost < min ) { m = k; min = closedge[k].lowcost; } }//挑选最小的 closedge[m].lowcost = 0; p = G->vertex[m].next; while( p != NULL ) { if( p->weight < closedge[p->adjvex].lowcost ) { closedge[p->adjvex].lowcost = p->weight; closedge[p->adjvex].adjvex = m; } p = p->next; }//while 找到变短的 } printf("\t\t\t\t\t\t\t布线方式:\n"); for( i=1; i<=G->vexnum; i++ ) { if( i!= start) { printf("\t\t\t\t\t\t\t%d 从%d:%s 到 %d:%s\n ",i,closedge[i].adjvex, NumtoName(G,closedge[i].adjvex),i,NumtoName(G,i)); } } }prime算法的核心在与 在V 和 V-S 集合之间寻找一个最短一个路径，将这个路径的V-S 头放在 V集，在进行下一步，直到最后。
还有就是节点的删除和添加，弧的添加和删除
M节点的删除的思路:
删除与之相连的弧
删除M节点，将后面的节点往前移动
遍历所有弧，将弧尾节点指向大于M，自减一
完成
校园导游图的课程设计(三)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。