graphic.cpp

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

#include "stdafx.h"
#include "queue.h"
Graphic::Graphic()
{
	//构造函数对图进行初始化
	m_verqueue = NULL;
	m_narc = 0;
	m_nver = 0;
	m_nvisit = 0;
	m_nunit = 0;
}
void Graphic::InsertArc(VerNode* pnode,VerNode* pend,int mark)
{
	//INSERTARC函数实现在pnode和pend之间插入一条弧
	ArcNode* pnew = (ArcNode*)new ArcNode;
	pnew->m_padjver = pend;
	pnew->m_pnextarc = NULL;
	pnew->info = mark;
	if(pnode->m_pfirstarc == NULL){
		pnode->m_pfirstarc = pnew;
		m_narc++;
	}
	else{
		for(ArcNode* p = pnode->m_pfirstarc;p->m_pnextarc;p = p->m_pnextarc){}
		p->m_pnextarc = pnew;
		m_narc++;
	}

}
BOOL Graphic::IsNewArc(VerNode* pnode,VerNode* pend)
{
	//判断pnode和pend之间是否已存在一条弧
	for(ArcNode* p = pnode->m_pfirstarc;p;p = p->m_pnextarc){
		if(p->m_padjver == pend)
			return FALSE;
	}
	return TRUE;
}
CPoint Graphic::ChagetoPoint(CRect rect)
{
	//实现结点所占据的矩形到点的转变
	CPoint point;
	point.x = (rect.left+rect.right)/2;
	point.y = (rect.bottom+rect.top)/2;
	return point;
}
void Graphic::DisplayGraph(CDC* pdc,int type)
{
	//在视图上显示图的结构
	ArcNode* parc;
	CPoint point1,point2;
	pdc->SelectStockObject(BLACK_BRUSH);
	for(VerNode* pver = m_verqueue->m_phead;pver;pver = pver->m_pnextver){
			pdc->Ellipse(pver->m_rect);
			point1 = ChagetoPoint(pver->m_rect);
		for(parc = pver->m_pfirstarc;parc;parc = parc->m_pnextarc){
				pdc->MoveTo(point1);
				point2 = ChagetoPoint(parc->m_padjver->m_rect);
				pdc->LineTo(point2);
				if(type == 0){
					pdc->MoveTo(point2);
					pdc->LineTo(XL(point1.x,point1.y,point2.x,point2.y),
						YL(point1.x,point1.y,point2.x,point2.y));
					pdc->MoveTo(point2);
					pdc->LineTo(XR(point1.x,point1.y,point2.x,point2.y),
						YR(point1.x,point1.y,point2.x,point2.y));
					pdc->MoveTo(XL(point1.x,point1.y,point2.x,point2.y),
						YL(point1.x,point1.y,point2.x,point2.y));
					pdc->LineTo(XR(point1.x,point1.y,point2.x,point2.y),
					YR(point1.x,point1.y,point2.x,point2.y));
				}
		}	
	}
	pdc->SelectStockObject(WHITE_BRUSH);
}

void Graphic::DeleteVer(VerNode* pnode)
{
	//删除pnode所指的结点
	VerNode* ptemp;
	ArcNode* parc,*parctemp = NULL;
	int arc = 0;
	for(ptemp = m_verqueue->m_phead;ptemp;ptemp = ptemp->m_pnextver){
		for(parc = ptemp->m_pfirstarc;parc;parc = parc->m_pnextarc){
			if(parc->m_padjver == pnode){
				parctemp = parc;
				arc++;
			}
		}
		if(parctemp != NULL)
		DeleteArc(ptemp,parctemp);
		parctemp = NULL;
	}
	m_narc = m_narc-GetArcNum(pnode)-arc;
	m_verqueue->m_phead = m_verqueue->DeleteVer(pnode);
}

void Graphic::DeleteArc(VerNode* pver,ArcNode* parc)
{
	//删除以pver为头到parc所指的邻接结点之间的弧
	ArcNode* ptemp = pver->m_pfirstarc;
	if(parc == pver->m_pfirstarc){
		pver->m_pfirstarc = pver->m_pfirstarc->m_pnextarc;
	}
	else{
		for(;ptemp->m_pnextarc !=parc;ptemp = ptemp->m_pnextarc){}
		ptemp->m_pnextarc = parc->m_pnextarc;
		delete parc;
	}
}
int Graphic::GetArcNum(VerNode* pver)
{
	//获得图中弧的个数
	int n = 0;
	for(ArcNode* parc = pver->m_pfirstarc;parc;parc = parc->m_pnextarc){
		n++;
	}
	return n;
}

