⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 最小生成树dlg.cpp

📁 这是用VC实现的一个查找最小生成树的程序
💻 CPP
📖 第 1 页 / 共 2 页
字号:
🔍
12 
   
    
    g.vexnum=10; 
        
    for(i=1;i<=g.vexnum;i++)
	     g.vexs[i].ver=i; 

	for(i=1;i<=10;i++)
	   for(j=1;j<=10;j++)
           if (i==j) g.arcs[i][j].adj=0;  
    g.vexnum=10;
	CString string;
    char cha;
	   for(i=1;i<=10;i++)	   
	   {  
		   if(i==10) 
				{string="10";dc.DrawText(string,CRect(tudian[i][3],tudian[i][4]+10,tudian[i][5],tudian[i][6]+10),DT_CENTER);}
	       else { cha=i+'0';
		         dc.DrawText(cha,CRect(tudian[i][3],tudian[i][4]+10,tudian[i][5],tudian[i][6]+10),DT_CENTER);
				}
	   }
	//m_number=g.vexnum;
	g.arcnum=0;
	m_chushidian=1;
	m_qidian=1;
	m_zhongdian=1;
	m_quanzhi=0.0;
	m_closechushi=0;


	UpdateData(FALSE);
	//输入默认的边及权值
    m_qidian=1;m_zhongdian=2;m_quanzhi=2;UpdateData(FALSE);OnButton4();
    m_qidian=1;m_zhongdian=3;m_quanzhi=1;UpdateData(FALSE);OnButton4();
    m_qidian=1;m_zhongdian=5;m_quanzhi=3;UpdateData(FALSE);OnButton4();
    m_qidian=7;m_zhongdian=2;m_quanzhi=5;UpdateData(FALSE);OnButton4();
    m_qidian=3;m_zhongdian=4;m_quanzhi=4;UpdateData(FALSE);OnButton4();
    m_qidian=4;m_zhongdian=6;m_quanzhi=4.5;UpdateData(FALSE);OnButton4();
    m_qidian=6;m_zhongdian=7;m_quanzhi=8.0;UpdateData(FALSE);OnButton4();
    m_qidian=6;m_zhongdian=10;m_quanzhi=6;UpdateData(FALSE);OnButton4();
    m_qidian=7;m_zhongdian=9;m_quanzhi=3.5;UpdateData(FALSE);OnButton4();
    m_qidian=8;m_zhongdian=10;m_quanzhi=4;UpdateData(FALSE);OnButton4();
    m_qidian=9;m_zhongdian=10;m_quanzhi=2.5;UpdateData(FALSE);OnButton4();

}


void CMyDlg::OnButton4() 
{
  
  UpdateData(TRUE);
  
  if(m_quanzhi==0) MessageBox("权值不可以为零,请重新输入!");
  else if(m_qidian==m_zhongdian) MessageBox("当起点与终点相同时，其权值为零，谢谢！");
  else if((m_qidian>=1)&&(m_zhongdian>=1)&&(m_qidian<=10)&&(m_zhongdian>=1))
  {
     int big,i,k,j;
     float sma,sma2;
     char s[100];
     int wei;
     big=m_quanzhi;

  for(i=0;i<=8;i++)
		{
	      if(big>=pow(10,i));
	      else {k=i-1;i=9;}
		}

   i=0;
   while(k>=0)
   {
      s[i]=big/pow(10,k)+'0'; 
      j=big/pow(10,k);
      big=big-pow(10,k)*j;  
      i++;
      k--;
   }
  while(s[i-1]=='0')i--;
  
  big=m_quanzhi;
  sma=m_quanzhi-big;

  if(sma==0) k=0;
  else {k=3;s[i]='.';i++;}
  while(k>0)
	{ 
	   sma=sma*10;
	   big=sma;
	   sma=sma-big;
	   s[i]=big+'0';
	   i++;
	   k--;
	}
  
   s[i]='\0';i++;



  g.arcs[m_qidian][m_zhongdian].adj=m_quanzhi;
  g.arcs[m_zhongdian][m_qidian].adj=m_quanzhi;
  g.arcnum++;

  CClientDC dc(this);
  dc.MoveTo(tudian[m_qidian][1],tudian[m_qidian][2]);
  dc.LineTo(tudian[m_zhongdian][1],tudian[m_zhongdian][2]);
  i=(tudian[m_qidian][1]+tudian[m_zhongdian][1])/2; 
  k=(tudian[m_qidian][2]+tudian[m_zhongdian][2])/2;

  CString string;
  
  string=".......";
  CPen PenNew(PS_SOLID,1,RGB(0,100,255));
  CPen *pPenOld;
  pPenOld=dc.SelectObject(&PenNew);
  
  dc.RoundRect(i-30,k-10,i+30,k+10,4,4);
  dc.SelectObject(pPenOld);
  PenNew.DeleteObject();
  dc.DrawText(s,CRect(i-30,k-10,i+30,k+10),DT_CENTER);

  UpdateData(FALSE);
  //显示这条边

  }
  else MessageBox("输入错误，请重新输入");

  
}

