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); 
} 

}