最小生成树dlg.cpp

这是用VC实现的一个查找最小生成树的程序

// 最小生成树Dlg.cpp : implementation file
//

#include "stdafx.h"
#include "最小生成树.h"
#include "最小生成树Dlg.h"
#include "math.h"
#include "stdio.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMyDlg dialog

CMyDlg::CMyDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CMyDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CMyDlg)
	m_qidian = 0;
	m_quanzhi = 0.0f;
	m_zhongdian = 0;
	m_chushidian = 0;
	//m_number = 0.0f;
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CMyDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CMyDlg)
	DDX_Text(pDX, IDC_EDIT1, m_qidian);
	DDV_MinMaxInt(pDX, m_qidian, 1, 10);
	DDX_Text(pDX, IDC_EDIT5, m_quanzhi);
	DDX_Text(pDX, IDC_EDIT2, m_zhongdian);
	DDV_MinMaxInt(pDX, m_zhongdian, 1, 10);
	DDX_Text(pDX, IDC_EDIT3, m_chushidian);
	DDV_MinMaxInt(pDX, m_chushidian, 1, 10);
	//DDX_Text(pDX, IDC_EDIT4, m_number);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CMyDlg, CDialog)
	//{{AFX_MSG_MAP(CMyDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_BUTTON5, OnButton5)
	ON_BN_CLICKED(IDC_BUTTON4, OnButton4)
	ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
	ON_BN_CLICKED(IDC_BUTTON2, OnButton2)
	ON_BN_CLICKED(IDC_BUTTON3, OnButton3)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMyDlg message handlers

BOOL CMyDlg::OnInitDialog()
{	
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here


	return TRUE;
	// return TRUE  unless you set the focus to a control
}

void CMyDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CMyDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}

	int i,j;
	CClientDC dc(this);
    dc.RoundRect(25,30,590,460,4,4);
  
	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++)                 //对邻接矩阵的初始化，将其每个元素都赋
	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.arcs[1][2].adj=2.0;g.arcs[2][1].adj=2.0;
   g.arcs[1][3].adj=1.0;g.arcs[3][1].adj=1.0;
   g.arcs[1][5].adj=3.0;g.arcs[5][1].adj=3.0;
   g.arcs[2][7].adj=5.0;g.arcs[7][2].adj=5.0;
   g.arcs[3][4].adj=4.0;g.arcs[4][3].adj=4.0;
   g.arcs[4][6].adj=4.5;g.arcs[6][4].adj=4.5;
   g.arcs[6][7].adj=8.0;g.arcs[7][6].adj=8.0;
   g.arcs[6][10].adj=6.0;g.arcs[10][6].adj=6.0;
   g.arcs[7][9].adj=3.5; g.arcs[9][7].adj=3.5;
   g.arcs[8][10].adj=4.0;g.arcs[10][8].adj=4.0;
   g.arcs[9][10].adj=2.5;g.arcs[10][9].adj=2.5;
*/    
   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);
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CMyDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

void CMyDlg::OnButton5() 
{
    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++)                 //对邻接矩阵的初始化，将其每个元素都赋最大的整数；
	for(j=1;j<=10;j++)                 
          g.arcs[i][j].adj=32767;