首先我要说明的是，我对节点和图的了解非常有限。
我的目标是为存储在数组中的迷宫创建一个求解器。我确切知道如何实现求解算法（实际上我正在实现几种算法），但我的问题在于，我对如何在每个空单元格中实现求解器使用的节点感到非常困惑。
这是一个示例数组：
char maze[5][9] = "#########", "# # #", "# ## ## #", "# # #", "#########"我的求解器从左上角开始，解决方案（出口）在右下角。
我已经阅读了节点的工作原理以及图的实现方式，所以这是我认为需要做的：
- 起点将成为一个节点
- 每个节点将具有列号和行号属性
- 每个节点还将具有访问状态属性
- 访问状态可以是
visited（已访问），visited and leads to dead end（已访问且通向死胡同），not visited（未访问） - 每当一个节点被访问时，每个直接相邻的、空的且未访问的单元格将成为该访问节点的子节点
- 每个访问过的节点都会被放置在solutionPath堆栈的顶部（并在地图上标记为’*’）
- 每个导致死胡同的节点将从堆栈中移除（并在地图上标记为’~’）
完成的迷宫示例：
"#########","#*~#****#","#*##*##*#","#****~#*#","#########"我的问题基本上是，我这样思考是否有什么愚蠢的地方（因为我对节点真的很不熟练），如果有，请解释一下为什么？另外，如果可能的话，请提供其他网站供我查看，这些网站实现了图在现实世界应用中的示例，以便我能更好地理解它。
回答：
答案真的取决于你认为问题中什么是最重要的。如果你寻找的是效率和速度——你添加的节点太多了。没有必要添加那么多节点。
高效的方法
你的求解器只需要在路径的起点和终点，以及地图上的每个可能的拐角处设置节点。就像这样：
"#########","#oo#o o#","# ## ## #","#o oo#o#","#########"没有必要测试地图上的其他地方——你要么必须经过这些地方，要么根本不需要测试这些地方。
如果你觉得有帮助——我有一个设计用于简单图表示的模板digraph类。它写得不是很好，但它非常适合展示可能的解决方案。
#include <set>#include <map>template <class _nodeType, class _edgeType>class digraph{public: set<_nodeType> _nodes; map<pair<unsigned int,unsigned int>,_edgeType> _edges;};我使用这个类在塔防游戏中使用 Dijkstra算法寻找路径。这种表示对于任何其他算法来说应该都足够了。
节点可以是任何给定类型——你可能会使用pair<unsigned int, unsigned int>。 _edges通过它们在集合中的position连接两个_nodes。
易于编码的方法
另一方面——如果你寻找的是易于实现的方法——你只需要将数组中的每个空格视为可能的节点。如果这是你想要的——没有必要设计图，因为数组完美地表示了问题。
你不需要专门的类来以这种方式解决它。
bool myMap[9][5]; //包含地图信息的数组。0 = 不可通过，1 = 可通过vector<pair<int,int>> route; //你需要走的路线pair<int,int> start = pair<int,int>(1,1); //路线从(1,1)开始pair<int,int> end = pair<int,int>(7,3); //路线在(7,3)结束route = findWay(myMap,start,end); //使用你编写的算法寻找路线其中findWay的原型是vector<pair<int,int>> findWay(int[][] map, pair<int,int> begin, pair<int,int> end)，并实现你想要的算法。在函数内部，你可能需要另一个二维布尔类型数组，用于指示哪些地方已经被测试过。
当算法找到一条路线时，你通常需要反向读取它，但我猜这取决于算法。
在你的特定示例中，myMap将包含：
bool myMap[9][5] = {0,0,0,0,0,0,0,0,0, 0,1,1,0,1,1,1,1,0, 0,1,0,0,1,0,0,1,0, 0,1,1,1,1,1,0,1,0, 0,0,0,0,0,0,0,0,0};而findWay将返回一个包含(1,1),(1,2),(1,3),(2,3),(3,3),(4,3),(4,2),(4,1),(5,1),(6,1),(7,1),(7,2),(7,3)的vector
