Wie man mit Java den Hamilton-Zyklus-Algorithmus für Graphen implementiert
Ein Hamilton-Zyklus ist ein Rechenproblem in der Graphentheorie, bei dem es darum geht, einen geschlossenen Pfad zu finden, der alle Eckpunkte in einem bestimmten Graphen enthält. In diesem Artikel stellen wir detailliert vor, wie der Hamilton-Zyklus-Algorithmus mithilfe der Programmiersprache Java implementiert wird, und stellen entsprechende Codebeispiele bereit.
Graph
mit den folgenden Eigenschaften und Methoden: class Graph { private int[][] adjacencyMatrix; private int numVertices; public Graph(int numVertices) { this.numVertices = numVertices; adjacencyMatrix = new int[numVertices][numVertices]; } public void addEdge(int start, int end) { adjacencyMatrix[start][end] = 1; adjacencyMatrix[end][start] = 1; } public boolean isConnected(int start, int end) { return adjacencyMatrix[start][end] == 1; } }
Graph
的类,包含以下属性和方法:class HamiltonianCycle { private Graph graph; private int numVertices; private int[] path; public HamiltonianCycle(Graph graph) { this.graph = graph; this.numVertices = graph.getNumVertices(); this.path = new int[numVertices]; // 将路径初始化为-1,表示顶点还未被遍历 for (int i = 0; i < numVertices; i++) { path[i] = -1; } } public void findHamiltonianCycle() { path[0] = 0; // 从顶点0开始 if (findFeasibleSolution(1)) { printSolution(); } else { System.out.println("No solution exists."); } } private boolean findFeasibleSolution(int position) { if (position == numVertices) { int start = path[position - 1]; int end = path[0]; if (graph.isConnected(start, end)) { return true; } else { return false; } } for (int vertex = 1; vertex < numVertices; vertex++) { if (isFeasible(vertex, position)) { path[position] = vertex; if (findFeasibleSolution(position + 1)) { return true; } // 回溯 path[position] = -1; } } return false; } private boolean isFeasible(int vertex, int actualPosition) { // 两个相邻顶点之间必须是连通的 if (!graph.isConnected(path[actualPosition - 1], vertex)) { return false; } // 该顶点是否已经在路径中 for (int i = 0; i < actualPosition; i++) { if (path[i] == vertex) { return false; } } return true; } private void printSolution() { System.out.println("Hamiltonian Cycle exists:"); for (int i = 0; i < numVertices; i++) { System.out.print(path[i] + " "); } System.out.println(path[0]); } }
HamiltonianCycle
的类,包含以下方法:public class Main { public static void main(String[] args) { Graph graph = new Graph(5); graph.addEdge(0, 1); graph.addEdge(0, 3); graph.addEdge(1, 2); graph.addEdge(1, 3); graph.addEdge(1, 4); graph.addEdge(2, 4); graph.addEdge(3, 4); HamiltonianCycle hamiltonianCycle = new HamiltonianCycle(graph); hamiltonianCycle.findHamiltonianCycle(); } }
在这个测试示例中,我们创建了一个具有5个顶点的图,并添加了一些边。然后我们创建了一个HamiltonianCycle
对象并调用findHamiltonianCycle
Hamilton-Zyklus-Algorithmus
HamiltonianCycle
mit den folgenden Methoden: rrreeeTest
Abschließend können wir den folgenden Code verwenden, um unsere Implementierung zu testen:HamiltonianCycle
-Objekt und rufen die Methode findHamiltonianCycle
auf, um den Hamilton-Zyklus zu finden und auszugeben. 🎜🎜Durch die oben genannten Schritte haben wir den Hamilton-Zyklusalgorithmus des Diagramms erfolgreich mithilfe der Programmiersprache Java implementiert. Sie können die Anzahl der Scheitelpunkte und Kantenverbindungen nach Bedarf ändern und dann den Code ausführen, um die Richtigkeit und Wirkung des Algorithmus zu überprüfen. 🎜Das obige ist der detaillierte Inhalt vonSo implementieren Sie den Hamilton-Zyklus-Algorithmus von Graphen mit Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!