void CMyDlg::OnButton1() 
{
  int j,i,k;     
 
  UpdateData(TRUE);
                       
  for(j=1;j<=g.vexnum;j++)
	{ if(j!=m_chushidian) 
		{closedge[j].adj.ver=m_chushidian;
         closedge[j].lowcost.adj=g.arcs[m_chushidian][j].adj;
		}
      else  {
		     closedge[m_chushidian].lowcost.adj=0;
			}
	} 
  m_closechushi=1;


 for(i=1;i<g.vexnum;i++)                                
 {
	k=minimum();                                       
                                                  
    //cout<<closedge[k].adj.ver<<"--->"<<g.vexs[k].ver<<endl;
	//m_number=k;
	UpdateData(FALSE);


	j=closedge[k].adj.ver;

    CClientDC dc(this);
	CPen PenNew(PS_SOLID,1,RGB(255,30,30));
	CPen *pPenOld;
	pPenOld=dc.SelectObject(&PenNew);
	dc.MoveTo(tudian[j][1],tudian[j][2]);
	dc.LineTo(tudian[k][1],tudian[k][2]);
	dc.SelectObject(pPenOld);
	PenNew.DeleteObject();

	closedge[k].lowcost.adj=0;
    for(j=1;j<=g.vexnum;j++)
	{   //   
		if(g.arcs[k][j].adj<closedge[j].lowcost.adj)
		{  closedge[j].adj=g.vexs[k];
		    closedge[j].lowcost.adj=g.arcs[k][j].adj;
		}
	}
 }

}

int CMyDlg::minimum()
{
	int i,j=0;
    int k=1;
    for(i=1;i<=10;i++)
	    if(closedge[i].lowcost.adj!=0){k=i;i=10; }

    for(i=1;i<=10;i++)
     	if(closedge[i].lowcost.adj!=0)j=1;
    if (j==0) return -1;

    for(i=1;i<=10;i++)
		{   if(closedge[i].lowcost.adj==0);
	     	else if((closedge[i].lowcost.adj<closedge[k].lowcost.adj)&&(closedge[i].lowcost.adj!=0)) k=i;
		}
    return k;
}

void CMyDlg::OnButton2() 
{ 
	int i,j,k;
    UpdateData(TRUE);
    if((m_chushidian>=1)&&(m_chushidian<=10))
	{
      if(m_closechushi==0)
      for(j=1;j<=g.vexnum;j++)
		{ if(j!=m_chushidian) 
			{
	     	    closedge[j].adj.ver=m_chushidian;
                closedge[j].lowcost.adj=g.arcs[m_chushidian][j].adj;
			}
      
	  else  {
		     closedge[m_chushidian].lowcost.adj=0;
			}
		} 
    m_closechushi=1;
 
    k=minimum();
	if(k!=-1)
		{
	      j=closedge[k].adj.ver;

          CClientDC dc(this);
	      CPen PenNew(PS_SOLID,1,RGB(255,30,30));
     	
	      CPen *pPenOld;
	      pPenOld=dc.SelectObject(&PenNew);
	      dc.MoveTo(tudian[j][1],tudian[j][2]);
	      dc.LineTo(tudian[k][1],tudian[k][2]);
	      dc.SelectObject(pPenOld);
	      PenNew.DeleteObject();

    
	      closedge[k].lowcost.adj=0;
          for(j=1;j<=g.vexnum;j++)
		  {   //   
	    	if(g.arcs[k][j].adj<closedge[j].lowcost.adj)
			{  
				closedge[j].adj=g.vexs[k];
		        closedge[j].lowcost.adj=g.arcs[k][j].adj;
			}
		  }	
		}else MessageBox("最小生成树已经建成。谢谢！");
	}
     
	else MessageBox("您输入的起始顶点不合法，请重新输入！");

}

