Wie man eine Adjazenzmatrix in Java implementiert, die Hamilton-Zyklen erzeugt

Question

Ich versuche eine Adjazenzmatrix in Java zu implementieren, die eine Ausgabe für einen Hamilton-Zyklus erzeugt, die dann mit verschiedenen Algorithmen wie kruskurals, dikstras und 2opt gelöst werden kann Ansatz. Ich weiß, dass ich ein 2D-Array brauche, aber ich weiß nicht, wo ich anfangen soll. Ich muss in der Lage sein, die Matrix zu speichern und sie auf den Graph anzuwenden, den ich habe, der momentan ein Kreis mit "n" Knoten ist (abhängig von der Matrix). Jede Hilfe ist willkommen, dank

Answer 1

Hier ist ein Skelett Sie arbeiten können:

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]; 
    } 
} 

Dinge, die Sie auf verbessern können:

• Vielleicht mehrere Kanten ermöglichen zwischen den Knoten?
• Vielleicht erlauben gewichtete Kanten?
• Vielleicht Node Typ anstelle von int Indizes für Vertices verwenden?
• etc ...