queue.h

BFS、DFS、有向图、无向图中的各种算法的实现

#define INFINITY 100000000
struct VerNode{
public:	
	CRect m_rect;
	struct VerNode* m_pnextver;
	struct ArcNode* m_pfirstarc;
	CString m_strname;
	BOOL m_bvisit;
	int m_nvisit;
};
struct ArcNode{ 
public:
	int info;
	struct VerNode* m_padjver;
	struct ArcNode* m_pnextarc;
};
typedef struct VerNode VerNode;
typedef struct ArcNode ArcNode;
///////////////////////////////////////////////////////
//class VerQueue:
class VerQueue
{
public:
	VerNode* m_phead;
	VerNode* m_prear;
	int m_nnum;
public:
	VerQueue();
	void EnQueue(CRect q);
	void DeQueue(CRect& q);
	VerNode* IsInQueue(CPoint p,CPoint& cp);
	CPoint ChagetoPoint(CRect rect);
	VerNode* DeleteVer(VerNode* pver);
	void EnQueue(VerNode node);
	void DeQueue(VerNode& node);
};

///////////////////////////////////////////////////////////
//class Graphic:
class Graphic
{
public:
	VerQueue* m_verqueue;
	int m_nver;
	int m_narc;	
	int m_nunit;
	int m_nvisit;
public:
	Graphic();
	void DeleteVer(VerNode* pnode);
	void DeleteArc(VerNode* pver,ArcNode* parc);
	void InsertArc(VerNode* pnode,VerNode *pend,int mark);
	BOOL IsNewArc(VerNode* pnode,VerNode* pend);
	void DisplayGraph(CDC* pdc,int type);
	CPoint ChagetoPoint(CRect rect);
	int GetArcNum(VerNode* pver);
	void DeleteArc(VerNode* pstart,VerNode* pend);
	VerNode* NameToPointer(CString name);
	int CalculateDu(VerNode* pver);
	int CalculateInDu(VerNode* pver);
	int CalculateOutDu(VerNode* pver);
	void DFSTraverse(CDC* pdc);
	void DFS(VerNode* pnode,CDC* pdc);
	void DFSTraverse();
	void DFS(VerNode* pnode);
	void BFSTraverse(CDC* pdc);
	void BFSTraverse();
	BOOL TestKeda(VerNode* start,VerNode* end);
	void TKD(VerNode* start,VerNode* end,int& mark);
	int XL(int x1,int y1,int x2,int y2);
	int YL(int x1,int y1,int x2,int y2);
	int XR(int x1,int y1,int x2,int y2);
	int YR(int x1,int y1,int x2,int y2);
	int	PointerToNum(VerNode* pnode);
	void ShortestPath(VerNode* pstart,BOOL** p);
};

//////////////////////////////////////////////////////////
//CLASS ArcQueue: