graph.cpp

实现了图的搜索算法

	int end = getVertexID(coor2);
	return BFS(start, end, tree);
}

BOOL Graph::DFS(int start, int end, Graph& tree)
{
	if(start>=0 && end>=0 && start<m_vertexs.size() && end<m_vertexs.size()){
		VerNode* pv1 = NULL, *pv2 = NULL;
		EdgeNode* pe = NULL;
		int coorp[2], coorc[2], parent, child, size;
		//初始化搜索树
		tree.clear();
		pv1= m_vertexs[start];
		tree.insertVertex(pv1->m_nCoor);
		//初始化开表和毕表
		m_open.clear();
		m_close.clear();
		clearVertexFlag();
		m_open.push_back(start);
		pv1->m_bInOpen = TRUE;
		//开始算法的运算过程
		while(m_open.size()>0){
			parent = m_open[0];//将n节点从开表中删除，放到毕表中
			m_open.pop_front();
			m_close.push_back(parent);
			pv1 = m_vertexs[parent];
			pv1->m_bInClose = TRUE;
			pv1->m_bInOpen = FALSE;
			if(parent == end){
				//找到目标节点
				return TRUE;
			}else{
				//扩展n节点
				size = pv1->m_edgeOut.size();
				coorp[0] = pv1->m_nCoor[0];
				coorp[1] = pv1->m_nCoor[1];
				for(int i = 0; i<size; i++){
					pe = pv1->m_edgeOut[i];
					child = pe->m_pVerTo->m_nID;
					pv2 = m_vertexs[child];
					coorc[0] = pv2->m_nCoor[0];
					coorc[1] = pv2->m_nCoor[1];
					if(!pv2->m_bInClose && !pv2->m_bInOpen){
						//新的节点没有出现在open或者close表中
						tree.insertVertex(coorc);
						tree.insertEdge(coorp, coorc);
						//对于深度优先搜索来说，将扩展的节点放到open表的前面
						m_open.push_front(child);
						pv2->m_bInOpen = TRUE;
					}
				}
			}
		}
	}		
	return FALSE;
}

BOOL Graph::BFS(int start, int end, Graph& tree)
{
	if(start>=0 && end>=0 && start<m_vertexs.size() && end<m_vertexs.size()){
		VerNode* pv1 = NULL, *pv2 = NULL;
		EdgeNode* pe = NULL;
		int coorp[2], coorc[2], parent, child, size;
		//初始化搜索树
		tree.clear();
		pv1= m_vertexs[start];
		tree.insertVertex(pv1->m_nCoor);
		//初始化开表和毕表
		m_open.clear();
		m_close.clear();
		clearVertexFlag();
		m_open.push_back(start);
		pv1->m_bInOpen = TRUE;
		//开始算法的运算过程
		while(m_open.size()>0){
			parent = m_open[0];//将n节点从开表中删除，放到毕表中
			m_open.pop_front();
			m_close.push_back(parent);
			pv1 = m_vertexs[parent];
			pv1->m_bInClose = TRUE;
			pv1->m_bInOpen = FALSE;
			if(parent == end){
				//找到目标节点
				return TRUE;
			}else{
				//扩展n节点
				size = pv1->m_edgeOut.size();
				coorp[0] = pv1->m_nCoor[0];
				coorp[1] = pv1->m_nCoor[1];
				for(int i = 0; i<size; i++){
					pe = pv1->m_edgeOut[i];
					child = pe->m_pVerTo->m_nID;
					pv2 = m_vertexs[child];
					coorc[0] = pv2->m_nCoor[0];
					coorc[1] = pv2->m_nCoor[1];
					if(!pv2->m_bInClose && !pv2->m_bInOpen){
						//新的节点没有出现在open或者close表中
						tree.insertVertex(coorc);
						tree.insertEdge(coorp, coorc);
						//对于广度优先搜索来说，将扩展的节点放到open表的后面
						m_open.push_back(child);
						pv2->m_bInOpen = TRUE;
					}
				}
			}
		}
	}		
	return FALSE;
}

BOOL Graph::Dijkstra(int start, int end, Graph& tree)
{
	if(start>=0 && end>=0 && start<m_vertexs.size() && end<m_vertexs.size()){
		VerNode* pv1 = NULL, *pv2 = NULL;
		EdgeNode* pe = NULL;
		int coorp[2], coorc[2], parent, child, size;
		float newg = 0.0f, newf = 0.0f;//新的估价函数值
		int idtree = 0;//节点在tree中的索引值
		VerNode* pvtree = NULL;//节点在tree中的指针
		EdgeNode* petree = NULL;//边在tree中的指针

		//初始化搜索树
		tree.clear();
		pv1= m_vertexs[start];
		tree.insertVertex(pv1->m_nCoor);
		//初始化开表和毕表
		m_open.clear();
		m_close.clear();
		clearVertexFlag();
		m_open.push_back(start);
		pv1->m_bInOpen = TRUE;
		pv1->m_g = 0.0f;//计算起始点的估价函数值
		pv1->m_f = pv1->m_g;
		//开始算法的运算过程
		while(m_open.size()>0){
			parent = m_open[0];//得到当前节点，并放到毕表中；
			m_open.pop_front();
			m_close.push_back(parent);
			pv1 = m_vertexs[parent];
			pv1->m_bInClose = TRUE;
			pv1->m_bInOpen = FALSE;
			if(parent == end){
				//找到目标节点
				return TRUE;
			}else{
				//扩展n节点
				size = pv1->m_edgeOut.size();
				coorp[0] = pv1->m_nCoor[0];
				coorp[1] = pv1->m_nCoor[1];
				for(int i = 0; i<size; i++){
					//得到扩展节点的属性（节点的ID，节点的指针）
					pe = pv1->m_edgeOut[i];
					child = pe->m_pVerTo->m_nID;
					pv2 = m_vertexs[child];
					coorc[0] = pv2->m_nCoor[0];
					coorc[1] = pv2->m_nCoor[1];
					//计算新扩展的节点的估价函数值
					//新的估价函数 = 节点pv1的估价函数值 + 边（pv1， pv2）的权值
					newg = pv1->m_g+pe->m_nWeight;
					newf = newg;
					if(!pv2->m_bInClose && !pv2->m_bInOpen){
						//新的节点没有出现在open或者close表中
						pv2->m_f = newf;//记录新的节点的估价值
						pv2->m_g = newg;
						//更新搜索图
						tree.insertVertex(coorc);
						tree.insertEdge(coorp, coorc);
						//新节点放到open表中
						insertOpen(child);
						pv2->m_bInOpen = TRUE;
					}else if(pv2->m_bInOpen){
						//节点pv2出现在open表中
						if(newf<pv2->m_f){
							pv2->m_f = newf;//更新节点pv2的估价值
							pv2->m_g = newg;
							//重新标定指针
							idtree = tree.getVertexID(coorc);
							pvtree = tree.m_vertexs[idtree];
							for(int k = 0; k<pvtree->m_edgeIn.size(); k++){
								petree = pvtree->m_edgeIn[k];
								tree.deleteEdge(petree->m_pVerFrom->m_nID, pvtree->m_nID);
							}
							tree.insertEdge(coorp, coorc);
							//更新open表中的内容
							updateOpen();
						}
					}else if (pv2->m_bInClose) {
						//节点pv2出现在close表中
						if(newf<pv2->m_f){
							pv2->m_f = newf;//更新节点pv2的估价值
							pv2->m_g = newg;
							//重新标定指针
							idtree = tree.getVertexID(coorc);
							pvtree = tree.m_vertexs[idtree];
							for(int k = 0; k<pvtree->m_edgeIn.size(); k++){
								petree = pvtree->m_edgeIn[k];
								tree.deleteEdge(petree->m_pVerFrom->m_nID, pvtree->m_nID);
							}
							tree.insertEdge(coorp, coorc);
							//将节点pv2重新放回open表中
							insertOpen(child);
							pv2->m_bInOpen = TRUE;
							pv2->m_bInClose = FALSE;
						}
					}
				}
				//以上为扩展节点n的操作
			}
		}
	}		
	return FALSE;
}

float Graph::A_star_h(int n, int end)
{
	//A*算法的启发函数
	//n为当前的节点，end为终点
	VerNode* pv1 = m_vertexs[n];
	VerNode* pv2 = m_vertexs[end];
	float d = sqrt(pow(pv1->m_nCoor[0]-pv2->m_nCoor[0], 2)+pow(pv1->m_nCoor[1]-pv2->m_nCoor[1], 2));
//	float d = fabs(pv1->m_nCoor[0]-pv2->m_nCoor[0])+fabs(pv1->m_nCoor[1]-pv2->m_nCoor[1]);
	return d;
}

BOOL Graph::A_star(int start, int end, Graph& tree)
{
	if(start>=0 && end>=0 && start<m_vertexs.size() && end<m_vertexs.size()){
		VerNode* pv1 = NULL, *pv2 = NULL;
		EdgeNode* pe = NULL;
		int coorp[2], coorc[2], parent, child, size;
		float newg = 0.0f, newf = 0.0f;//新的估价函数值
		int idtree = 0;//节点在tree中的索引值
		VerNode* pvtree = NULL;//节点在tree中的指针
		EdgeNode* petree = NULL;//边在tree中的指针

		//初始化搜索树
		tree.clear();
		pv1= m_vertexs[start];
		tree.insertVertex(pv1->m_nCoor);
		//初始化开表和毕表
		m_open.clear();
		m_close.clear();
		clearVertexFlag();
		m_open.push_back(start);
		pv1->m_bInOpen = TRUE;
		pv1->m_g = 0.0f;//计算起始点的估价函数值
		pv1->m_f = pv1->m_g+A_star_h(start, end);
		//开始算法的运算过程
		while(m_open.size()>0){
			parent = m_open[0];//得到当前节点，并放到毕表中；
			m_open.pop_front();
			m_close.push_back(parent);
			pv1 = m_vertexs[parent];
			pv1->m_bInClose = TRUE;
			pv1->m_bInOpen = FALSE;
			if(parent == end){
				//找到目标节点
				return TRUE;
			}else{
				//扩展n节点
				size = pv1->m_edgeOut.size();
				coorp[0] = pv1->m_nCoor[0];
				coorp[1] = pv1->m_nCoor[1];
				for(int i = 0; i<size; i++){
					//得到扩展节点的属性（节点的ID，节点的指针）
					pe = pv1->m_edgeOut[i];
					child = pe->m_pVerTo->m_nID;
					pv2 = m_vertexs[child];
					coorc[0] = pv2->m_nCoor[0];
					coorc[1] = pv2->m_nCoor[1];
					//计算新扩展的节点的估价函数值
					//新的估价函数 = 节点pv1的估价函数值 + 边（pv1， pv2）的权值
					newg = pv1->m_g+pe->m_nWeight;
					newf = newg+A_star_h(child, end);
					if(!pv2->m_bInClose && !pv2->m_bInOpen){
						//新的节点没有出现在open或者close表中
						pv2->m_f = newf;//记录新的节点的估价值
						pv2->m_g = newg;
						//更新搜索图
						tree.insertVertex(coorc);
						tree.insertEdge(coorp, coorc);
						//新节点放到open表中
						insertOpen(child);
						pv2->m_bInOpen = TRUE;
					}else if(pv2->m_bInOpen){
						//节点pv2出现在open表中
						if(newf<pv2->m_f){
							pv2->m_f = newf;//更新节点pv2的估价值
							pv2->m_g = newg;
							//重新标定指针
							idtree = tree.getVertexID(coorc);
							pvtree = tree.m_vertexs[idtree];
							for(int k = 0; k<pvtree->m_edgeIn.size(); k++){
								petree = pvtree->m_edgeIn[k];
								tree.deleteEdge(petree->m_pVerFrom->m_nID, pvtree->m_nID);
							}
							tree.insertEdge(coorp, coorc);
							//更新open表中的内容
							updateOpen();
						}
					}else if (pv2->m_bInClose) {
						//节点pv2出现在close表中
						if(newf<pv2->m_f){
							pv2->m_f = newf;//更新节点pv2的估价值
							pv2->m_g = newg;
							//重新标定指针
							idtree = tree.getVertexID(coorc);
							pvtree = tree.m_vertexs[idtree];
							for(int k = 0; k<pvtree->m_edgeIn.size(); k++){
								petree = pvtree->m_edgeIn[k];
								tree.deleteEdge(petree->m_pVerFrom->m_nID, pvtree->m_nID);
							}
							tree.insertEdge(coorp, coorc);
							//将节点pv2重新放回open表中
							insertOpen(child);
							pv2->m_bInOpen = TRUE;
							pv2->m_bInClose = FALSE;
						}
					}
				}
				//以上为扩展节点n的操作
			}
		}
	}		
	return FALSE;
}

void Graph::insertOpen(int vnode)
{
	//往open表中插入新的节点，并按照估价函数进行排序
	int size = m_open.size();
	VerNode* pv1 = m_vertexs[vnode];
	VerNode* pv2 = NULL;
	if(size>0){
		int index = -1; 
		for(int i = 0; i<size; i++){
			pv2 = m_vertexs[m_open[i]];
			if(pv1->m_f<=pv2->m_f){
				index = i;
				break;
			}
		}
		if(index>=0){
			m_open.insert(m_open.begin()+index, vnode);
		}else{
			m_open.push_back(vnode);
		}
	}else{
		m_open.push_back(vnode);
	}
}

void Graph::updateOpen()
{
	//更新OPEN表中的数据，前提是只有一个数据变化
	int size = m_open.size();
	VerNode *pv1, *pv2;
	int index = -1, temp;
	for(int i = 0; i<size-1; i++){
		pv1 = m_vertexs[m_open[i]];
		pv2 = m_vertexs[m_open[i+1]];
		if(pv1->m_f>pv2->m_f){
			index = i;
			temp = m_open[i];
			m_open[i] = m_open[i+1];
			m_open[i+1] = temp;
			break;
		}
	}

	if(index>=0){
		for(int i = index+1; i<size-1; i++){
			pv1 = m_vertexs[m_open[i]];
			pv2 = m_vertexs[m_open[i+1]];
			if(pv1->m_f>pv2->m_f){
				temp = m_open[i];
				m_open[i] = m_open[i+1];
				m_open[i+1] = temp;
			}else{
				break;
			}
		}

		for(i = index; i>0; i--){
			pv1 = m_vertexs[m_open[i]];
			pv2 = m_vertexs[m_open[i-1]];
			if(pv1->m_f<pv2->m_f){
				temp = m_open[i];
				m_open[i] = m_open[i-1];
				m_open[i-1] = temp;
			}else{
				break;
			}
		}
	}
}