如何使用Java實作圖的哈密頓迴路演算法
哈密頓迴路是一種圖論中的計算問題,即在給定的圖中找到一條包含所有頂點的閉合路徑。在這篇文章裡,我們將詳細介紹如何使用Java程式語言實作哈密頓迴路演算法,並提供對應的程式碼範例。
Graph
的類,包含以下屬性和方法: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; } }
HamiltonianCycle
的類,包含以下方法: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]); } }
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
方法來尋找並輸出哈密頓迴路。
透過上述步驟,我們成功地實作了使用Java程式語言實作圖的哈密頓迴路演算法。你可以根據需要更改頂點數量以及邊的連接關係,然後運行程式碼來驗證演算法的正確性和效果。
以上是如何使用java實作圖的哈密頓迴路演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章!