matriz de adyacencia en Java - solapamiento borde

Question

Tengo una pregunta muy simple para preguntar.

Estoy utilizando una matriz de adyacencia (matriz 2D) en Java para crear una pequeña gráfica con nodos y los bordes.

Mi problema es que cuando me instruir al programa para iterar a través de la matriz de adyacencia, usando un bucle anidado simple, experimento el problema de la superposición de borde. Para ser más específicos, cuando matriz [i] [j] es verdadera y matriz [j] [i] es verdad también la aplicación va a tratar de extraer 2 bordes entre los nodos i y j que sería un desperdicio y de aspecto feo.

¿Cómo puedo superar ese problema?

Answer 1

No iterar a través de toda la matriz, se puede utilizar el medio triangular superior (o la más baja) y que cubrirá todas las entradas que le interesa.

Suponiendo que la matriz es diagonal simétrica, ya sea un medio será suficiente. Si no es simétrica, entonces usted está usando un grafo dirigido (bordes tienen flechas) y que se quiere preservar esos bordes duplicados.

Una manera fácil para iterar a través de un medio triangular es este tipo de bucle anidado:

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

A partir j = i significa la iteración columnares comienza a partir de la diagonal y se salta la parte duplicada.

Answer 2

sólo tiene que ir a través de un medio de la matriz (es decir, por debajo de la diagonal principal)

hacer algo como

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

Answer 3

Suena como este es un grafo no dirigido, en ese caso sólo la mitad superior (por encima de la diagonal) de la matriz realmente contiene ningún dato. Si este es el caso:

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

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

Tenga en cuenta que el uso de esta iteración es imposible tener bordes duplicados, ya que sólo una iteración en la mitad de la matriz.