如何通過鄰接矩陣行進？

Question

說我有以下的鄰接矩陣產生

 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 

摹 - > d - >甲 - >乙

我知道BFS/DFS，但難倒什麼，我可以用這個矩陣這樣做，我可以實現BFS/DFS。

任何幫助表示感謝你！

Answer 1

如果您只需要查看是否可以使用某個節點，請使用BFS或DFS。

Answer 2

使用任何舊的圖形搜索，例如：

• Breadth-first search。
• Depth-first search。

Answer 3

如果你自己乘以鄰接矩陣，你會得到一個包含所有長度爲2的路徑的矩陣，依此類推。

您矩陣的n次方將向您顯示所有節點之間長度爲n的路徑的數量。

當然，如果你只需要兩個節點之間的距離，你不必做全矩陣乘法。