void Graphic::DeleteArc(VerNode* pstart,VerNode* pend)
{
	//删除pstart和pend所指结点之间的弧
	VerNode* start = pstart,* end = pend;
	ArcNode* arc = NULL,* temp = NULL;
	for(arc = start->m_pfirstarc;arc;arc = arc->m_pnextarc){
		if(arc->m_padjver == pend){
			temp = arc;
			m_narc--;
		}
	}
	if(temp != NULL)
	DeleteArc(pstart,temp);
}

VerNode* Graphic::NameToPointer(CString name)
{
	//由结点的名字获得它的指针
	VerNode* vertex = NULL;
	for(vertex = m_verqueue->m_phead;vertex;vertex = vertex->m_pnextver){
			if(vertex->m_strname == name)
				break;
	}
	return vertex;
}

int Graphic::CalculateDu(VerNode* pver)
{
	//计算结点pver的度数
	VerNode* ver;
	ArcNode* arc;
	int count = 0;
	for(ver = m_verqueue->m_phead;ver;ver = ver->m_pnextver){
		for(arc = ver->m_pfirstarc;arc;arc = arc->m_pnextarc){
			if(arc->m_padjver == pver)count++;
		}
	}
	for(arc = pver->m_pfirstarc;arc;arc = arc->m_pnextarc)count++;
	return count/2;

}

void Graphic::DFSTraverse(CDC* pdc)
{
	//DFS深度优先搜索函数
	//用于一次显示所有的结点
	CPen pen(PS_DASHDOTDOT,2,RGB(255,0,0));
	pdc->SelectObject(&pen);
	for(VerNode* pnode = m_verqueue->m_phead;pnode;pnode = pnode->m_pnextver)
		pnode->m_bvisit = FALSE;
	m_nvisit = 0;
	m_nunit = 0;

	for(pnode = m_verqueue->m_phead;pnode;pnode = pnode->m_pnextver){
		if(!pnode->m_bvisit){
			DFS(pnode,pdc);
			m_nunit++;
		}
	}
	pdc->SelectStockObject(BLACK_PEN);
}

void Graphic::DFS(VerNode* pnode,CDC* pdc)
{
	//DFS递归实现函数
	CString str;
	m_nvisit++;
	pnode->m_bvisit = TRUE;

	str.Format("%d",m_nvisit);	
	pdc->Ellipse(pnode->m_rect.left-5,pnode->m_rect.top-5,
		pnode->m_rect.right+5,pnode->m_rect.bottom+5);
	pdc->TextOut(pnode->m_rect.left,pnode->m_rect.top-3,str);

	for(ArcNode* parc = pnode->m_pfirstarc;parc;parc = parc->m_pnextarc){
		VerNode* padj = parc->m_padjver;
		if(!padj->m_bvisit)
			DFS(padj,pdc);
	}
}

void Graphic::DFSTraverse()
{
	//DFS深度优先搜索
	//用于实现逐步显示
	for(VerNode* pnode = m_verqueue->m_phead;pnode;pnode = pnode->m_pnextver)
		pnode->m_bvisit = FALSE;
	m_nvisit = 0;
	m_nunit = 0;

	for(pnode = m_verqueue->m_phead;pnode;pnode = pnode->m_pnextver){
		if(!pnode->m_bvisit){
			DFS(pnode);
			m_nunit++;
		}
	}

}

void Graphic::DFS(VerNode* pnode)
{
	//DFS深度优先递归函数
	//用于实现逐步显示
	pnode->m_bvisit = TRUE;
	m_nvisit++;
	pnode->m_nvisit = m_nvisit;
	
	for(ArcNode* parc = pnode->m_pfirstarc;parc;parc = parc->m_pnextarc){
		VerNode* padj = parc->m_padjver;
		if(!padj->m_bvisit)
			DFS(padj);
	}
}

