matrice d'adjacence en Java - chevauchement des bords

Question

J'ai une question très simple à poser. J'utilise une matrice d'adjacence (tableau 2D) dans Java pour créer un petit graphe avec des nœuds et des arêtes. Mon problème est que lorsque j'ordonne au programme de parcourir la matrice d'adjacence, en utilisant une simple boucle imbriquée, je rencontre le problème du chevauchement des bords. Pour être plus précis, quand la matrice [i] [j] est vraie et la matrice [j] [i] est vraie aussi, l'application essayera de dessiner 2 arêtes entre les nœuds i et j, ce qui serait une perte et une laideur .

Comment puis-je résoudre ce problème?

Answer 1

Ne pas itérer sur l'ensemble de la matrice, vous pouvez utiliser la moitié triangulaire supérieure (ou inférieure) et qui couvrira toutes les entrées qui vous intéressent.

En supposant que la matrice est diagonale symétrique, la moitié suffira. Si ce n'est pas symétrique, vous utilisez un graphe orienté (les arêtes ont des flèches) et vous souhaitez conserver ces arêtes dupliquées.

Un moyen facile de itérer à travers un demi triangulaire est ce genre de boucle imbriquée:

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

A partir j = i signifie l'itération de la colonne commence diagonale et saute la partie en double.

Answer 2

Il semble que ce soit un graphe non orienté, dans ce cas, seule la moitié supérieure (au-dessus de la diagonale) de la matrice contient réellement des données. Si tel est le cas:

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

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

Notez que cette itération il est impossible d'avoir des bords en double, car nous ne parcourons la moitié de la matrice.

Answer 3

juste passer par la moitié de la matrice (par exemple en dessous de la diagonale principale)

faire quelque chose comme

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