How to travese through an adjacency matrix?

Question

Say I have the following adjacency matrix produced

     A B C D E F G H I    
   A 0 1 0 1 0 0 0 0 0
   B 1 0 0 0 0 0 0 0 0
   C 0 0 0 1 0 0 0 0 0
   D 1 0 1 0 0 0 1 0 0
   E 0 0 0 0 0 1 0 0 0
   F 0 0 0 0 1 0 0 0 0
   G 0 0 0 1 0 0 0 0 0
   H 0 0 0 0 0 0 0 0 1
   I 0 0 0 0 0 0 0 1 0

Whats the best way to traverse through to confirm that I can go from G to B? since

  [G][D] = true
  [A][D] = true
  [A][B] = true

G-->D-->A-->B

I am aware of BFS/DFS but stumped as to what I can do with this matrix so that I can implement BFS/DFS for it.

Any help is appreciated thank you!

Answer 1

If you only need to see if you can reach some node use BFS or DFS.

Answer 2

Use any old graph search, for example:

• Breadth-first search.
• Depth-first search.

Answer 3

If you multiply the adjacency matrix by itself, you'll get a matrix that contains all paths with a length of 2 and so on.

Your matrix raised to the power of n will show you the number of paths of length n between all the nodes.

Of course if you only need the distance between two nodes, you don't have to do the full matrix multiplication.