void Graphic::BFSTraverse()
{
	//BFS广度优先搜索
	//用于逐步显示搜索的过程
	VerQueue queue;
	VerNode pnode1;
	for(VerNode* pnode = m_verqueue->m_phead;pnode;pnode = pnode->m_pnextver){
		pnode->m_bvisit = FALSE;
	}
	m_nvisit = 0;
	for(pnode = m_verqueue->m_phead;pnode;pnode = pnode->m_pnextver){
		if(!pnode->m_bvisit){
			m_nvisit++;
			pnode->m_bvisit = TRUE;
			pnode->m_nvisit = m_nvisit;

			queue.EnQueue(*pnode);
			while(queue.m_nnum){
				queue.DeQueue(pnode1);
				for(ArcNode* parc = pnode1.m_pfirstarc;parc;parc = parc->m_pnextarc){
					if(!parc->m_padjver->m_bvisit)
					{
						m_nvisit++;
						parc->m_padjver->m_bvisit = TRUE;
						parc->m_padjver->m_nvisit = m_nvisit;
						queue.EnQueue(*parc->m_padjver);
					}	//inner if
				}	//inner for

			}	//while
		}	//outer if
	}	//outer for

}

void Graphic::BFSTraverse(CDC* pdc)
{
	//BFS广度优先搜索
	//用于实现一次性显示广度优先搜索的过程
	CPen pen(PS_DASHDOTDOT,2,RGB(255,0,0));
	pdc->SelectObject(&pen);
	VerQueue queue;
	VerNode pnode1;
	CString str;
	for(VerNode* pnode = m_verqueue->m_phead;pnode;pnode = pnode->m_pnextver){
		pnode->m_bvisit = FALSE;
	}
	m_nvisit = 0;
	for(pnode = m_verqueue->m_phead;pnode;pnode = pnode->m_pnextver){
		if(!pnode->m_bvisit){
			m_nvisit++;
			pnode->m_bvisit = TRUE;

			str.Format("%d",m_nvisit);	
			pdc->Ellipse(pnode->m_rect.left-5,pnode->m_rect.top-5,
					pnode->m_rect.right+5,pnode->m_rect.bottom+5);
			pdc->TextOut(pnode->m_rect.left,pnode->m_rect.top-3,str);

			queue.EnQueue(*pnode);
			while(queue.m_nnum){
				queue.DeQueue(pnode1);
				for(ArcNode* parc = pnode1.m_pfirstarc;parc;parc = parc->m_pnextarc){
					if(!parc->m_padjver->m_bvisit)
					{
						m_nvisit++;
						parc->m_padjver->m_bvisit = TRUE;
						str.Format("%d",m_nvisit);	
						pdc->Ellipse(parc->m_padjver->m_rect.left-5,
									parc->m_padjver->m_rect.top-5,
									parc->m_padjver->m_rect.right+5,
									parc->m_padjver->m_rect.bottom+5);
						pdc->TextOut(parc->m_padjver->m_rect.left,
									parc->m_padjver->m_rect.top-3,str);
						queue.EnQueue(*parc->m_padjver);
					}	//inner if
				}	//inner for

			}	//while
		}	//outer if
	}	//outer for
	pdc->SelectStockObject(BLACK_PEN);
}

int Graphic::CalculateInDu(VerNode* pver)
{
	//对于有向图计算它的入度
	int count = 0;
	for(VerNode* ver = m_verqueue->m_phead;ver;ver = ver->m_pnextver){
		for(ArcNode* arc = ver->m_pfirstarc;arc;arc = arc->m_pnextarc){
			if(arc->m_padjver == pver)count++;
		}
	}
	return count;
}

int Graphic::CalculateOutDu(VerNode* pver)
{
	//对于有向图计算它的出度
	int count = 0;
	for(ArcNode* parc = pver->m_pfirstarc;parc;parc = parc->m_pnextarc)
		count++;
	return count;
}

int Graphic::XL(int x1,int y1,int x2,int y2)
{
	int a,b;
	a = ((x2-x1)*(x2-x1)*(7*x2/8+x1/8))+((y2-y1)*(y2-y1)*x2)-(y2-y1)*(y2-y1)*(x2-x1)/8-12*(y2-y1)*(x2-x1);
	b = (y2-y1)*(y2-y1)+(x2-x1)*(x2-x1);
	return a/b;
}

int Graphic::YL(int x1,int y1,int x2,int y2)
{
	int a,b,c,d;
	a = (y2-y1)*(y2-y1);
	b = (x2-x1)*(x2-x1);
	c = a*(7*y2/8+y1/8)+b*(y2+12)-b*(y2-y1)/8;
	d = a+b;
	return c/d;
}

