prim040819dlg.cpp

这是一个用于计算最小生成树的程序。当人们逐个输入每条边的权

// PRIM040819Dlg.cpp : implementation file
//

#include "stdafx.h"
#include "PRIM040819.h"
#include "PRIM040819Dlg.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()

/////////////////////////////////////////////////////////////////////////////
// CPRIM040819Dlg dialog

CPRIM040819Dlg::CPRIM040819Dlg(CWnd* pParent /*=NULL*/)
	: CDialog(CPRIM040819Dlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CPRIM040819Dlg)
	m_BEGIN = 0;
	m_END = 0;
	m_COST = 0;
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);

	Init();
}

void CPRIM040819Dlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CPRIM040819Dlg)
	DDX_Text(pDX, IDC_EDIT1, m_BEGIN);
	DDX_Text(pDX, IDC_EDIT2, m_END);
	DDX_Text(pDX, IDC_EDIT3, m_COST);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CPRIM040819Dlg, CDialog)
	//{{AFX_MSG_MAP(CPRIM040819Dlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
	ON_BN_CLICKED(IDC_BUTTON2, OnButton2)
	ON_BN_CLICKED(IDC_BUTTON3, OnButton3)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CPRIM040819Dlg message handlers

BOOL CPRIM040819Dlg::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 CPRIM040819Dlg::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 CPRIM040819Dlg::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();
		DrawFrame();
				DrawGraph();
	}
}

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

void CPRIM040819Dlg::OnButton1() 
{
	// TODO: Add your control notification handler code here
	if(UpdateData() != TRUE) return ;
	AddEdge(m_BEGIN,m_END,m_COST);
	DrawEdge(m_BEGIN,m_END);
	Invalidate();

}


void CPRIM040819Dlg::Init()
{MyGraph.arcnum =0;
	MyGraph.vexnum =10;
	for(int i=1; i<=MyGraph.vexnum; i++)
	{
		MyGraph.vexs[i]=i;
		for(int j=1; j<=MyGraph.vexnum; j++)
		{
			MyGraph.matrix [i][j] = INF;
		}
	}

}

void CPRIM040819Dlg::DrawFrame()
{	CWnd *pWnd = GetDlgItem(IDC_PIC);
	CDC *pdc = pWnd->GetDC ();
	pdc->SelectStockObject(NULL_BRUSH);
	CRect rect;
	::GetClientRect(pWnd->m_hWnd , &rect);
	CPoint pt = rect.CenterPoint ();
	CPoint oldpt=pdc->SetViewportOrg(pt);
	int radius = rect.Width ()-35;
	radius = radius / 2;
	for(double angle=0.0; angle < 2*PI; angle += PI/5)
	{
		pdc->MoveTo (0, 0);
		CPoint temp((int)(radius * cos(angle)), (int)( radius * sin(angle)) );
		CRect cir(temp.x-15,temp.y-15,temp.x+15, temp.y+15);
		pdc->Ellipse (&cir);
		CString count(_T(""));
		count.Format("%d", (int)(angle/(PI/5))+1);
		pdc->DrawText(count, &cir, DT_SINGLELINE | DT_CENTER | DT_VCENTER );
	}
	pdc->SetViewportOrg(oldpt);
	pWnd->ReleaseDC(pdc);

}

void CPRIM040819Dlg::DrawGraph()
{int count=0;
	if(MyGraph.arcnum == 0 ) return; 
	for(int i=1; i<=MyGraph.vexnum ; i++)
	{
		for(int j=1; j<i; j++)
		{
			if(MyGraph.matrix [i][j] != INF)
			{
				DrawEdge(i,j);
				count++; 
			}
		}
	}

}

