如何在圖形表示爲二維數組時顯示圖形可達性？

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'。