如何在图形表示为二维数组时显示图形可达性？

Question

假设问题是我们想要查找给定图中是否有可能从源S到目的地D的路径。用'。'，'X'，'S'，'D'表示的图形。 ''表示可用空间，'X'表示阻塞区域，'S'表示源'D'表示目的地。

假设给定的图被表示为二维数组，这样

...SXX.. 
XX...X.. 
X..X.... 
XX....X. 
XXXX.... 
...D.... 

我知道，我们可以使用DFS或BFS，但问题是如何在图中二维数组的形式给出执行这些。将这个Matrix转换成Adjacency列表是否有效，或者我们可以直接应用DFS或BFS？如果是，那么如何？

Answer 1

将此矩阵转换为邻接表或甚至邻接表将采用O（4e）其中e表示阵列中的条目数。之后，通过BFS或DFS查找它们是否与OFS（4e）相连，因为边的数量以4e为界，每个上，下，左，右都有一个边。因此，转换到BFS或DFS大约需要O（8e）。

不进行转换的算法如下（这是一个稍微修改BFS）：

int x 
int y 
char givenGraph[x][y] 
boolean pathExists 

// sourceX and sourceY represent the location of the 'S' 
start(int sourceX, int sourceY, int destinationX, int destinationY) { 
    recursiveCheck(sourceX, sourceY, destinationX, destinationY)) 
    if(!pathExists) { 
     print("Path does not exist!") 
    } 
} 

recursiveCheck(int currentX, int currentY) { 

    if(givenGraph[currentX][currentY] == 'D') { // if the destination then say so 
     print("Path exists!") 
     pathExists = true 
    } 
    else if(givenGraph[currentX][currentY] == 'X') { // if a wall then return 
     return 
    } 
    else if(givenGraph[currentX][currentY] == 'C') { // if already checked return 
     return 
    } 
    else { // not checked yet, either 'S' or '.' so mark 
     givenGraph[currentX][currentY] = 'C' // for checked 
    }   

    if(currentX + 1 < x) { // check left 
     recursiveCheck(currentX + 1, currentY) 
    } 
    if(currentX - 1 >= 0) { // check right 
     recursiveCheck(currentX - 1, currentY) 
    } 
    if(currentY + 1 < y) { // check up 
     recursiveCheck(currentX, currentY + 1) 
    } 
    if(currentY - 1 >= 0) { // check down 
     recursiveCheck(currentX, currentY - 1) 
    } 
} 

这种递归算法检查上，下，左，右为每个条目，并假定“S”位置是已知的。已知'S'的复杂性大约是O（4e）。通过搜索表中的所有条目，查找'S'将会带O（e）。因此，这种算法的效率是O（5e）。

转换可以进一步优化，就像上面的算法一样。这个简化的非转换版本是为了表明它可以像转换一样高效或更高效。

另一方面，这个递归算法确实会覆盖'S'。它不得不稍微修改以免覆盖'S'。