📄 图的深度优先搜索算法view.cpp

📁 图的深度优先算法动态演示
💻 CPP
字号:
// 图的深度优先搜索算法View.cpp : implementation of the CMyView class
//

#include "stdafx.h"
#include "图的深度优先搜索算法.h"

#include "图的深度优先搜索算法Doc.h"
#include "图的深度优先搜索算法View.h"
#include <list>

#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<V_Count; 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(y<=pPointTo->y)
		{		
			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; x<=pPointTo->x; x++,y++ )
		{
			DRAW( x , y, color ); 
		}
	}
	else
	if( dy < dx && dy > 0 )//0<k<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;
				x++;
			}
			else
			{
				d += dy - dx;
				x++;
				y++;
			}

			DRAW( x, y, color );
		}
	}
	else
	if ( dy == 0 )
	{
		for( INT x = pPointFrom->x; x<=pPointTo->x; x++ )
		{
			DRAW( x, pPointFrom->y, color );
		}
	}
	if( dy < 0 && dy > -dx )//-1<k<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;
				x++;
			}
			else
			{
				d += dy + dx;
				x++;
				y--;
			}
			DRAW( x, y, color );
		}
	}
	else
	if( dy == -dx )
	{
		for( INT x = pPointFrom->x, y = pPointFrom->y; x<=pPointTo->x; 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<k<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 == 0 )
	{
		for( INT x = pPointFrom->x; x<=pPointTo->x; x-- )
		{
			DRAW( x, pPointFrom->y, color );
		}
	}
	if( dy < 0 && dy > -dx )//-1<k<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 == -dx )
	{
		for( INT x = pPointFrom->x, y = pPointFrom->y; x<=pPointTo->x; 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 += -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<V_Count; 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<V_Count; 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
💿 文件大小 204 K
👤 上传用户 KuFly
📂 所属分类其他
🏷️ 相关标签

#算法 #动态
⌨️ 快捷键说明

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