How to solve graph reachability when the graph is represented as 2-D array?

Question

Suppose the question is we want to find whether a path is possible from Source S to Destination D in the graph given. Graph represented by characters '.','X','S','D' . '.' represents free space, 'X' represents blocked area, 'S' is Source 'D' is destination.

Suppose the given graph is represented as 2D array like this

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

I know that we can use DFS or BFS but the problem is how to perform these when the graph is given in the form of 2D array. Is converting this Matrix to Adjacency list the efficient way or we can directly apply DFS or BFS ? If yes,then how ?

All you need to know for a given position is connectivity to its neighbors, right? So you just look at each of the neighbors and see if they have something other than a .. — beaker

D. Law. D. Law. · Accepted Answer · 2016-09-05T17:33:58

Converting this matrix to an adjacency list, or even an adjacency table, would take O(4e) where e represents the number of entries in the array. After that, finding if they are linked by BFS or DFS would just be around O(4e) since the number of edges is bounded by 4e, one edge per up, down, left, and right. Thus, conversion then BFS or DFS would take about O(8e).

An algorithm that does not do the conversion is as follows (it is a slightly modified 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)
    }
}

This recursive algorithm checks up, down, left, and right for each entry, and it assumes that the "S" location is known. With the 'S' known, the complexity is about O(4e). Finding 'S' would take O(e) by just searching all the entries in the table. Therefore, the efficiency of this algorithm is O(5e).

The conversion can be optimized further, as can the above algorithm. This simplified non-conversion version was to show that it can be as efficient or more efficient then a conversion.

On a side not, this recursive algorithm does overwrite the 'S'. It would have to be modified slightly to not overwrite 'S'.

How to solve graph reachability when the graph is represented as 2-D array?

1 Answers