沟通无限校园网--最小生成树（prim算法）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了沟通无限校园网--最小生成树（prim算法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1542字，纯文字阅读大概需要3分钟。

内容图文

算法代码如下

#include <iostream>
using namespace std;
const int INF = 0x3fffffff;
const int N = 100;
bool s[N];
int closest[N];
int lowcost[N];
void Prim(int n, int u0, int c[N][N]) 
{  //顶点个数n、开始顶点u0、带权邻接矩阵C[n][n]
  //如果s[i]=true,说明顶点i已加入最小生成树
  //的顶点集合U；否则顶点i属于集合V-U
  //将最后的相关的最小权值传递到数组lowcost
  s[u0] = true; //初始时，集合中U只有一个元素，即顶点u0
  int i;
  int j;
  for(i = 1; i <= n; i++)//①
  {
       if(i != u0) 
       {
            lowcost[i] = c[u0][i];
            closest[i] = u0;
            s[i] = false;
       }
       else
            lowcost[i] =0;
  }
  for(i = 1; i <= n; i++)  //②
  {
       int temp = INF;
       int t = u0;
       for(j = 1; j <= n; j++) //③在集合中V-u中寻找距离集合U最近的顶点t
       { 
           if((!s[j]) && (lowcost[j] < temp)) 
           {
                t = j;
                temp = lowcost[j];
           }
       }
      if(t == u0)
         break;       //找不到t，跳出循环
      s[t] = true;    //否则，讲t加入集合U
      for(j = 1; j <= n; j++)  //④更新lowcost和closest
      {       
          if((!s[j]) && (c[t][j] < lowcost[j]))
          {
              lowcost[j] = c[t][j];
              closest[j] = t;
          }
      }
    }
}
int main()
{
    int n, c[N][N], m, u, v, w;
    int u0;
    cout <<"输入结点数n和边数m："<<endl;
    cin >> n >> m;
    int sumcost = 0;
    for(int i = 1; i <= n; i++) 
       for(int j = 1; j <= n; j++) 
          c[i][j] = INF;
    cout <<"输入结点数u，v和边值w："<<endl;
    for(int i=1; i<=m; i++) 
    {
        cin >> u >> v >> w;
        c[u][v] = c[v][u] = w;
    }
    cout <<"输入任一结点u0："<<endl;
    cin >> u0 ;
    //计算最后的lowcost的总和，即为最后要求的最小的费用之和
    Prim(n, u0, c);
    cout <<"数组lowcost的内容为："<<endl;
    for(int i = 1; i <= n; i++)
        cout << lowcost[i] << " ";
    cout << endl;
    for(int i = 1; i <= n; i++)
                sumcost += lowcost[i];
    cout << "最小的花费是：" << sumcost << endl << endl;
    return 0;
}

内容总结

以上是互联网集市为您收集整理的沟通无限校园网--最小生成树（prim算法）全部内容，希望文章能够帮你解决沟通无限校园网--最小生成树（prim算法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---