Comment utiliser Java pour implémenter l'algorithme de cycle hamiltonien des graphiques

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.

1. Représentation graphique
   Tout d'abord, nous devons utiliser une structure de données appropriée pour représenter le graphique. En Java, nous pouvons représenter des graphiques à l'aide de matrices de contiguïté ou de listes chaînées de contiguïté. Ici, nous choisissons d'utiliser une matrice de contiguïté pour représenter le graphique. Définissez une classe nommée 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]);
    }
}

2. 哈密顿回路算法
   接下来，我们将使用回溯法来实现哈密顿回路算法。定义一个名为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();
    }
}

3. 测试
   最后，我们可以使用以下代码来测试我们的实现：

rrreee

在这个测试示例中，我们创建了一个具有5个顶点的图，并添加了一些边。然后我们创建了一个HamiltonianCycle对象并调用findHamiltonianCycleAlgorithme du cycle hamiltonien

Ensuite, nous utiliserons la méthode Backtracking pour implémenter l'algorithme du cycle hamiltonien. Définissez une classe appelée HamiltonianCycle avec les méthodes suivantes : rrreee

Test

Enfin, nous pouvons utiliser le code suivant pour tester notre implémentation :

rrreee🎜Dans cet exemple de test, nous créons un graphe avec 5 sommets et ajoutons quelques arêtes. Ensuite, nous créons un objet 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!