0

次の隣接行列を作成したとします

     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

G から B に移動できることを確認するためにトラバースする最良の方法は何ですか? 以来

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

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

私は BFS/DFS を認識していますが、このマトリックスを使って何ができるかについて困惑しているので、BFS/DFS を実装することができます。

どんな助けでも大歓迎ですありがとう！

4

3 に答える 3

2

一部のノードに到達できるかどうかを確認するだけでよい場合は、BFSまたはDFSを使用してください。

于 2011-02-15T11:38:32.877 に答える
0

たとえば、古いグラフ検索を使用します。

于 2011-02-15T11:45:46.687 に答える
0

隣接行列をそれ自体で乗算すると、長さが 2 などのすべてのパスを含む行列が得られます。

行列を n 乗すると、すべてのノード間の長さ n のパスの数が表示されます。

もちろん、2 つのノード間の距離だけが必要な場合は、完全な行列乗算を行う必要はありません。

于 2011-02-15T11:54:31.263 に答える