graph.cpp

这是由Dijkstra算法实现的最短路径的实现

#include "StdAfx.h"
#include ".\graph.h"
#include <math.h>

CGraph::CGraph(void)//构造函数
{
}

CGraph::~CGraph(void)//析构函数
{
}

CGraphNode::CGraphNode(void)
{
	m_bSelected = FALSE;
}

CGraphNode::~CGraphNode(void)
{
}

void CGraph::clear(void)//删除所有结点
{
	m_Nodes.clear();//清空结点数组
}

int CGraph::AddNode(CPoint Pos)//新增加结点,Pos为其位置坐标
{
	CGraphNode node;//node为CGraphNode的一个实例
	node.m_Pos=Pos;//使鼠标点击的位置坐标为当前node的位置坐标
	m_Nodes.push_back( node );//将当前node放入结点数组中
	return 0;
}

void CGraph::Draw(CDC * pDC)//画点或在已连接的两点间画线
{
	//参数检查
   	if (!pDC)
  		return;   //判断指针是否为空，不空则往下进行
	int n=(int)  m_Nodes.size();//用n承载结点个数

	//画边
	for (int i=0;i<n;i++)//扫描所有点
	{
		CGraphNode &node = m_Nodes[i];//用node引用第i个结点
		int nAdj = (int)node.m_Adj.size();//用nAdj承载j的邻接表的大小
		for (int j=0;j<nAdj;j++)//扫描i的邻接表
		{
			int nAdjNode = node.m_Adj[j];//用nAdj承载j的邻接表的内容
			if (nAdjNode>=0&&nAdjNode<n)//若此邻接点合法，不越界 ,则
			{
				pDC->MoveTo(node.m_Pos);//指针跳回起始点
				pDC->LineTo(m_Nodes[nAdjNode].m_Pos);
				    //从起始点到邻接点画一条可见的直线
				CPoint p=node.m_Pos+m_Nodes[nAdjNode].m_Pos;
				p.x/=2;p.y/=2;//找直线的中点,用来写权值
				CString s; 
				s.Format("%d",Cost(i,nAdjNode));//调用Cost函数计算权值
				pDC->TextOut(p.x,p.y,s);//在直线的中点处打印权值
			}
		}
	}
	CPen pen;
	pen.CreatePen(PS_SOLID,2,0xFF);//建立画笔,画实心,宽度为2的红边
	CPen* pOldPen = pDC->SelectObject(&pen);
	for (i=0;i<n;i++)//扫描所有结点
	{
		CGraphNode &node = m_Nodes[i];//用node引用第i个结点
		int nAdj = (int)  node.m_SelectAdj.size();
		                            //用nAdj承载被选中的邻接表的大小
		for (int j=0;j<nAdj;j++)//扫描i的邻接点
		{
			int nAdjNode = node.m_SelectAdj[j];
			                //用nAdjNode承载i的邻接表的内容
			if (nAdjNode>=0&&nAdjNode<n)//若此邻接点合法，不越界 ,则
			{
				pDC->MoveTo(node.m_Pos);//指针跳回起始点
				pDC->LineTo(m_Nodes[nAdjNode].m_Pos);
				                //从起始点到邻接点画一条可见的红色直线
			}
		}

	}
	pDC->SelectObject(pOldPen);

	//画节点
	for (i=0;i<n;i++)//扫描所有结点
	{
		CGraphNode &node = m_Nodes[i];//用node引用结点i
		CRect rcNode = GetNodeRect(i);//用i的坐标确定一个矩形框
		pDC->Ellipse(rcNode);//在此矩形框中画一个圆
		CString s;
		s.Format("%d",i);//打印结点的编号
		pDC->SetBkMode(TRANSPARENT);//背景透明
     
	   
		pDC->DrawText(s,rcNode,DT_VCENTER|DT_CENTER);
		          //在矩形的中心位置打印结点编号
	}
}

int CGraph::GetNodeIndex(CPoint Pos)//返回结点的位置
{
	int n=(int)m_Nodes.size();//用n承载结点个数
	for (int i=0;i<n;i++)//遍历所有结点
	{
		CGraphNode &node = m_Nodes[i];//用node引用结点i
		CRect rcNode = GetNodeRect(i);//以i的坐标确定矩形框
		if ( rcNode.PtInRect(Pos) )//若此位置实际存在
			return i;//则返回i
	}
	return -1;//否则返回无效点-1
}