void CPRIM040819Dlg::DrawEdge(int start, int end)
{
CWnd *pWnd = GetDlgItem(IDC_PIC);
	CDC *pdc = pWnd->GetDC ();
	CRect rect;
	::GetClientRect(pWnd->m_hWnd , &rect);
	CPoint pt = rect.CenterPoint ();
	CPoint oldpt=pdc->SetViewportOrg(pt);
	int radius = rect.Width ()-35;
	radius = radius / 2;
	
	double angle=(double)(start-1)*(PI/5);
	CPoint pt1,pt2,ptText;
	pt1.x=(int)(radius*cos(angle) );
	pt1.y=(int)(radius*sin(angle) );
	pdc->MoveTo (pt1);
	angle=(double)(end-1)*(PI/5);
	pt2.x=(int)(radius*cos(angle) );
	pt2.y=(int)(radius*sin(angle) );
	pdc->LineTo (pt2);
	ptText.x= (int)( (pt2.x + 2*pt1.x)/3);
	ptText.y= (int)( (pt2.y + 2*pt1.y)/3);
	CString str;
	str.Format ("%d",MyGraph .matrix [start][end]);
	pdc->TextOut (ptText.x-7,ptText.y-7, str);
	pdc->SetViewportOrg (oldpt);
	pWnd->ReleaseDC (pdc);
}

void CPRIM040819Dlg::OnButton2() 
{
	// TODO: Add your control notification handler code here
	Init();
	DrawFrame();
	DrawGraph();
	Invalidate();

}

void CPRIM040819Dlg::AddEdge(int start, int end, int length)
{	if (start==end) 
	{
	AfxMessageBox("起点和终点不应该一样");
	return;
	}
	if(MyGraph.matrix [start][end] == INF) MyGraph.arcnum ++;
	MyGraph.matrix [start][end] = length;
	MyGraph.matrix [end][start] = length;

}

void CPRIM040819Dlg::OnButton3() 
{
	// TODO: Add your control notification handler code here
			MinSpanTree();

}

void CPRIM040819Dlg::MinSpanTree()
{				  	int k=StartVex();
		if(k==0) return;
	
	int i,j,minCost;
	for(j=1; j<=MyGraph.vexnum ; j++)
	{
		if(j != k)
		{
			MyCloseEdge[j].adjvex = k; 
			MyCloseEdge[j].lowcost =MyGraph.matrix [k][j];
		}
	}
	MyCloseEdge[k].lowcost =0;

	for(i=1; i<MyGraph.vexnum ; i++)
	{
	    minCost=INF;
		BOOL bflag = FALSE;
		for(j=1; j<=MyGraph.vexnum; j++)
		{
			
			if(MyCloseEdge[j].lowcost<minCost && MyCloseEdge[j].lowcost!=0)
			{
				minCost=MyCloseEdge[j].lowcost;
				k=j;
				bflag = TRUE;
			}//if
		}//for
		if(bflag== FALSE) 
		{
			//AfxMessageBox("求解最小生成树提前结束");
			return ;
		}
//画最小生成树
		DrawTree(MyCloseEdge[k].adjvex,k);
//修改MyCloseEdge数组
		MyCloseEdge[k].lowcost = 0;
		for(j=1; j<=MyGraph.vexnum ; j++)
		{
			if(MyGraph.matrix [k][j] < MyCloseEdge[j].lowcost )
			{
				MyCloseEdge[j].adjvex = k;
				MyCloseEdge[j].lowcost =MyGraph.matrix [k][j];
			}//if
		}//for
	}


}

int CPRIM040819Dlg::StartVex()
{for(int i=1; i<=MyGraph.vexnum ; i++)
	{
		for(int j=1; j<i ; j++)
			if(MyGraph.matrix [i][j] != INF) return MyGraph.vexs[j];
	}
	return 0;

}

void CPRIM040819Dlg::DrawTree(int start, int end)
{
CWnd *pWnd = GetDlgItem(IDC_PIC);
	CDC *pdc = pWnd->GetDC();

	CPen pen, *oldpen;
	pen.CreatePen (PS_SOLID,3, RGB(255,0,255));
	oldpen=pdc->SelectObject (&pen);
	CRect rect;
	::GetClientRect(pWnd->m_hWnd , &rect);
	CPoint pt = rect.CenterPoint ();
	CPoint oldpt=pdc->SetViewportOrg(pt);
	int radius = rect.Width ()-35;
	radius = radius / 2;
	
	double angle=(double)(start-1)*(PI/5);
	pdc->MoveTo ( (int)(radius*cos(angle)), (int)(radius*sin(angle) ) );
	angle=(double)(end-1)*(PI/5);
	pdc->LineTo ( (int)(radius*cos(angle)), (int)(radius*sin(angle) ) );
	
	pdc->SetViewportOrg (oldpt);
	pdc->SelectObject (oldpen);
	pWnd->ReleaseDC(pdc);
}