我正在解决 BFS 上的问题。我能够通过邻接表在 C 中实现 BFS 算法，但我陷入了这个问题: 我必须判断是否可以从迷宫的起点移动到迷宫的终点。单元格包含 0 或 1。考虑到它不能穿过包含值 1 的单元格并且在 之间移动仅当两个单元共享公共(public)边缘时，它们才是可能的。 那么这里如何不经过邻接表直接实现BFS呢？
最佳答案
您不必将图显式表示为邻接列表即可进行 BFS。从每个单元格 (x,y) 中，您可以知道其 4 个潜在邻居 - (x-1, y)、(x, y-1)、(x+1, y) 和 (x, y+1)。我说潜在是因为他们中的任何一个都可能从 table 上掉下来，因此不是邻居。现在只需用一对整数(其坐标)来标识每个顶点，并将对推送到队列中。当从队列中弹出时，使用我上面所说的访问四个可能的邻居。
希望这足以帮助您 - 我可以提供完整的代码，但您最好自己编写。
关于algorithm - 实现无邻接表的 bfs，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19027999/