int Graphic::XR(int x1,int y1,int x2,int y2)
{
	int a,b;
	a = ((x2-x1)*(x2-x1)*(7*x2/8+x1/8))+((y2-y1)*(y2-y1)*x2)-(y2-y1)*(y2-y1)*(x2-x1)/8+12*(y2-y1)*(x2-x1);
	b = (y2-y1)*(y2-y1)+(x2-x1)*(x2-x1);
	return a/b;
}

int Graphic::YR(int x1,int y1,int x2,int y2)
{
	int a,b,c,d;
	a = (y2-y1)*(y2-y1);
	b = (x2-x1)*(x2-x1);
	c = a*(7*y2/8+y1/8)+b*(y2-12)-b*(y2-y1)/8;
	d = a+b;
	return c/d;
}

BOOL Graphic::TestKeda(VerNode* start,VerNode* end)
{
	//判断start结点到end结点之间是否可达
	for(VerNode* pnode = m_verqueue->m_phead;pnode;pnode = pnode->m_pnextver){
		pnode->m_bvisit = FALSE;
	}
	int mark = 0;
	TKD(start,end,mark);
	return mark;
}

void Graphic::TKD(VerNode* start,VerNode* end,int& mark)
{
	//判断keda的具体函数
	start->m_bvisit = TRUE;
	for(ArcNode* parc = start->m_pfirstarc;parc;parc = parc->m_pnextarc){
		VerNode* padj = parc->m_padjver;
		if(!padj->m_bvisit){
			if(padj == end)mark = 1;
			else TKD(padj,end,mark);
		}
	}
}

int Graphic::PointerToNum(VerNode* pnode)
{
	//由结点pnode的指针转换为它的编号
	int count = 0;
	for(VerNode* pver = m_verqueue->m_phead;pver;pver = pver->m_pnextver){
		if(pver == pnode)return count;
		else count++;
	}
	return -1;

}
void Graphic::ShortestPath(VerNode* pstart,BOOL** p)
{
	//求出由结点PSTART到其余各个结点之间的最小路径
	int v0,v,min,adj,w;
	VerNode* pmin;
	v0 = PointerToNum(pstart);

///////////////////////////////////////////////////////////////////////////////////
	for(VerNode* pnode = m_verqueue->m_phead;pnode;pnode = pnode->m_pnextver){
		pnode->m_bvisit = FALSE;
		pnode->m_nvisit = INFINITY;
	}
	for(ArcNode* parc = pstart->m_pfirstarc;parc;parc = parc->m_pnextarc){
		parc->m_padjver->m_nvisit = parc->info;			
	}
	for(pnode = m_verqueue->m_phead;pnode;pnode = pnode->m_pnextver){
		v = PointerToNum(pnode);
		for(w = 0;w<m_verqueue->m_nnum;w++)p[v][w] = FALSE;
		if(pnode->m_nvisit<INFINITY){
			p[v][v0] = TRUE;
			p[v][v] = TRUE;		
		}
	}
////////////////////////////////////////////////////////////////////////////////////

	pstart->m_bvisit = TRUE;
	pstart->m_nvisit = 0;

/////////////////////////////////////////////////////////////////////////////////////
	for(int i = 1;i<m_verqueue->m_nnum;i++){
		min = INFINITY;
		for(pnode = m_verqueue->m_phead;pnode;pnode = pnode->m_pnextver){
			if(!pnode->m_bvisit)
				if(pnode->m_nvisit<min){
					pmin = pnode;
					min = pnode->m_nvisit;
				}
		}

		v = PointerToNum(pmin);
		pmin->m_bvisit = TRUE;

		for(pnode = m_verqueue->m_phead;pnode;pnode = pnode->m_pnextver){
			w = PointerToNum(pnode);
			adj = INFINITY;

			for(parc = pmin->m_pfirstarc;parc;parc = parc->m_pnextarc){
				if(pnode == parc->m_padjver)adj = parc->info;
			}
			
			if(!pnode->m_bvisit&&(min+adj<pnode->m_nvisit)){
				pnode->m_nvisit = min+adj;
				for(int j = 0;j<m_verqueue->m_nnum;j++)
					p[w][j] = p[v][j];
				p[w][w] = TRUE;
			}
		}	
	}
	
}