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 因为他们中的任何一个都可能从 table 上掉下来，因此不是邻居。现在简单地用一对整数标识每个顶点 - 它的坐标并将对推送到队列中。当从队列中弹出时，使用我上面所说的访问四个可能的邻居。

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