void CGraph::AddEdge(int nStart, int nEnd)
 //在点nStart与nEnd点之间连一条边 
{
	int n=(int)  m_Nodes.size();//用n承载结点个数
	if (nStart>=0 && nEnd>=0 && nStart<n && nEnd<n )
		//若此边所连接的两点合法，不越界,则连一条边
	{
		m_Nodes[nStart].AddAdjNode(nEnd);//使nEnd为点nStart的邻接点
		m_Nodes[nEnd].AddAdjNode(nStart);//使nStart为点nEnd的邻接点
	}
}

CRect CGraph::GetNodeRect(int nNode)//获得矩形框的实际大小
{
	if (nNode<0 || nNode>=(int)m_Nodes.size() )//判断nNode是否合法
		return CRect();       
	CGraphNode &node = m_Nodes[nNode];//用node引用结点i
	CRect rcNode ( node.m_Pos.x-10 ,node.m_Pos.y-10,node.m_Pos.x+10,node.m_Pos.y+10);
	//返回一个20*20的矩形框
	return rcNode;//返回rcNode
}

int CGraphNode::AddAdjNode(int nNode)
{
	int n=(int)m_Adj.size();
	for (int i=0;i<n;i++)
	{
		//已经有了
		if (m_Adj[i] == nNode)
			return 0;
	}
	m_Adj.push_back(nNode);
	return 0;
}

int CGraphNode::ClearSelect(void)
{
	m_bSelected = FALSE;
	m_SelectAdj.clear();
	return 0;
}

int CGraphNode::SelectEdge(int nNode)
{
	int n=(int)m_SelectAdj.size();
	for (int i=0;i<n;i++)
	{
		//已经有了
		if (m_SelectAdj[i] == nNode)
			return 0;
	}
	m_SelectAdj.push_back(nNode);
	return 0;
}

int CGraph::ClearSelect(void)//清空结点数组中每个结点的bSelected项
                             //使其为false
{
	int n=(int)m_Nodes.size();//用n承载结点个数
	for (int i=0;i<n;i++)//扫描所有结点
	{
		m_Nodes[i].ClearSelect();//使与结点相关联的边的bSelected项为false
	}
	return 0;
}

int CGraph::ShortestPath(int v,int vd)//求该图的最短路径
{
	int n=(int)m_Nodes.size();//用n承载结点个数
	int u,k,i,j;

	if (v<0 || v>= n)//判断v是否越界
		return 0;
	if (vd<0 || vd>= n)//判断vd是否越界
		return 0;
	static int path[1000];//定义路径数组
	static int dist[1000];//定义距离数组
	static int s[1000];//数组s[]记录i是否被访问过

	for (i=0;i<n;i++)//数组path[]，dist[]，s[]初始化
	{
		dist[i] = INT_MAX;
		path[i] = -1;
		s[i]=0;
	}
	dist[v] = 0;//初始顶点v的数组值
	s[v]=0;

	u=v;//u为刚访问过的结点
	for (j=0;j<n;j++)//循环（1）
	{
		int nAdj = (int)m_Nodes[u].m_Adj.size();
		for (int p=0;p<nAdj;p++)
			//循环（2）修改u邻接顶点的path[]，dist[]，s[]值
		{
			k=	m_Nodes[u].m_Adj[p];
			if (k<0 || k>= n)
				continue;
			if (s[k]!=1 && dist[u]+ Cost(u,k) <dist[k])
			{
				dist[k]=dist[u]+Cost(u,k);
				path[k]=u;
			}
		}
		int ldist = INT_MAX;
		for (i=0;i<n;i++)//循环（3）确定即将被访问的结点u
		{
			if (dist[i]>0 && dist[i]<ldist && s[i]==0)
			{
				ldist=dist[i];u=i;
			}
		}
		s[u]=1;//访问u
	}

	if (path[vd]!=-1)     
	{
		int kk=vd;
		while (kk>=0&&kk<n)
		{
			m_Nodes[kk].SelectEdge(path[kk]);
			kk=path[kk];
		}
	}

	return 0;
} 
typedef struct _Edge
{
	int Lowcost;
	int vex;
}_Edge;
int CGraph::Prim(void)//找最小生成树
{
	int n=(int)m_Nodes.size();//用n承载结点个数
	int i,j;
	static _Edge closedge[1000];//定义邻接边数组
	for (i=0;i<n;i++)//以顶点0为初始顶点，初始化数组closedge
	{
		closedge[i].Lowcost = Cost(0,i);//存放0到i的最小权值
		closedge[i].vex=0;//此时U未包含任何结点
	}
	closedge[0].vex=-1;//顶点0进入集合U
	int count = 0;//生成树的边计数器count
	for (i=1;i<n;i++)//循环n-1次
	{
		int min = INT_MAX;//设置最小值min
		int v=0;
		for (j=0;j<n;j++)//求当前权值最小的边和该边的终点v
			if (closedge[j].vex != -1 && closedge[j].Lowcost < min)
			{
				v=j;
				min = closedge[j].Lowcost;
			}
		if (v!=0)//若v为零，说明没有找到符合条件的顶点
		{   //向生成树的边集合中添加一个边
			m_Nodes[v].SelectEdge(closedge[v].vex);
			count++;//计数器加一
			closedge[v].Lowcost=0;//修改域值
			closedge[v].vex=-1;//顶点v进入集合U
			//因为v的进入，而要修改某些值
			for (j=0;j<n;j++)
				if (closedge[j].vex!=-1 && Cost(v,j)< closedge[j].Lowcost)
				{
					closedge[j].Lowcost=Cost(v,j);
					closedge[j].vex=v;
				}
		}
	}
	return 0;
}


