java或C++中的鄰接矩陣找到連接節點

Question

我給出了一個問題，我已經給出了一個圖中的N個節點互相連接，然後給出一個矩陣，列出一個節點連接到另一個節點（1 if它是，如果不是0）。我想知道如何最好地解決這個問題。我認爲這些是鄰接矩陣？但我將如何實現...

基本上我試圖擺脫這些是找到一個特定節點是否連接到給定集'S'中的所有其他節點。無論選定的項目是否集團或不...

我會很感激任何提示。

Answer 1

可以使用布爾值的2維數組實現這一點。所以，如果節點i連接到節點j，那麼myarray [i] [j]將是真實的。如果你的邊不是方向性的，那麼myarray [i] [j]就是myarray [j] [i]。

這也可以通過使用整數（或其他數值類型）而不是布爾值作爲數組的元素來擴展到加權邊。

Answer 2

提示：所以你有你的鄰接矩陣M它告訴你，如果兩個節點直接連接。那麼M^2給你什麼？它會告訴您兩個節點之間是否存在長度爲2的路徑。

我讓你想象是什麼立方公尺，...，M^INF（當你到達固定點）

Answer 3

要做到這一點，最簡單的方法是使用方陣（2d數組），無論是布爾值來顯示是否存在連接或整數來表示遍歷的代價。但是，對於稀疏圖，可以通過使用鋸齒狀數組來獲得更好的壓縮效果，然後存儲哪些節點與第一個節點相鄰。在Java中，我可能會做一個List<List<Integer>>，其中外部列表​​對應於所討論的節點，而內部列表是與該列表相鄰的所有節點。

假設您決定使用標準（未壓縮）矩陣，您可以通過迭代列表來查找節點i是否與列表中的每個節點j相鄰，然後查找A [i] [j] 。如果它們中的任何一個是false，則它不與列表中的每個項目相鄰，否則它是真實的。對於一個派系，你只需要爲列表中的每個項目執行此操作（刪除i = j的情況並對無向圖進行優化）。

一個例子（再次用Java）

public boolean isClique(boolean[][] A, List<Integer> nodes){ 
    for(int i : nodes){ 
    for(int j : nodes){ 
     if(i != j){ 
     if(!A[i][j]) return false; 
     } 
    } 
    } 
    return true; 
} 

優化和到最大 - 派問題的解決方案都留給讀者作爲練習給讀者。

Answer 4

使用您的鄰接矩陣，應用Floyd-Warshall algorithm將爲您提供節點之間的所有路徑。然後你可以檢查特定的設置。

Answer 5

您可能想要使用bitset或bit_vector而不是bool [] []。

如果您不使用鋸齒陣列，並且您的連接是對稱的，請考慮使用基於MIN（）的訪問器進行封裝​​（）& MAX（）[macros]。在兩個地方存儲相同的數據是痛苦的祕訣。最終，array [i] [j]！= array [j] [i]。

E.g: getValue(int i, int j) { return array [ MIN(i,j) ] [ MAX(i,j) ] } 

Answer 6

試試這個：

public class AdjacencyMatrix { 

private String [] nodes; 

private int [][] matrix; 

public AdjacencyMatrix(String [] nodes,int [][] matrix){ 
    this.nodes = nodes; 
    this.matrix = matrix; 
} 

boolean isSymmetric(){ 
    boolean sym = true; 
    for(int i=0;i<matrix.length;i++){ 
     for(int j=i+1; j < matrix[0].length ; j++){ 
      if (matrix[i][j] != matrix[j][i]){ 
       sym = false; 
       break; 
      } 
     } 
    } 
    return sym; 
} 

public Graph createGraph(){ 
    Graph graph = new Graph(); 
    Node[] NODES = new Node[nodes.length]; 

    for (int i=0; i<nodes.length; i++){ 
     NODES[i] = new Node(nodes[i]); 
     graph.addNode(NODES[i]); 
    } 

    for(int i=0;i<matrix.length;i++){    
     for(int j=i;j<matrix[0].length;j++){ 
      int distance = matrix[i][j]; 
      if (distance != 0){      
       graph.addEdge(new Edge(NODES[i], NODES[j], distance)); 
      } 
     } 
    } 

    return graph; 
} 


public long pathLength(int[] path){ 
    long sum = 0; 
    for (int i=0; i<path.length - 1; i++){ 
     if (matrix[path[i]][path[i+1]] != 0) 
      sum += matrix[path[i]][path[i+1]]; 
     else { 
      sum = 0; 
      break; 
     } 
    } 

    return sum; 
} 


public static void main(String[] args){ 
    String[] nodes = {"A", "B", "C", "D", "E"}; 
    int [][] matrix= { {0, 2, 2, 1, 0}, 
         {2, 0, 1, 0, 0}, 
         {2, 1, 0, 0, 1}, 
         {1, 0, 0, 0, 4}, 
         {0, 0, 1, 4, 7}}; 
    AdjacencyMatrix am = new AdjacencyMatrix(nodes, matrix); 
    Graph graph = am.createGraph(); 
    int[] a = {0, 2, 4, 4, 3, 0}; 
    int[] b = {0, 1, 2, 4, 4, 3, 0}; 
    graph.writeGraph(); 
    am.pathLength(a); 
    am.pathLength(b); 
} 

}