2

我遇到了一个问题,我在图中给出了 N 个节点,这些节点相互连接,然后给出一个矩阵,其中列出了一个节点连接到另一个节点(如果是,则为 1,如果不是,则为 0)。我想知道如何最好地解决这个问题。我认为这些是邻接矩阵?但是我将如何实现...

基本上,我试图摆脱这些的是找出特定节点是否连接到给定集合“S”中的所有其他节点。以及所选项目是否为集团...

我会很感激任何提示。

4

6 回答 6

7

您可以使用二维布尔数组来实现这一点。因此,如果节点 i 连接到节点 j,则 myarray[i][j] 将为真。如果您的边缘不是定向的,那么 myarray[j][i] 将在 myarray[i][j] 为真时为真。

这也可以通过使用整数(或其他数字类型)而不是布尔值作为数组元素来扩展到加权边。

于 2008-12-08T13:07:37.073 回答
3

最简单的方法是使用方阵(2d 数组),使用布尔值来显示连接的存在或不存在,或者使用整数来表示遍历的成本。然而,对于稀疏图,您可以通过使用锯齿状数组然后存储与第一个节点相邻的节点来获得更好的压缩。在 Java 中,我可能会通过设置一个List<List<Integer>>外部列表对应于所讨论的节点而内部列表是与该节点相邻的所有节点来做到这一点。

假设您决定使用标准(未压缩)矩阵,您可以通过遍历列表然后查找 A[i][j] 来确定节点 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;
}

Max-Clique 问题的优化和解决方案留给读者作为练习。

于 2008-12-08T14:04:15.150 回答
3

试试这个:

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

}
于 2009-06-07T17:13:00.070 回答
2

提示:所以你有你的邻接矩阵M,它告诉你两个节点是否直接连接。那么 M^2 给了你什么?它告诉您两个节点之间是否存在长度为 2 的路径。

我让你想象什么是 M^3,... , M^inf (当你到达固定点时)

于 2008-12-08T13:05:57.183 回答
1

使用您的邻接矩阵,应用Floyd-Warshall 算法将为您提供节点之间的所有路径。然后你可以检查特定的集合。

于 2008-12-08T14:43:32.107 回答
0

您可能想使用bitsetbit_vector代替 bool[][]。

如果您不使用锯齿状数组,并且您的连接是对称的,请考虑使用基于 MIN() 和 MAX() [宏] 的访问器进行包装。在两个地方存储相同的数据是一个痛苦的秘诀。最终,array[i][j] != array[j][i]。

E.g: getValue( int i, int j ) { return array [ MIN(i,j) ] [ MAX(i,j) ] }
于 2008-12-08T19:28:18.053 回答