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

Comment utiliser Java pour implémenter l'algorithme du cycle d'Euler des graphiques ?

Le circuit eulérien est un problème classique de la théorie des graphes. Son essence est de trouver un chemin qui peut passer par chaque arête du graphique une et une seule fois, et enfin revenir au nœud de départ. Cet article expliquera comment utiliser le langage Java pour implémenter l'algorithme de cycle d'Euler des graphiques et fournira des exemples de code spécifiques.

1. Représentation graphique
Avant d'implémenter l'algorithme de boucle d'Euler, vous devez d'abord choisir une représentation graphique appropriée. Les représentations courantes incluent les matrices de contiguïté et les listes de contiguïté. Dans cet article, nous utiliserons des listes de contiguïté pour représenter des graphiques.

La liste de contiguïté est une structure de données de liste chaînée, qui représente chaque nœud du graphique comme un nœud de liste chaînée, qui enregistre les nœuds directement adjacents au nœud. Voici un exemple de graphique représenté par une liste de contiguïté :

import java.util.LinkedList;

// 图中的节点类
class Node {
    int val;
    LinkedList<Node> neighbors;

    public Node(int val) {
        this.val = val;
        this.neighbors = new LinkedList<Node>();
    }
}

// 图类
class Graph {
    LinkedList<Node> vertices;

    public Graph() {
        this.vertices = new LinkedList<Node>();
    }

    public void addNode(Node node) {
        vertices.add(node);
    }
}

Dans cet exemple, chaque nœud est représenté à l'aide de la classe Node, où l'attribut val représente la valeur du nœud et l'attribut voisins représente les nœuds directement adjacents au nœud. Le graphique est représenté par la classe Graph et ses sommets d'attribut sont une liste chaînée représentant tous les nœuds du graphique.

2. Implémentation de l'algorithme de boucle d'Euler
Ce qui suit est un exemple de code utilisant Java pour implémenter l'algorithme de boucle d'Euler :

import java.util.Stack;

// 图中的节点类
class Node {
    int val;
    LinkedList<Node> neighbors;
    boolean visited;

    public Node(int val) {
        this.val = val;
        this.neighbors = new LinkedList<Node>();
        this.visited = false;
    }
}

// 图类
class Graph {
    LinkedList<Node> vertices;

    public Graph() {
        this.vertices = new LinkedList<Node>();
    }

    public void addNode(Node node) {
        vertices.add(node);
    }

    // 深度优先搜索
    public void dfs(Node node) {
        System.out.print(node.val + " ");
        node.visited = true;

        for (Node neighbor : node.neighbors) {
            if (!neighbor.visited) {
                dfs(neighbor);
            }
        }
    }

    // 判断图是否连通
    public boolean isConnected() {
        for (Node node : vertices) {
            if (!node.visited) {
                return false;
            }
        }
        return true;
    }

    // 判断图中是否存在欧拉回路
    public boolean hasEulerCircuit() {
        for (Node node : vertices) {
            if (node.neighbors.size() % 2 != 0) {
                return false;
            }
        }
        return isConnected();
    }

    // 找到欧拉回路
    public void findEulerCircuit(Node node) {
        Stack<Node> stack = new Stack<Node>();
        stack.push(node);

        while (!stack.isEmpty()) {
            Node current = stack.peek();
            boolean hasUnvisitedNeighbor = false;

            for (Node neighbor : current.neighbors) {
                if (!neighbor.visited) {
                    stack.push(neighbor);
                    neighbor.visited = true;
                    current.neighbors.remove(neighbor);
                    neighbor.neighbors.remove(current);
                    hasUnvisitedNeighbor = true;
                    break;
                }
            }

            if (!hasUnvisitedNeighbor) {
                Node popped = stack.pop();
                System.out.print(popped.val + " ");
            }
        }
    }

    // 求解欧拉回路
    public void solveEulerCircuit() {
        if (hasEulerCircuit()) {
            System.out.println("欧拉回路：");
            findEulerCircuit(vertices.getFirst());
        } else {
            System.out.println("图中不存在欧拉回路！");
        }
    }
}

Dans cet exemple, nous définissons la classe Graph et la classe Node, où la classe Graph contient de la profondeur. première recherche (dfs), déterminez si le graphique est connecté (isConnected), déterminez s'il existe un circuit d'Euler dans le graphique (hasEulerCircuit), trouvez l'algorithme du circuit d'Euler (findEulerCircuit) et résolvez le circuit d'Euler (solveEulerCircuit) et d'autres méthodes.

3. Exemple d'utilisation
Ce qui suit est un exemple de la façon d'utiliser le code ci-dessus pour résoudre le problème du cycle d'Euler d'un graphe spécifique :

public class Main {
    public static void main(String[] args) {
        // 创建图
        Graph graph = new Graph();

        // 创建节点
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);

        // 添加节点
        graph.addNode(node1);
        graph.addNode(node2);
        graph.addNode(node3);
        graph.addNode(node4);
        graph.addNode(node5);

        // 建立节点之间的关系
        node1.neighbors.add(node2);
        node1.neighbors.add(node3);
        node1.neighbors.add(node4);
        node2.neighbors.add(node1);
        node2.neighbors.add(node3);
        node3.neighbors.add(node1);
        node3.neighbors.add(node2);
        node3.neighbors.add(node4);
        node4.neighbors.add(node1);
        node4.neighbors.add(node3);
        node5.neighbors.add(node2);
        node5.neighbors.add(node4);

        // 求解欧拉回路
        graph.solveEulerCircuit();
    }
}

Dans cet exemple, nous avons créé un graphe contenant 5 nœuds et établi la relation entre les nœuds. entre. Ensuite, nous appelons la méthode solveEulerCircuit dans la classe Graph pour résoudre le circuit d'Euler et afficher le résultat.

Résumé :
Cet article présente comment utiliser le langage Java pour implémenter l'algorithme de cycle d'Euler des graphiques. Tout d’abord, une méthode de représentation graphique appropriée a été sélectionnée, puis des algorithmes de base tels que la recherche en profondeur et la recherche de circuits d’Euler ont été implémentés. Enfin, un exemple d'utilisation spécifique est donné. J'espère que les lecteurs pourront mieux comprendre et maîtriser l'algorithme de boucle d'Euler des graphiques grâce à l'introduction et aux exemples de cet article.

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!