zuixiaozhangshu.cpp

最小张树分类法 作最小张树(可考虑按距离给出权值) 在最张树上,确定该树的直径,并标出直径上各点的深度. 绘制直径上个点深度图,由深度图包括找出局部最小值. 去掉局部最小值的点,获得分离的二类

#include <iostream.h>
#include <math.h>
const int N=10; 
float s[2][N]={{0,1,2,1,3,6,5,8,10,12},
{0,0,1,2,1,4,5,9,9,10}};
float D[N][N],DT[N][N],LDT[N][N];
float temp;
int i,j,k;

void minispantree_prim(float gn[N][N],float DT[N][N],float bl[N][N],int u0)
 /* 从u0出发构造网gn的最小生成树，按普里姆算法输出生成树上各条边 */
{
	struct node  {  int vex;
                  float lowcost;
               } closedge[N];
  for(i=0;i<N;i++)
	  for (j=0;j<N;j++)
		  bl[i][j]=90;
   for (int v=1;v<N;v++)
    {closedge[v].vex=u0;
     closedge[v].lowcost=gn[u0][v];
   };
  closedge[u0].lowcost=0;    // 辅助数组初始化
for ( i=0;i<N-1;i++ )  // 只需N-1条边 
  {// k = minimun(closedge);
   k=1;
   float val=999;
   for(int v=1;v<N;v++)
   if (closedge[v].lowcost>0 && closedge[v].lowcost<val)
   { k=v; val=closedge[v].lowcost;}     
//求minimum函数求得K值,使closedge[k].lowcost=MIN{closedge[v].lowcost}
//closedge[v].lowcost>0,v V-U}, 函数minimun()求得k值,达到某种极小 
     DT[closedge[k].vex][k]=DT[k][closedge[k].vex]=val; 
	 bl[closedge[k].vex][k]=bl[k][closedge[k].vex]=1;
   /*  记录生成树的边  */
     closedge[k].lowcost=0;   /*  顶点k并入U集  */
     for (v=0;v<N; v++)
        if ( (closedge[v].lowcost>0)&&(gn[k][v]<closedge[v].lowcost))
                 { closedge[v].lowcost=gn[k][v];closedge[v].vex=k;}
        /*  在新的顶点并集合以后，重新选择具有最小代价的边  */
   }      
 }    
