Java を使用してグラフのハミルトニアン サイクル アルゴリズムを実装する方法

Java を使用してグラフのハミルトニアン サイクル アルゴリズムを実装する方法

ハミルトニアン サイクルは、グラフ理論における計算問題、つまり、グラフ内のパスを見つけることです。与えられたグラフ すべての頂点を含む閉じたパス。この記事では、Java プログラミング言語を使用してハミルトニアン サイクル アルゴリズムを実装する方法と、対応するコード例を詳しく紹介します。

1. グラフ表現
   まず、グラフを表現するために適切なデータ構造を使用する必要があります。 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;
    }
}

2. ハミルトニアン サイクル アルゴリズム
   次に、バックトラッキング メソッドを使用してハミルトニアン サイクルを実装します。アルゴリズム。次のメソッドを使用して、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]);
    }
}

3. Testing
   最後に、次のコードを使用して実装をテストできます。

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 中国語 Web サイトの他の関連記事を参照してください。