java - Java中的邻接矩阵 - 边缘重叠

Question

我有一个非常简单的问题要问。

我在java中使用邻接矩阵（二维数组）来创建一个带有节点和边的小图。

我的问题是，当我使用简单的嵌套循环指示程序遍历邻接矩阵时，我遇到了边缘重叠的问题。更具体地说，当 matrix[i][j] 为 true 且 matrix[j][i] 为 true 时，应用程序将尝试在节点 i 和 j 之间绘制 2 条边，这将是一种浪费和丑陋的外观。

我怎样才能克服这个问题？

Answer 1

不要遍历整个矩阵，您可以使用上三角半部分（或下半部分），这将涵盖您感兴趣的所有条目。

假设矩阵是对角对称的，任何一半都足够了。如果它不是对称的，那么您正在使用有向图（边有箭头）并且您希望保留那些重复的边。

遍历三角形一半的简单方法是这种嵌套循环：

for(i=0;i<n;i++){
  for(j=i;j<m;j++){
   whatever(i,j);
  }
 }

开始 j=i 意味着柱状迭代从对角线开始并跳过重复的部分。

Answer 2

只需穿过矩阵的一半（即在主对角线下方）

做类似的事情

for(i=1; i<= size; i++)
  for(j=i+1; j<= size; j++) 
     // draw

Answer 3

听起来这是一个无向图，在这种情况下，只有矩阵的上半部分（对角线上方）真正包含任何数据。如果是这种情况：

int[][] foo = //...

for(int i = 0; i < foo.length; i++){
    for(int j = i; j < foo[j].length; j++){
        // ...
    }
}

请注意，使用此迭代不可能有重复的边，因为我们只迭代矩阵的一半。