CString CGraph::Save(void)//存盘操作
{	
	CString sReturn;  //用sReturn储存所有关于所有点的信息

	int n=(int)  m_Nodes.size();//用n来承载结点个数
	for (int i=0;i<n;i++)//扫描所有结点
	{
		CString sSave,s;//sSave储存第i个结点的信息，s存放邻接点
		CGraphNode &node = m_Nodes[i];//用node来引用结点i
		sSave.Format("%d,%d\t;\t",node.m_Pos.x,node.m_Pos.y);
		           //打印当前结点的横纵坐标
		for (int j=0;j<(int)node.m_Adj.size();j++)
			     //遍历第i个结点的邻接点
		{
			s.Format("%d,",node.m_Adj[j]);//打印该邻接点的名称
			                              //以逗号隔开
			sSave+=s;//第i个结点信息的扩充
		}
		sReturn+=sSave+"\r\n";//所有结点信息的扩充
	}

	return sReturn;//返回所有结点的信息
}
void _Next(CString &s,char c)
{
	int t=s.Find(c);
	if (t==-1)
		s.Empty();
	else
		s = s.Right(s.GetLength()-t-1);//取save中一行的“,”右册侧的所有信息
}
int CGraph::Load(CString sGraph)//读取结点信息
{
	clear();//清空当前面板信息
	int a=0,b=0;//中间变量
	while (1)
	{
		a=sGraph.Find('\n',b);//用a存放一个接点的信息
		if (a<0)break;//若a不合法，则退出
		CString sNode = sGraph.Mid(b,a-b);//按段截取信息读取
		if (!sNode.IsEmpty())//若结点信息非空
		{
			CGraphNode node;//定义一个CGraphNode的实例
			sscanf(sNode,"%d,%d",&node.m_Pos.x,&node.m_Pos.y);
			                    //读取横纵坐标
			_Next(sNode,';');//取分号右侧的信息
			while (!sNode.IsEmpty())//若分号右侧的信息非空
			{
				int t=-1;//令t为-1
				sscanf(sNode,"%d",&t);//扫描邻接点信息
				if (t>=0)//若存在邻接点
					node.AddAdjNode(t);//将其加入到邻接表中
				_Next(sNode,',');//取逗号右侧的信息
			}
			m_Nodes.push_back(node);//将结点信息放入结点数组中
		}
		b=a+1;  //按行分割
	}
	return 0;
}

int CGraph::Cost(int j,  int k)//计算从j到k的权值
{
	int n=(int)   m_Nodes.size();//用n承载结点个数

	if (j<n&&k<n&&j>=0&&k>=0)
		//若此边所连接的两点合法，不越界
	{
		BOOL bLink = FALSE;//bLink = FALSE即两点不连接
		int nAdj = (int)  m_Nodes[j].m_Adj.size();
		//用nAdj承载j的邻接表的大小
		for (int p=0;p<nAdj;p++)//扫描j的邻接表中的所有结点
		{
			if (m_Nodes[j].m_Adj[p]==k)//判断k是否在j的邻接表中
				bLink = TRUE;//若在表中bLink =TRUE 即两点连接
		}
		if (!bLink)//若bLink = FALSE即两点不连接
			return INT_MAX;//使这两点间权值为无穷大
                           //否则bLink =TRUE 即两点连接,计算权值 
		int x1,x2,y1,y2,cost;//x1,y1表示j的坐标,
		                     //x2,y2表示k的坐标,
		                     //cost表示权值
		x1=m_Nodes[j].m_Pos.x;
		y1=m_Nodes[j].m_Pos.y;
		x2=m_Nodes[k].m_Pos.x;
		y2=m_Nodes[k].m_Pos.y;
		cost=(int)sqrt((double)(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
		//根据两点坐标求两点间距离
		return cost;//若两点邻接返回权值
	}
	return INT_MAX;//若两点不邻接返回无穷大
}