返回
首页
业界
电商
创业
访谈
手机
移动
报告
运营
建站
互联网+
系统
教程
搜索

使用C语言实现最小生成树求解的简单方法

2020-01-06 13:44:10王冬梅
  • }   
  • /* 标记1号节点加入生成树 */  mst[1] = 0; 
  •   /* n个节点至少需要n-1条边构成最小生成树 */ 
  • for (i = 2; i <= n; i++)  { 
  • min = MAXCOST;  minid = 0; 
  •   /* 找满足条件的最小权值边的节点minid */ 
  • for (j = 2; j <= n; j++)  { 
  • /* 边权值较小且不在生成树中 */  if (lowcost[j] < min && lowcost[j] != 0) 
  • {  min = lowcost[j]; 
  • minid = j;  } 
  • }  /* 输出生成树边的信息:起点，终点，权值 */ 
  • printf("%c - %c : %dn", mst[minid] + 'A' - 1, minid + 'A' - 1, min);   
  • /* 累加权值 */  sum += min; 
  •   /* 标记节点minid加入生成树 */ 
  • lowcost[minid] = 0;   
  • /* 更新当前节点minid到其他节点的权值 */  for (j = 2; j <= n; j++) 
  • {  /* 发现更小的权值 */ 
  • if (graph[minid][j] < lowcost[j])  { 
  • /* 更新权值信息 */  lowcost[j] = graph[minid][j]; 
  •   /* 更新最小权值边的起点 */ 
  • mst[j] = minid;  } 
  • }  } 
  • /* 返回最小权值和 */  return sum; 
  • }   
  • int main()  { 
  • int i, j, k, m, n;  int x, y, cost; 
  • char chx, chy;   
  • /* 读取节点和边的数目 */  scanf("%d%d", &m, &n); 
  • getchar();   
  • /* 初始化图，所有节点间距离为无穷大 */  for (i = 1; i <= m; i++) 
  • {  for (j = 1; j <= m; j++) 
  • {  graph[i][j] = MAXCOST; 
    • 相关文章 大家在看