实现没有邻接表的bfs

我正在解决BFS上的问题。我能够通过邻接表实现BFS算法，但我被困在这个问题中：我必须告诉是否有可能从起点行进迷宫到迷宫终点的距离。单元格包含0或1。由于它不能通过包含值1的单元格传播，并且两个单元格之间的移动只有在它们共享一个公共边缘时才有可能。那么如何直接在这里实现BFS而不需要进入邻接表呢？实现没有邻接表的bfs

来源

2013-09-26 TSP1993

如何查看相邻单元格的地图（2d数组）而不是邻接列表？ – Shahbaz

@Shahbaz你不需要明确存储邻接表来解决问题。 –

@IvayloStrandjev，是不是我说的？ – Shahbaz

您不必将图形显式表示为做BFS的邻接表。从每个单元格(x,y)你知道哪些是它的4个潜在的邻居 - (x-1, y),(x, y-1),(x+1, y)和(x, y+1)。我说potential，因为它们中的任何一个都可能脱离桌子，因此不能成为邻居。现在只需用一对整数 - 它的坐标和队列中的推对来标识每个顶点。当从队列中弹出时，使用上面所述的方法访问四个可能的邻居。

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

来源

2013-09-26 12:20:08

是啊，现在我明白了。但我不知道要在C中使用pair吗？ – TSP1993

不，我不想要的代码。 – TSP1993

@RahulKumarSingh，只是得到两个不同的变量。有你的一对！但是，严重的是，你创建一个'struct'把这两个变量放在里面。 – Shahbaz

实现没有邻接表的bfs

回答

相关问题