wuxiangwang.txt

无向网生成最小树

无向网--最小生成树 
 #include<iostream.h>
#include<stdlib.h>
const int SEED=8998;
const int MAX=32678;
const int N=8;
int begin;
int A[N][N];
struct node
{
 int flag;//标记是否已被访问
 int degree;//该节点的孩子数
 int lelt;//左孩子的下标
 int right;//右孩子的下标
}T[N];//存N个节点
struct btree
{
 int node;
 btree *left;
 btree *right;
}*B;
void Init()
{
 srand(SEED);
 int i;
 int j;
 for(i=0;i<N;i++)
  cout<<'\t'<<i;
 cout<<endl;
 for(i=0;i<N;i++)
 {
  cout<<i<<"'\t";
  for(j=0;j<N;j++)
  {
   A[i][j]=rand()%200;
   cout<<A[i][j]<<'\t';
  }
  cout<<endl;
 }
  for(i=0;i<N;i++)
  {
   T[i].degree=T[i].flag=0;
   T[i].lelt=T[i].right=-1;
  }
}
int Min_value()
{
 int i;
 int j;
 int Begin=-1;
 int value=MAX;
 for(i=0;i<N;i++)
  for(j=0;j<N;j++)
  {
   if(A[i][j]<value)
   {
    value=A[i][j];
    Begin=i;
   }
  }
  return Begin;
}
int Next_min_value(int i,int &j)
{
 int value=MAX;
 int k;
 for(k=0;k<N;k++)
 {
  if(T[k].flag==0)
  {
   if(A[i][k]<value)
   {
    value=A[i][k];
    j=k;
   }
  }
 }
 return value;
}
void Min_btree()
{
 begin=Min_value();
 T[begin].flag=1;
 int i;
 int j;
 int jj;
 int k;
 int kk;
 int min;
 int value;
 i=0;
 while(i<N)
 {
  value=MAX;
  k=-1;
  for(jj=0;jj<N;jj++)
   if(T[jj].flag==1&&T[jj].degree!=2)
   {
    min=Next_min_value(jj,kk);
    if(min<value)
    {
     value=min;
     k=kk;
     j=jj;
    }
   }
   if(k>=0)
   {
    if(T[j].degree==0)
     T[j].lelt=k;
    else
     T[j].right=k;
    T[j].degree++;
    T[k].flag=1;
   
   }
   i++;
 }
}
void Creat_btree(btree *&B,int i,int degree)
{
 B=new btree;
 B->left=B->right=0;
 B->node=i;
 btree *p;
 p=B;
 int l=T[i].lelt;
 int r=T[i].right;
 if(l>=0)
  Creat_btree(p->left,l,1);
 if(r>=0)
  Creat_btree(p->right,r,2);
}
void Print_btree(btree *B)
{
 if(B)
 {
  cout<<B->node<<"(";
  Print_btree(B->left);
  cout<<",";
  Print_btree(B->right);
  cout<<")";
 }
}
void main()
{
 Init();
 Min_btree();
 Creat_btree(B,begin,0);
 cout<<" The min btree is : \n  ";
 Print_btree(B);
 cout<<endl;
}