void CMyDlg::OnButton3() 
{
 	 CClientDC dc(this);
     dc.RoundRect(25,30,590,460,4,4);

     int i,j;
  
	 CPen PenNew(PS_SOLID,1,RGB(0,255,100));
   
	 CPen *pPenOld;
    
	 pPenOld=dc.SelectObject(&PenNew);

	 dc.Ellipse(100,40,140,80);
	 dc.Ellipse(320,40,360,80);
	 tudian[1][1]=120;tudian[1][2]=60;
	 tudian[2][1]=340;tudian[2][2]=60;
	
     dc.Ellipse(40,100,80,140);
	 dc.Ellipse(440,100,480,140);
	 tudian[3][1]=60;tudian[3][2]=120;
	 tudian[4][1]=460;tudian[4][2]=120;
	
	 dc.Ellipse(40,220,80,260);
	 dc.Ellipse(390,200,430,240);
	 tudian[5][1]=60;tudian[5][2]=240;
	 tudian[6][1]=410;tudian[6][2]=220;

	 dc.Ellipse(140,320,180,360);
	 dc.Ellipse(400,320,440,360);
	 tudian[7][1]=160;tudian[7][2]=340;
	 tudian[8][1]=420;tudian[8][2]=340;

	 dc.Ellipse(160,400,200,440);
	 dc.Ellipse(300,390,340,430);
	 tudian[9][1]=180;tudian[9][2]=420;
	 tudian[10][1]=320;tudian[10][2]=410;

	 dc.SelectObject(pPenOld);
	 PenNew.DeleteObject();

	 for( i=1;i<=10;i++)
		for( j=3;j<=6;j++)
		{	
			if(j==3) tudian[i][j]=tudian[i][1]-20;
		    if(j==4) tudian[i][j]=tudian[i][2]-20;
			if(j==5) tudian[i][j]=tudian[i][1]+20;
			if(j==6) tudian[i][j]=tudian[i][2]+20;
		}

	 for(i=1;i<=10;i++)              //对邻接矩阵的初始化，将其每个元素都赋为32767，作为最大的数
	 for(j=1;j<=10;j++)              //最大的整数指；
          g.arcs[i][j].adj=32767;           
   
    
    g.vexnum=10; 
        
    for(i=1;i<=g.vexnum;i++)
	      g.vexs[i].ver=i; 

	 for(i=1;i<=10;i++)
	   for(j=1;j<=10;j++)
       if (i==j) g.arcs[i][j].adj=0;  
    g.vexnum=10;
	CString string;
    char cha;
	for(i=1;i<=10;i++)	   
	   {  
		  if(i==10) 
				{string="10";dc.DrawText(string,CRect(tudian[i][3],tudian[i][4]+10,tudian[i][5],tudian[i][6]+10),DT_CENTER);}
	      else { cha=i+'0';
		         dc.DrawText(cha,CRect(tudian[i][3],tudian[i][4]+10,tudian[i][5],tudian[i][6]+10),DT_CENTER);
				}
	   }
	//m_number=g.vexnum;
	g.arcnum=0;
	m_chushidian=1;
	m_qidian=1;
	m_zhongdian=1;
	m_quanzhi=0.0;
	m_closechushi=0;


	UpdateData(FALSE);
}
12

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -