践了DFS,BFS,启发式,Bellman-Ford,Dijkstr 搜索算法 界面能直观清晰地看到各算法的执行结果

#include "csearcher.h" CSearcher::CSearcher() { // m_Parents.rehash( 3000000 ); // m_ShortestPath.rehash( 3000000 ); } bool CSearcher::Dfs(Map_t Map, const QPoint &ptSrc, const QPoint &ptDst) { ClearResult() ; Sp_Point_t ptCurrent( make_shared<QPoint>( ptSrc ) ) ; unordered_set< string > Visited ; stack< Sp_Point_t > Stack ; // 入工作栈 Stack.push( ptCurrent ); // 记录当前顶点的前驱顶点 m_Parents[ ptCurrent ] = ptCurrent ; // 记录距离值 m_Distances[ ptCurrent ] = 0 ; // 加入访问路径序列 m_Points.push_back( ptCurrent ); // 设置访问标记 Visited.insert( ToString( ptCurrent ) ) ; for( ; Stack.size() > 0 ; ) { // 出栈一个点 ptCurrent = Stack.top() ; Stack.pop(); // 取得指定顶点的所有邻居顶点 vector< Sp_Point_t > AdjacentVertexes = GetAdjacentVertexes( Map , Visited , ptCurrent ); for( size_t idx = 0 ; idx < AdjacentVertexes.size() ; ++idx ) { Sp_Point_t pt = AdjacentVertexes[ idx ] ; // 入工作栈 Stack.push( pt ); // 设置访问标记 Visited.insert( ToString( pt ) ) ; // 记录当前顶点的前驱顶点 m_Parents[ pt ] = ptCurrent ; // 记录距离值 m_Distances[ pt ] = m_Distances[ ptCurrent ] + 1 ; // 把当前顶点加入访问路径序列 m_Points.push_back( pt ); // 访问顶点 if( *pt == ptDst ) { m_ptDst = pt ; return true ; } } } return false ; } bool CSearcher::Bfs(Map_t Map, const QPoint &ptSrc, const QPoint &ptDst) { ClearResult() ; Sp_Point_t ptCurrent( make_shared<QPoint>( ptSrc ) ) ; unordered_set< string > Visited ; queue< Sp_Point_t > Queue ; // 入工作栈 Queue.push( ptCurrent ); // 记录当前顶点的前驱顶点 m_Parents[ ptCurrent ] = ptCurrent ; // 记录距离值 m_Distances[ ptCurrent ] = 0 ; // 加入访问路径序列 m_Points.push_back( ptCurrent ); // 设置访问标记 Visited.insert( ToString( ptCurrent ) ) ; for( ; Queue.size() > 0 ; ) { // 出栈一个点 ptCurrent = Queue.front() ; Queue.pop(); // 取得指定顶点的所有邻居顶点 vector< Sp_Point_t > AdjacentVertexes = GetAdjacentVertexes( Map , Visited , ptCurrent ); for( size_t idx = 0 ; idx < AdjacentVertexes.size() ; ++idx ) { Sp_Point_t pt = AdjacentVertexes[ idx ] ; // 入工作栈 Queue.push( pt ); // 设置访问标记 Visited.insert( ToString( pt ) ) ; // 记录当前顶点的前驱顶点 m_Parents[ pt ] = ptCurrent ; // 把当前顶点加入访问路径序列 m_Points.push_back( pt ); // 记录距离值 m_Distances[ pt ] = m_Distances[ ptCurrent ] + 1 ; // 访问顶点 if( *pt == ptDst ) { m_ptDst = pt ; return true ; } } } return false ; } bool CSearcher::DfsRandomly(Map_t Map, const QPoint &ptSrc, const QPoint &ptDst) { ClearResult() ; size_t nCounter = 0 ; Sp_Point_t pt = make_shared<QPoint>( ptSrc ) ; unordered_set< string > Visited ; stack< Sp_Point_t > Stack ; // 入工作栈 Stack.push( pt ); // 记录当前顶点的前驱顶点 m_Parents[ pt ] = pt ; // 记录距离值 m_Distances[ pt ] = 0 ; // 加入访问路径序列 m_Points.push_back( pt ); // 设置访问标记 Visited.insert( ToString( pt ) ) ; // 访问顶点 m_VisitOrders[ pt ] = nCounter++ ; if( *pt == ptDst ) { m_ptDst = pt ; return true ; } for( ; Stack.size() > 0 ; ) { // 出栈一个点 Sp_Point_t ptCurrent = Stack.top() ; Stack.pop(); // 取得指定顶点的所有邻居顶点 vector< Sp_Point_t > AdjacentVertexes = GetAdjacentVertexes( Map , Visited , ptCurrent ); for( ; AdjacentVertexes.size() > 0 ; ) { // 从邻居顶点列表中，随机抽出一个顶点 int idx = rand() % AdjacentVertexes.size() ; Sp_Point_t pt = AdjacentVertexes[ idx ] ; AdjacentVertexes.erase( AdjacentVertexes.begin() + idx ) ; // 入工作栈 Stack.push( pt ); // 设置访问标记 Visited.insert( ToString( pt ) ) ; // 记录当前顶点的前驱顶点 m_Parents[ pt ] = ptCurrent ; // 记录距离值 m_Distances[ pt ] = m_Distances[ ptCurrent ] + 1 ; // 把当前顶点加入访问路径序列 m_Points.push_back( pt ); // 访问顶点 m_VisitOrders[ pt ] = nCounter++ ; if( *pt == ptDst ) { m_ptDst = pt ; return true ; } } } return false ; } bool CSearcher::BfsRandomly(Map_t Map, const QPoint &ptSrc, const QPoint &ptDst) { ClearResult() ; size_t nCounter = 0 ; Sp_Point_t pt = make_shared<QPoint>( ptSrc ) ; unordered_set< string > Visited ; queue< Sp_Point_t > Queue ; // 入工作栈 Queue.push( pt ); // 记录当前顶点的前驱顶点 m_Parents[ pt ] = pt ; // 记录距离值 m_Distances[ pt ] = 0 ; // 加入访问路径序列 m_Points.push_back( pt ); // 设置访问标记 Visited.insert( ToString( pt ) ) ; // 访问顶点 m_VisitOrders[ pt ] = nCounter++ ; if( *pt == ptDst ) { m_ptDst = pt ; return true ; } for( ; Queue.size() > 0 ; ) { // 出栈一个点 Sp_Point_t ptCurrent = Queue.front() ; Queue.pop(); // 取得指定顶点的所有邻居顶点 vector< Sp_Point_t > AdjacentVertexes = GetAdjacentVertexes( Map , Visited , ptCurrent ); for( ; AdjacentVertexes.size() > 0 ; ) { // 从邻居顶点列表中，随机抽出一个顶点 int idx = rand() % AdjacentVertexes.size() ; Sp_Point_t pt = AdjacentVertexes[ idx ] ; AdjacentVertexes.erase( AdjacentVertexes.begin() + idx ) ; // 入工作栈 Queue.push( pt ); // 设置访问标记 Visited.insert( ToString( pt ) ) ; // 记录当前顶点的前驱顶点 m_Parents[ pt ] = ptCurrent ; // 记录距离值 m_Distances[ pt ] = m_Distances[ ptCurrent ] + 1 ; // 把当前顶点加入访问路径序列 m_Points.push_back( pt ); // 访问顶点 m_VisitOrders[ pt ] = nCounter++ ; if( *pt == ptDst ) { m_ptDst = pt ; return true ; } } } return false ; } std::string CSearcher::ToString(const QPoint &pt) { format fmt( "%d#%d" ) ; fmt.bind_arg( 1 , pt.x() ) ; fmt.bind_arg( 2 , pt.y() ) ; return fmt.str() ; } std::string CSearcher::ToString( const shared_ptr<QPoint> &pt ) { format fmt( "%d#%d" ) ; fmt.bind_arg( 1 , pt.get()->x() ) ; fmt.bind_arg( 2 , pt.get()->y() ) ; return fmt.str() ; } vector<Sp_Point_t> CSearcher::GetAdjacentVertexes(Map_t Map, unordered_set< string > &Visited , const Sp_Point_t &pt) { vector<Sp_Point_t> AdjacentVertexes ; // 上 Sp_Point_t ptTest = make_shared<QPoint>( pt->x() , pt->y() -1 ) ; if( Map[ ptTest->y() ][ ptTest->x() ] == 0 && Visited.find( ToString( ptTest ) ) == Visited.end() ) { AdjacentVertexes.push_back( ptTest ); } // 上右 ptTest = make_shared<QPoint>( pt->x() + 1 , pt->y() - 1 ) ; if( Map[ ptTest->y() ][ ptTest->x() ] == 0 && Visited.find( ToString( ptTest ) ) == Visited.end() ) { AdjacentVertexes.push_back( ptTest ); } // 右 ptTest = make_shared<QPoint>( pt->x() + 1 , pt->y() ) ; if( Map[ ptTest->y() ][ ptTest->x() ] == 0 && Visited.find( ToString( ptTest ) ) == Visited.end() ) { AdjacentVertexes.push_back( ptTest ); } // 下右 ptTest = make_shared<QPoint>( pt->x() + 1 , pt->y() + 1 ) ; if( Map[ ptTest->y() ][ ptTest->x() ] == 0 && Visited.find( ToString( ptTest ) ) == Visited.end() ) { AdjacentVertexes.push_back( ptTest ); } // 下 ptTest = make_shared<QPoint>( pt->x() , pt->y() + 1 ) ; if( Map[ ptTest->y() ][ ptTest->x() ] == 0 && Visited.find( ToString( ptTest ) ) == Visited.end() ) { AdjacentVertexes.push_back( ptTest ); } // 下左 ptTest = make_shared<QPoint>( pt->x() - 1 , pt->y() + 1 ) ; if( Map[ ptTest->y() ][ ptTest->x() ] == 0 && Visited.find( ToString( ptTest ) ) == Visited.end() ) { AdjacentVertexes.push_back( ptTest ); } // 左 ptTest = make_shared<QPoint>( pt->x() - 1 , pt->y() ) ; if( Map[ ptTest->y() ][ ptTest->x() ] == 0 && Visited.find( ToString( ptTest ) ) == Visited.end() ) { AdjacentVertexes.push_back( ptTest ); } // 上左 ptTest = make_shared<QPoint>( pt->x() - 1 , pt->y() - 1 ) ; if( Map[