void floyd(float a[N][N],float c[N][N],int path[N][N])
//c 为邻接矩阵
{int i,j,k;
 for(i=0;i<N;i++)
  for(j=0;j<N;j++) /*初始化*/
   {a[i][j]=c[i][j]; /*置a数组 */
    path[i][j]=j; /*path全初始化为0 */
   }
 for(i=0; i<N;i++)
     a[i][i]=0; /*主对角线置0，顶点自己到自己的长度为0*/
 for(k=0;k<N;k++)
    for(i=0;i<N;i++)
      for(j=0;j<N;j++)
        if (a[i][k]+a[k][j]<a[i][j])
          { a[i][j]=a[i][k]+a[k][j];
            path[i][j]=path[i][k]; 
			//i的直接后继为k
          }
}
void main(void)
{ int k=0;
  int h=0;
  float tp=0;
  float LDT[N][N];
  float LTDT[N][N];
float LLTDT[N][N];
  int Lpath[N];
  float boola[N][N];
  float b[N][N];
  float TREE90[N][N];
  int pp[N][N];
  int ppp;
  int width[N];
  int l=0;
  int next; 
  int p[N][N];
  cout<<"first\n";
  for (i=0;i<N;i++)
   for(j=1;j<N;j++)
   {float ft=(float)sqrt((s[0][i]-s[0][j])*(s[0][i]-s[0][j])+(s[1][i]-s[1][j])*(s[1][i]-s[1][j]));
    D[i][j]=ft;D[j][i]=ft;   
	}//qiuchu adjacent matrix
   cout<<"D: \n";
   for (i=0;i<N;i++)
   {for(j=0;j<N;j++)
	   cout<<D[i][j]<<"  ";
     cout<<"\n";
   }
   minispantree_prim(D,DT,boola,0);
   //求出最小生成树并存入DT[N][N]，逻辑树boola[N][N],非树枝存90
   cout<<"最小生成树DT:\n";
   for (i=0;i<N;i++)
   {for(j=0;j<N;j++)
	   cout<<DT[i][j]<<"  ";
    cout<<"\n";
   }
   cout<<"boola:\n";
   for (i=0;i<N;i++)
   {for(j=0;j<N;j++)
     cout<<boola[i][j]<<"  ";
    cout<<"\n";
   }
   for(i=0;i<N;i++)
     for(j=0;j<N;j++)
	  TREE90[i][j]=boola[i][j];
      
  for(i=0;i<N;i++)
   for(j=0;j<N;j++)
	   LTDT[i][j]=LDT[i][j]=DT[i][j]; //LTDT作临时保存用
cout<<"最小生成树LDT=DT \n";
   for (i=0;i<N;i++)
   {for(j=0;j<N;j++)
      cout<<LDT[i][j]<<"  ";
    cout<<"\n";
   }
    
  for (i=0;i<N;i++)
     for(j=0;j<N;j++)
       if(LDT[i][j]>tp){tp=LDT[i][j];k=i;h=j;}
  cout<<tp<<" maxpoint no useful "<<(k+1)<<" "<<(h+1)<<" \n";
  cout<<"准备求任意两点间的最小距离,LTDT转化为逻辑树，点间无边时置90 :\n";  
  
  /*for (i=0;i<N;i++)
     for(j=0;j<N;j++)
       if(LTDT[i][j]>0) LTDT[i][j]=1;else LTDT[i][j]=90;
   
   for (i=0;i<N;i++)
   {for(j=0;j<N;j++)
     cout<<LTDT[i][j]<<"  ";
    cout<<"\n";
   }*/
   //求出任意两点间的最短距离存入矩阵LLTDT[N][N]
   floyd(LLTDT,boola,p);//
	cout<<"求生成树中任意两点间的最小距离放入LLTDT:\n";
	for (i=0;i<N;i++)
     for(j=0;j<N;j++)
       if(LLTDT[i][j]>90) LLTDT[i][j]=0;
   for (i=0;i<N;i++)
   {for(j=0;j<N;j++)
      cout<<LLTDT[i][j]<<"  ";
    cout<<"\n";
   }
   //扫描LLTDT中最大边所在位置（k，h）,Lpath[N]存放其路径，即最大直径
   tp=0;
	k=0; 
	h=0;
	for (i=0;i<N;i++)
     for(j=0;j<N;j++)
       if(LLTDT[i][j]>tp){tp=LLTDT[i][j];k=i;h=j;}
      //找出最长的路径，即直径（树中的）
	cout<<"\n输出直径长及其上的各点:\n";
	cout<<"直径长:"<<tp<<" 两个端点: "<<(k+1)<<"和 "<<(h+1)<<" \n";
Lpath[0]=k;
	 l=0;
	 next=p[k][h];     /* next为起点的直接后继 */
     if (next==0) cout<<"no path\n";
	 else
	 {while (next!=h)
		{l++;Lpath[l]=next;
         next=p[next][h];  /* 继续找下一个直接后继 */
		}
	   l++;Lpath[l]=h;}
	 cout<<"\n直径上的各点:\n";
	 for(i=0;i<=l;i++) cout<<Lpath[i]<<" ";
     cout<<"\n";
// 将直径中的点存入Lpath
//再求出直径上每一点的宽度
  cout<<"boola:\n";
  for(i=0;i<N;i++)
  { for(j=0;j<N;j++)
	  cout<<boola[i][j]<<" ";
    cout<<"\n";
  } 
  cout<<"ooooo\n";
  //boola[][]中存放的是树支和其他大的值，把树上直径中点间距离置为90，
  //即不希望直径上的边参与计算最小距离
cout<<"\n";
for(i=0;i<=l;i++)
   for(j=0;j<=l;j++)
	  LTDT[Lpath[i]][Lpath[j]]=boola[Lpath[i]][Lpath[j]]=90;
    
cout<<"\n显示pppppp boola:+90\n";
for(i=0;i<N;i++)
  { for(j=0;j<N;j++)
	  cout<<boola[i][j]<<" ";
    cout<<"\n";
  }
cout<<"llll\n";
floyd(b,boola,pp);
cout<<"b为不含直径上的点间距离的任意两点间的最小长度:\n";
for(i=0;i<N;i++)
  { for(j=0;j<N;j++)
	  cout<<b[i][j]<<" ";
    cout<<"\n";
  }
//再求出不包括最长直径在内，生成树上任意两点的最小距离。
//距离大的(999)的边不计算在内?
for(i=0;i<N;i++)
  for(j=0;j<N;j++)
	  if(b[i][j]>=90) b[i][j]=0;
cout<<"输出b-90,是去掉最大值后，不含直径上点之间的最小长度:\n";   
for(i=0;i<N;i++)
  { for(j=0;j<N;j++)
	  cout<<b[i][j]<<" ";
    cout<<"\n";
  }
cout<<"hhhhyhyh\n";
cout<<"直径上每点的宽度???:b中存放的是不含直径在内的任意两点间的最小距离\n";
for (j=0;j<l;j++)
{  int tmp=0;
   for(i=0;i<N;i++)
     if (b[Lpath[j]][i]>tmp)tmp=(int)b[Lpath[j]][i];
   width[j]=(int)tmp;
}
cout<<"\n直径上每个点:\n";
for (j=0;j<l;j++)
  cout<<Lpath[j]<<" ";
cout<<"\n直径上每点的宽度:\n";
for (j=0;j<l;j++)
  cout<<width[j]<<" ";
cout<<"\n";
  //由k到h,对直径上的每点扫描，求出局部最小，并加以分断
//ppp=width[0];
i=1;
while (i<=l) 
{//ppp=width[Lpath[i]];
	if	((width[Lpath[i-1]]-width[Lpath[i]])>=1) break;
 else i++;
}
cout<<"TREE90-断点\n";
TREE90[Lpath[i-1]][Lpath[i]]=TREE90[Lpath[i]][Lpath[i-1]]=90;
k=i;
h=i+1;
for(i=0;i<N;i++)
  { for(j=0;j<N;j++)
	  cout<<TREE90[i][j]<<" ";
    cout<<"\n";
  }
cout<<"两断点"<<k+1<<"---"<<h+1<<"\n";
int pa[N][N];
float dd[N][N];
floyd(dd,TREE90,pa);//重新求树上任意两点之间的距离
cout<<"dd: \n";
for(i=0;i<N;i++)
  { for(j=0;j<N;j++)
	  cout<<dd[i][j]<<" ";
    cout<<"\n";
  }  

cout<<"first center "<<k+1<<":";//第一个中心k+1,所有与k+1相通的点为一类，
for (j=0;j<N;j++)
  if (dd[j][k]<90) cout<<j+1<<" ";
cout<<"\n";
cout<<"second center "<<h+1<<":";//第二个中心
for (j=0;j<N;j++)
  if (dd[j][h]<90)cout<<j+1<<" ";
//所有与h+1相通的点属于另一类（在树上）。
   cout<<"\n";
}