algorithm - 实现没有邻接表的 bfs

Question

我正在解决 BFS 上的问题。我能够通过邻接列表在 C 中实现 BFS 算法，但我陷入了这个问题：我必须判断是否可以从迷宫的起点移动到迷宫的终点迷宫。单元格包含 0 或 1。考虑到它不能穿过包含值 1 的单元格的限制，并且只有当它们共享一个共同的边缘时，两个单元格之间的移动才可能。那么如何直接在这里实现BFS而不用邻接表呢？

Answer 1

您不必将图形明确表示为邻接列表即可执行 BFS。从每个单元格中，(x,y)您知道哪些是它的 4 个潜在邻居 - (x-1, y)、(x, y-1)和。我说是因为他们中的任何一个都可能从桌子上掉下来，因此不是邻居。现在简单地用一对整数识别每个顶点 - 它的坐标并将对推入队列。当从队列中弹出时，使用我上面所说的访问四个可能的邻居。(x+1, y)(x, y+1)potential

希望这足以帮助您 - 我可以提供完整的代码，但最好是您自己编写。