Xingkong vs C++

C++ learning
随笔 - 5, 文章 - 0, 评论 - 2, 引用 - 0
数据加载中……

kruskal算法实现

//给出kruskal球联通网络的最小生成树的算法实现
//调试成功
#include<iostream>
#include<stack>
using namespace std;
int main()
{
 stack<int> travstack;
 int i,j,k,n=5;
 cout<<"以矩阵形式表示"<<endl;
 int a[5][5],b[5][5],c[5][5],d[5];
 cout<<"请输入各路径权值";
 for( i=0;i<n;i++)
    for(j=i+1;j<n;j++)
 {
        cout<<"a[i][j]="<<endl;
        cin>>a[i][j];
 }
 int biggest=0,big=1000;
 for(k=0;k<n*n-n;k++)
     for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)
  {
            if(a[i][j]>biggest&&a[i][j]<big)
   {
                 biggest=a[i][j];
                 travstack.push(i);
                 travstack.push(j);
   }
           big=a[i][j];
  }
 for(i=0;i<n;i++)
     for(j=0;j<n;j++)
  {
         int p1,p2;
         p1=travstack.top();//p1=j
         travstack.pop();
         p2=travstack.top();//p2=i
         travstack.pop();
         if(b[p1][p2]==0)
   {
            b[p1][p2]=1;
            b[p2][p1]=1;
            c[p2][p1]=a[p2][p1];
            if(d[p1]==0&&d[p2]==0)
              d[p1]=d[p2]=1;
  
            else if(d[p1]==0)
   {
              d[p1]=1;
              for( i=0;i<n;i++)
     {
                 if(b[p2][i]==1)
     {
                    b[p1][i]=1;
                    b[i][p1]=1;
     }
     }
   }
           else if(d[p2]==0)
     {
              d[p2]=1;
              for(i=0;i<n;i++)
     {
                 if(b[p1][i]==1)
     {
                    b[p2][i]=1;
                    b[i][p2]=1;
     }
     }
     }
   }
  }
  for(i=0;i<n;i++)
  {
      for(j=i+1;j<n;j++)
      cout<<"c[i][j]="<<c[i][j];
      cout<<endl;
      for(int k=0;k<n;k++)
      cout<<"*";
 }
 return 0;
}

posted on 2008-06-03 17:06 星空 阅读(1385) 评论(1)  编辑 收藏 引用

评论

# re: kruskal算法实现  回复  更多评论   

需要的输入什么样的数据啊?

怎么就没结果啊?

QQ:396886380
Email:jhm3305@163.com
2009-12-26 11:08 | jhm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理