// 图的深度优先搜索算法View.cpp : implementation of the CMyView class
//
#include "stdafx.h"
#include "图的深度优先搜索算法.h"
#include "图的深度优先搜索算法Doc.h"
#include "图的深度优先搜索算法View.h"
#include
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
/////////////////////////////////////////////////////////////////////////////
// CMyView
IMPLEMENT_DYNCREATE(CMyView, CView)
BEGIN_MESSAGE_MAP(CMyView, CView)
//{{AFX_MSG_MAP(CMyView)
// NOTE - the ClassWizard will add and remove mapping macros here.
// DO NOT EDIT what you see in these blocks of generated code!
//}}AFX_MSG_MAP
// Standard printing commands
ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)
ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)
ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CMyView construction/destruction
CMyView::CMyView()
{
// TODO: add construction code here
}
CMyView::~CMyView()
{
}
BOOL CMyView::PreCreateWindow(CREATESTRUCT& cs)
{
// TODO: Modify the Window class or styles here by modifying
// the CREATESTRUCT cs
return CView::PreCreateWindow(cs);
}
/////////////////////////////////////////////////////////////////////////////
// CMyView drawing
CPoint g_V[] = { CPoint( 235, 370 ), CPoint( 120, 300 ), CPoint( 20, 200 ),
CPoint( 100, 80 ), CPoint( 170, 180 ), CPoint( 270, 280 ),
CPoint( 440, 300 ), CPoint( 550, 370 ), CPoint( 200, 20 ),
CPoint( 300, 90 ), CPoint( 480, 170 ), CPoint( 500, 270 ),
CPoint( 400, 20 ), CPoint( 600, 190 ), CPoint( 350, 175 ) };
typedef enum { VISITED, UNVISITED } BVISITED;
bool g_ShouldSleep = true;
ULONG g_ulVisitOrder;
class CNode{
private:
CPoint *m_pPoint;
std::list< CNode* > *m_pNeighbourhood_List;
BVISITED m_bVisited;
public:
void SetPoint( CPoint & Point ) { m_pPoint = &Point; }
void SetNeighbourhoodList( std::list< CNode* > & NeighbourhoodList )
{
m_pNeighbourhood_List = &NeighbourhoodList;
}
friend void Graphics_Visit( CNode & Root, CDC *pDC );
friend void Pre_Visit( CPoint V[], ULONG V_Count, std::list< CNode*> Neighbourhood_List[], CDC *pDC );//周游之前做一些初始化工作
friend void Visit( CNode *NodeFrom, CNode *NodeTo, CDC *pDC );
};
std::list< CNode* > g_Neighbourhood_List [ sizeof(g_V)/sizeof(CPoint) ];
#define R 7
CNode g_Node[ sizeof(g_V)/sizeof(CPoint) ];
void MySleep( DWORD dwMiliSeconds )
{
if( g_ShouldSleep )
{
Sleep( dwMiliSeconds );
}
}
void Initialize( CNode N[], ULONG V_Count, std::list< CNode*> Neighbourhood_List[] )
{
for( ULONG i=0; i {
g_Node[i].SetPoint( g_V[i] );
g_Node[i].SetNeighbourhoodList( g_Neighbourhood_List[i] );
}
Neighbourhood_List[0].push_back( &N[1] );
Neighbourhood_List[0].push_back( &N[5] );
Neighbourhood_List[0].push_back( &N[7] );
Neighbourhood_List[1].push_back( &N[0] );
Neighbourhood_List[1].push_back( &N[2] );
Neighbourhood_List[1].push_back( &N[3] );
Neighbourhood_List[1].push_back( &N[4] );
Neighbourhood_List[2].push_back( &N[1] );
Neighbourhood_List[3].push_back( &N[1] );
Neighbourhood_List[4].push_back( &N[1] );
Neighbourhood_List[4].push_back( &N[8] );
Neighbourhood_List[5].push_back( &N[0] );
Neighbourhood_List[5].push_back( &N[6] );
Neighbourhood_List[5].push_back( &N[8] );
Neighbourhood_List[5].push_back( &N[14] );
Neighbourhood_List[6].push_back( &N[5] );
Neighbourhood_List[6].push_back( &N[10] );
Neighbourhood_List[6].push_back( &N[11] );
Neighbourhood_List[6].push_back( &N[14] );
Neighbourhood_List[7].push_back( &N[0] );
Neighbourhood_List[7].push_back( &N[13] );
Neighbourhood_List[7].push_back( &N[11] );
Neighbourhood_List[8].push_back( &N[4] );
Neighbourhood_List[8].push_back( &N[5] );
Neighbourhood_List[8].push_back( &N[9] );
Neighbourhood_List[8].push_back( &N[14] );
Neighbourhood_List[9].push_back( &N[8] );
Neighbourhood_List[9].push_back( &N[10] );
Neighbourhood_List[9].push_back( &N[12] );
Neighbourhood_List[9].push_back( &N[14] );
Neighbourhood_List[10].push_back( &N[6] );
Neighbourhood_List[10].push_back( &N[9] );
Neighbourhood_List[10].push_back( &N[11] );
Neighbourhood_List[10].push_back( &N[14] );
Neighbourhood_List[11].push_back( &N[6] );
Neighbourhood_List[11].push_back( &N[10] );
Neighbourhood_List[11].push_back( &N[7] );
Neighbourhood_List[12].push_back( &N[9] );
Neighbourhood_List[12].push_back( &N[13] );
Neighbourhood_List[13].push_back( &N[7] );
Neighbourhood_List[13].push_back( &N[12] );
Neighbourhood_List[14].push_back( &N[5] );
Neighbourhood_List[14].push_back( &N[6] );
Neighbourhood_List[14].push_back( &N[8] );
Neighbourhood_List[14].push_back( &N[9] );
Neighbourhood_List[14].push_back( &N[10] );
}
void DrawLine( CPoint PointFrom, CPoint PointTo, COLORREF color, CDC *pDC )
{
#define DRAW( x, y, color ) { MySleep(10); pDC->SetPixel( x, y, color ); }
CPoint *pPointFrom, *pPointTo;
PointFrom.x < PointTo.x ? ( pPointFrom = &PointFrom, pPointTo = &PointTo) :
( pPointFrom = &PointTo, pPointTo = &PointFrom );
INT dy = pPointTo->y - pPointFrom->y;
INT dx = pPointTo->x - pPointFrom->x;
double d;
INT x,y;
if( dx == 0 )
{
ASSERT( dx!=0 );
}
if ( dy>dx )//k>1
{
x = pPointFrom->x;
y = pPointFrom->y;
d = dy*(x+0.5) - dx*(y+1) - dy*pPointFrom->x + dx * pPointFrom->y;
while(yy)
{
if( d < 0 )
{
d += dy - dx;
y++;
x++;
}
else
{
d += -dx;
y++;
}
DRAW( x, y, color );
}
}
else
if( dy == dx )//k==1
{
for( INT x = pPointFrom->x, y = pPointFrom->y; xx; x++,y++ )
{
DRAW( x , y, color );
}
}
else
if( dy < dx && dy > 0 )//0 {
x = pPointFrom->x;
y = pPointFrom->y;
d = dy*(x+1) - dx*(y+0.5) - dy*pPointFrom->x + dx * pPointFrom->y;
while(xx)
{
if( d < 0 )
{
d += dy;
x++;
}
else
{
d += dy - dx;
x++;
y++;
}
DRAW( x, y, color );
}
}
else
if ( dy == 0 )
{
for( INT x = pPointFrom->x; xx; x++ )
{
DRAW( x, pPointFrom->y, color );
}
}
if( dy < 0 && dy > -dx )//-1 {
x = pPointFrom->x;
y = pPointFrom->y;
d = dy*(x+1) - dx*(y-0.5) - dy*pPointFrom->x + dx * pPointFrom->y;
while(xx)
{
if( d > 0 )
{
d += dy;
x++;
}
else
{
d += dy + dx;
x++;
y--;
}
DRAW( x, y, color );
}
}
else
if( dy == -dx )
{
for( INT x = pPointFrom->x, y = pPointFrom->y; xx; x++,y-- )
{
DRAW( x , y, color );
}
}
else
if( dy < -dx )
{
x = pPointFrom->x;
y = pPointFrom->y;
d = dy*(x+0.5) - dx*(y-1) - dy*pPointFrom->x + dx * pPointFrom->y;
while( y>=pPointTo->y )
{
if( d > 0 )
{
d += dy + dx;
y--;
x++;
}
else
{
d += dx;
y--;
}
DRAW( x, y, color );
}
}
#undef DRAW
}
void DrawDirectedLine( CPoint PointFrom, CPoint PointTo, COLORREF color, CDC *pDC )
{
if( PointFrom.x < PointTo.x )
{
DrawLine( PointFrom, PointTo, color, pDC );
return;
}
#define DRAW( x, y, color ) { MySleep(10); pDC->SetPixel( x, y, color ); }
CPoint *pPointFrom = &PointFrom, *pPointTo = &PointTo;
INT dy = -pPointTo->y + pPointFrom->y;
INT dx = -pPointTo->x + pPointFrom->x;
double d;
INT x,y;
if( dx == 0 )
{
ASSERT( dx!=0 );
}
if ( dy>dx )//k>1
{
x = pPointFrom->x;
y = pPointFrom->y;
d = dy*(x-0.5) - dx*(y-1) - dy*pPointFrom->x + dx * pPointFrom->y;
while(y>=pPointTo->y)
{
if( d < 0 )
{
d += dx;
y--;
}
else
{
d += dx - dy;
y--;
x--;
}
DRAW( x, y, color );
}
}
else
if( dy == dx )//k==1
{
for( INT x = pPointFrom->x, y = pPointFrom->y; x>=pPointTo->x; x--,y-- )
{
DRAW( x , y, color );
}
}
else
if( dy < dx && dy > 0 )//0 {
x = pPointFrom->x;
y = pPointFrom->y;
d = dy*(x-1) - dx*(y-0.5) - dy*pPointFrom->x + dx * pPointFrom->y;
while(x>=pPointTo->x)
{
if( d < 0 )
{
d += -dy+dx;
x--;
y--;
}
else
{
d += -dy;
x--;
}
DRAW( x, y, color );
}
}
else
if ( dy == 0 )
{
for( INT x = pPointFrom->x; xx; x-- )
{
DRAW( x, pPointFrom->y, color );
}
}
if( dy < 0 && dy > -dx )//-1 {
x = pPointFrom->x;
y = pPointFrom->y;
d = dy*(x-1) - dx*(y+0.5) - dy*pPointFrom->x + dx * pPointFrom->y;
while(x>=pPointTo->x)
{
if( d > 0 )
{
d += -dy-dx;
x--;
y++;
}
else
{
d += -dy;
x--;
}
DRAW( x, y, color );
}
}
else
if( dy == -dx )
{
for( INT x = pPointFrom->x, y = pPointFrom->y; xx; x--,y++ )
{
DRAW( x , y, color );
}
}
else
if( dy < -dx )
{
x = pPointFrom->x;
y = pPointFrom->y;
d = dy*(x-0.5) - dx*(y+1) - dy*pPointFrom->x + dx * pPointFrom->y;
while( yy )
{
if( d > 0 )
{
d += -dx;
y++;
}
else
{
d += -dx - dy;
y++;
x--;
}
DRAW( x, y, color );
}
}
#undef DRAW
}
void Pre_Visit( CPoint V[], ULONG V_Count, std::list< CNode*> Neighbourhood_List[], CDC *pDC )//周游之前做一些初始化工作
{
for( UINT i = 0; i {
g_Node[i].m_bVisited = UNVISITED;
for( std::list< CNode* >::iterator iter = Neighbourhood_List[i].begin();
iter != Neighbourhood_List[i].end(); iter++ )
{
pDC->MoveTo( V[i] );
pDC->LineTo( *((**iter).m_pPoint) );
}
}
for( i = 0; i {
pDC->Ellipse( CRect( V[i].x-R, V[i].y+R, V[i].x+R, V[i].y-R ) );
}
}
void Visit( CNode *NodeFrom, CNode *NodeTo, CDC *pDC )
{
MySleep( 500 );
CBrush Brush( RGB ( 0, 128, 0) );
pDC->SelectObject( &Brush );
if( NodeFrom )
{
NodeFrom->m_pPoint->y++, NodeTo->m_pPoint->y++;
DrawDirectedLine( *NodeFrom->m_pPoint, *NodeTo->m_pPoint, RGB( 0, 0, 255), pDC );
NodeFrom->m_pPoint->y--, NodeTo->m_pPoint->y--;
}
pDC->Ellipse( CRect( NodeTo->m_pPoint->x-R, NodeTo->m_pPoint->y+R, NodeTo->m_pPoint->x+R, NodeTo->m_pPoint->y-R ) );
char temp[100];
//pDC->DrawText( ltoa( g_ulVisitOrder++, temp, 10 ), CRect( NodeTo->m_pPoint->x-R, NodeTo->m_pPoint->y+R, NodeTo->m_pPoint->x+R, NodeTo->m_pPoint->y-R ), DT_CENTER );
pDC->SetBkMode( TRANSPARENT );
pDC->TextOut( NodeTo->m_pPoint->x, NodeTo->m_pPoint->y, ltoa( g_ulVisitOrder++, temp, 10 ) );
}
void Graphics_Visit( CNode & Root, CDC *pDC )
{
std::list< CNode* > Queue;
Queue.push_front( &Root );
std::list< CNode* > FatherQueue;//这个队列不是周游算法需要的，设立此队列的目的是记录周游
//路径，便于显示
FatherQueue.push_front( NULL );//Root的Father是NULL
while( true )
{
if( Queue.empty() )
{
break;
}
else
{
CNode *CurrentNode = *Queue.begin();
CNode *pPreNode = *FatherQueue.begin();
Queue.pop_front();
FatherQueue.pop_front();
if( CurrentNode->m_bVisited == VISITED )
{
continue;
}
Visit( pPreNode, CurrentNode, pDC );
CurrentNode->m_bVisited = VISITED;
for( std::list< CNode* >::iterator iter = CurrentNode->m_pNeighbourhood_List->begin();
iter!=CurrentNode->m_pNeighbourhood_List->end(); iter++ )
{
Queue.push_front( *iter );
FatherQueue.push_front( CurrentNode );
}
}
}
}
class CInit//定义此类的唯一目的是在程序初始化的时候能够初始化邻接表
{
public:
CInit()
{
Initialize( g_Node, sizeof(g_V)/sizeof(CPoint), g_Neighbourhood_List );
}
} g_Init;
void CMyView::OnDraw(CDC* pDC)
{
CMyDoc* pDoc = GetDocument();
ASSERT_VALID(pDoc);
// TODO: add draw code for native data here
g_ulVisitOrder = 0;
Pre_Visit ( g_V, sizeof(g_V)/sizeof(CPoint), g_Neighbourhood_List, pDC );
Graphics_Visit( g_Node[0], pDC );
g_ShouldSleep = false;
}
/////////////////////////////////////////////////////////////////////////////
// CMyView printing
BOOL CMyView::OnPreparePrinting(CPrintInfo* pInfo)
{
// default preparation
return DoPreparePrinting(pInfo);
}
void CMyView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
// TODO: add extra initialization before printing
}
void CMyView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
// TODO: add cleanup after printing
}
/////////////////////////////////////////////////////////////////////////////
// CMyView diagnostics
#ifdef _DEBUG
void CMyView::AssertValid() const
{
CView::AssertValid();
}
void CMyView::Dump(CDumpContext& dc) const
{
CView::Dump(dc);
}
CMyDoc* CMyView::GetDocument() // non-debug version is inline
{
ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CMyDoc)));
return (CMyDoc*)m_pDocument;
}
#endif //_DEBUG
/////////////////////////////////////////////////////////////////////////////
// CMyView message handlers
