Comment utiliser Java pour implémenter l'algorithme du cycle hamiltonien pour les graphiques
Un cycle hamiltonien est un problème informatique en théorie des graphes, qui consiste à trouver un chemin fermé contenant tous les sommets d'un graphe donné. Dans cet article, nous présenterons en détail comment implémenter l'algorithme du cycle hamiltonien à l'aide du langage de programmation Java et fournirons des exemples de code correspondants.
Graph
avec les propriétés et méthodes suivantes : 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
Algorithme du cycle hamiltonien
HamiltonianCycle
avec les méthodes suivantes : rrreeeTest
Enfin, nous pouvons utiliser le code suivant pour tester notre implémentation :HamiltonianCycle
et appelons la méthode findHamiltonianCycle
pour rechercher et afficher le cycle hamiltonien. 🎜🎜Grâce aux étapes ci-dessus, nous avons implémenté avec succès l'algorithme du cycle hamiltonien du graphique à l'aide du langage de programmation Java. Vous pouvez modifier le nombre de sommets et de connexions d'arêtes selon vos besoins, puis exécuter le code pour vérifier l'exactitude et l'effet de l'algorithme. 🎜Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!