用C++实现寻路的几种方法。
地图
思前想后我决定用链表来存储地图，也就是用vector<int>按顺序存储地图的节点，由于地图一般是矩形的，知道高度与宽度后我们无需再存储位置信息，每个节点的内容可以是地形高度。用数组也是可以的，但栈中的数组需要确定大小，动态数组很好，但为了方便删除元素还是用效率低的vector容器吧。
points存储每个节点的高度，target存储目标节点的序号，landing存储登陆点的序号，width与length用于根据序号推算节点位置，height是寻路对象能够跨越的最大高度，track记录路径，find标记是否已到达所有终点。除了track与find，其余成员变量都要初始化。
class Graph{
private:
vector<int> points;
vector<int> target;
int landing;
int width,length;
int height;
vector<int> track;
bool find=false;
}
DFS
先写一个启动DFS的函数，用于未找到路径时输出结果。
void startDFS()
{
DFS(this->landing);
if (this->find == false)
{
cout << "未找到路径!" << endl;
}
}
DFS主函数检查周围的点是否已访问或符合规则，然后访问。访问后节点height被标记为-1，checkEnd用于判断是否已到达全部终点并修改find的值，checkNeighbor用于把将要访问的点放入neighbor。
bool DFS(int start)
{
vector<int> neighbor;
//如果已经找到那么结束
if (this->find == true)
{
return false;
}
//如果已经访问过那么返回
if (points[start]==-1)
{
return false;
}
else
{
points[start]=-1;
track.push_back(start);
}
checkEnd(start);
checkNeighbor(start, &neighbor);
for (int i = 0; i < neighbor.size(); i++)
{
DFS(neighbor[i]);
}
track.pop_back(); //返回上级时弹出
}
checkEnd函数：
void checkEnd(int start)
{
for (int k = 0; k < target.size(); k++)
{
if (start == target[k])
{
cout << "经过了" << start << endl;
target[k] = -1; //标记已到达
bool visitedAll = true;
for (int i = 0; i < target.size(); i++)
{
if (target[i] != -1)
{
visitedAll = false;
}
}
if (visitedAll == true)
{
cout << "已全部到达!" << endl;
this->find = true;
for (int i = 0; i < track.size(); i++)
{
cout <<"("<< track[i]/width <<","<<track[i]%width<<")"<< endl;
}
}
}
}
}
checkNeighbor函数，通过有关计算确定一个位置的上/下/左/右等位置是否存在节点。
void checkNeighbor(int start, vector<int> *neighbor)
{
int leftTop = -1, top = -1, rightTop = -1, left = -1, right = -1, bottom = -1, leftBottom = -1, rightBottom = -1;
bool hasLeft = false, hasRight = false, hasTop = false, hasBottom = false;
if (start % width != 0)
{
hasLeft = true;
}
if ((start + 1) % width != 0)
{
hasRight = true;
}
if (start - width >= 0)
{
hasTop = true;
}
if (start + width < width * height)
{
hasBottom = true;
}
//8个方向的数组序号
if (hasTop && hasLeft)
{
leftTop = start - width - 1;
if (abs(points[start] - points[leftTop]) >= maxZ)
{
leftTop = -1;
}
}
if (hasTop)
{
top = start - width;
if (abs(points[start] - points[top]) >= maxZ)
{
top = -1;
}
}
if (hasRight && hasTop)
{
rightTop = start - width + 1;
if (abs(points[start] - points[rightTop]) >= maxZ)
{
rightTop = -1;
}
}
if (hasLeft)
{
left = start - 1;
if (abs(points[start] - points[left]) >= maxZ)
{
left = -1;
}
}
if (hasRight)
{
right = start + 1;
if (abs(points[start] - points[right]) >= maxZ)
{
right = -1;
}
}
if (hasLeft && hasBottom)
{
leftBottom = start + width - 1;
if (abs(points[start] - points[leftBottom]) >= maxZ)
{
leftBottom = -1;
}
}
if (hasRight && hasBottom)
{
rightBottom = start + width + 1;
if (abs(points[start] - points[rightBottom]) >= maxZ)
{
rightBottom = -1;
}
}
if (hasBottom)
{
bottom = start + width;
if (abs(points[start] - points[bottom]) >= maxZ)
{
bottom = -1;
}
}
//添加到neighbor
if (leftTop != -1)
{
//neighbor.push_back(&points[leftTop]);
neighbor->push_back(leftTop);
}
if (top != -1)
{
//neighbor.push_back(&points[top]);
neighbor->push_back(top);
}
if (rightTop != -1)
{
neighbor->push_back(rightTop);
}
if (left != -1)
{
neighbor->push_back(left);
}
if (right != -1)
{
neighbor->push_back(right);
}
if (leftBottom != -1)
{
neighbor->push_back(leftBottom);
}
if (bottom != -1)
{
neighbor->push_back(bottom);
}
if (rightBottom != -1)
{
neighbor->push_back(rightBottom);
}
}
BFS
虽然我把BFS遍历写出来了，但BFS不方便记录轨迹，因为访问元素是依次加入队列的，之间没有父子关系。如果要记录路径的话，需要知道路径上每个节点的父节点，也就是要形成一颗BFS树：每个节点都记录自己的父节点。
那么BFS记录轨迹的方法就是，将邻居节点加入队列时，节点信息要包括本节点，收集从队列中弹出的节点（收集访问过的节点，可以组织成一棵树），当找到终点时，反向寻找出发点。