开发者

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!


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


Use any old graph search, for example:

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


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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