Comment implémenter une matrice d'adjacence dans Java produisant des cycles de hamilton

Question

J'essaye d'implémenter une matrice d'adjacence dans Java qui produira une sortie pour un cycle hamiltonien, qui peut alors être résolu avec différents algorithmes tels que kruskurals, djikstras et le 2opt approche. Je sais que j'ai besoin d'un tableau 2d mais je ne sais pas par où commencer. J'ai besoin de pouvoir stocker la matrice et l'appliquer au graphe que j'ai, qui est actuellement un cercle avec "n" nœuds (dépendant de la matrice). toute aide est la bienvenue, merci

Answer 1

Voici un squelette que vous pouvez travailler à partir de:

public class Graph { 
    public final int V; 
    private boolean[][] hasEdge; 

    public Graph(int V) { 
     this.V = V; 
     hasEdge = new boolean[V][V]; 
    } 

    public void addEdge(int v1, int v2) { 
     hasEdge[v1][v2] = hasEdge[v2][v1] = true; 
    } 
    public boolean hasEdge(int v1, int v2) { 
     return hasEdge[v1][v2]; 
    } 
} 

Les choses que vous pouvez améliorer:

• permettent peut-être plusieurs arêtes entre les noeuds?
• Peut-être autoriser les bords lestés?
• Peut-être utiliser Node type au lieu de int indices pour les sommets?
• etc ...