Créer des structures de données liées à partir du tableau

Question

Je suis novice en matière de structures de données liées et je me demandais comment créer un graphe non orienté lorsqu'on lui donnait 2 points à partir d'un tableau 2d et qu'aucun poids n'était déterminé entre les points. J'ai cherché autour et je ne pouvais pas vraiment trouver ce que je cherchais.

Exemple:

int[][] points = { { 0, 1 },{ 0, 2 },{ 1, 2 },{ 1, 3 },{ 3, 4 } }; 

étirées il devrait ressembler à ceci.

 0 
     | 
    ------- 
    |  | 
    1-----2 
    | 
    3-----4 

EDIT

Je veux aussi être en mesure de trouver le chemin le plus court de 0 à 4 et traversant à chaque point au moins une fois en comptant chaque mouvement le long du chemin. Il est possible que vous deviez reculer. Dans l'exemple ci-dessus, le chemin le plus court de 0 à 4 est (0-2) (2-1) (1-3) (3-4) et compte pour être 4 coups.

Answer 1

1. Créer une classe Noeud qui contient une liste des noeuds adjacents
2. à travers vos nœuds Itérer dans le tableau des points . Créer un objet de nœud pour chaque nœud que vous trouverez (probablement il serait préférable de les garder dans une carte au début.
3. Itérer encore une fois et remplir la liste des noeuds adjacents pour chaque noeud.

Considérez cette classe noeud:

public class Node { 
    private int id; 
    private List<Node> adjacentNodes = new ArrayList<Node>(); 

    public List<Node> getAdjacentNodes() { 
     return adjacentNodes; 
    } 

    public int getId() { 
     return id; 
    } 

    public void setId(int id) { 
     this.id = id; 
    } 
} 

et cette méthode crée une collection de tous les nœuds et ils sont reliés entre eux:

private static Collection<Node> createGraphNodes(int[][] pointsMatrix) { 
    Map<Integer, Node> nodes = new HashMap<Integer, Node>(); 
    for(int[] points: pointsMatrix) { 
     for(int point: points) { 
      if(nodes.containsKey(Integer.valueOf(point))) { 
       continue; 
      } 

      Node node = new Node(); 
      node.setId(point); 
      nodes.put(point, node); 
     } 
    } 

    for(int[] points: pointsMatrix) { 
     int nodeId1 = points[0]; 
     int nodeId2 = points[1]; 

     Node node1 = nodes.get(Integer.valueOf(nodeId1)); 
     Node node2 = nodes.get(Integer.valueOf(nodeId2)); 

     node1.getAdjacentNodes().add(node2); 
     node2.getAdjacentNodes().add(node1); 

    } 

    return nodes.values(); 

Answer 2

Il y a deux façons de base représenter des graphiques.

Matrice d'adjacence et listes d'adjacence. Pour mettre en œuvre des listes d'adjacence, vous créez une liste pour chaque nœud et vous mettez dans la liste tous les nœuds auxquels le nœud respectif est connecté.

Voici plus sur les représentations du graphique: http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29#Representations

Answer 3

La façon la plus simple de représenter des graphiques est d'utiliser la matrice de contiguïté, qui est une matrice booléenne à deux dimensions dans lequel les lignes et les colonnes représentent des noeuds dans le graphique, et l'intersection entre les états d'une ligne et d'une colonne s'ils sont connectés. Il en contient un s'ils sont connectés à zéro sinon.

Par exemple, votre graphique ci-dessus sera:

 0 1 2 3 4 
0 [0] [1] [1] [0] [0] 
1 [1] [0] [1] [1] [0] 
2 [1] [1] [0] [0] [0] 
3 [0] [1] [0] [0] [1] 
4 [0] [0] [0] [1] [0]