CODEWITHSUNDEEP
arraysalgorithmsearchgraphtraversal
intl
intl

Reputation: 2773

Graph/2-d array traversal and paths

I'm studying some computer science questions and many questions are about graph traversal and shortest paths. For example, you may be asked to find the shortest path from a point in the graph to another. In order to solve it, one would use breadth first search. The main thing is that graphs usually have correlating functions that give any adjacent nodes a node might have.

If, however, the question had a 2-d matrix of let's say 1's and 0's, where one 1's traversable and 0's are not, how would one go about solving such a problem? For example:

1101
0110
1011

If a coordinate is given, say [0][0], you may be asked to find all possible paths or the shortest path to the [n][n] point. How would you go about doing this? If anyone has any code examples, I would really appreciate it.

Upvotes: 0

Views: 1053

Answers (2)

beaker
beaker

Reputation: 16810

I'm assuming that the matrix you've presented is a sort of map or a maze rather than an adjacency matrix. As such, in your matrix

1101
0110
1011

you're allowed to go from [0][0] to [1][0], or from [1][1] to [1][0] or [2][1] and possibly [0][0], [0][2] and [2][2] if diagonal moves are allowed.

To apply graph algorithms to this sort of matrix you first need to convert it to an adjacency list or adjacency matrix by assigning an index to each entry, or node, in your matrix:

 0   1   2   3
 4   5   6   7
 8   9  10  11

Now you list all of the nodes that are reachable from node 0, or [0][0]:

0 -> 1, 5

since we can reach both nodes 1 and 5 from 0. (I'm assuming here that diagonal moves are allowed.) This gives you the first entry in the adjacency list. The equivalent for an adjacency matrix would be:

0 1 0 0 0 1 0 0 0 0 0 0

as the first row (row 0) of the matrix.

Repeat this process for each node in your matrix and you'll have your complete adjacency list or matrix to use in the normal graph algorithms.

Upvotes: 2

Mysterion
Mysterion

Reputation: 9320

Check some of the best algorithms for doing that - Dijkstra algorithm and BFS. It will solve your problem.

https://en.wikipedia.org/wiki/Breadth-first_search

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Upvotes: 0

Related Questions