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.
精彩评论