CODEWITHSUNDEEP
javaadjacency-matrix
xiao
xiao

Reputation: 1758

How to travese through an adjacency matrix?

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!

Upvotes: 0

Views: 1347

Answers (3)

biziclop
biziclop

Reputation: 49804

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.

Upvotes: 0

rlibby
rlibby

Reputation: 6021

Use any old graph search, for example:

Upvotes: 0

Klark
Klark

Reputation: 8290

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

Upvotes: 2

Related Questions