How to use java to implement the Euler cycle algorithm of graphs

How to use Java to implement the Euler cycle algorithm of graphs?

Eulerian loop is a classic graph theory problem. Its essence is to find a path that can pass through each edge in the graph once and only once, and finally return to the starting node. This article will introduce how to use Java language to implement the Euler cycle algorithm of graphs, and provide specific code examples.

1. Graph representation method
Before implementing the Euler loop algorithm, you first need to choose a suitable graph representation method. Common representations include adjacency matrices and adjacency lists. In this article, we will use adjacency lists to represent graphs.

The adjacency list is a linked list data structure that represents each node in the graph as a linked list node, which records the nodes directly adjacent to the node. The following is an example of a graph represented by an adjacency list:

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);
    }
}

In this example, each node is represented by the Node class, where the attribute val represents the value of the node, and the attribute neighbors represents the nodes directly adjacent to the node. node. The graph is represented by the Graph class, and its attribute vertices is a linked list representing all nodes in the graph.

2. Implementation of Euler loop algorithm
The following is a code example of using Java to implement the Euler loop algorithm:

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("图中不存在欧拉回路！");
        }
    }
}

In this example, we define the Graph class and the Node class , the Graph class includes depth-first search (dfs), judging whether the graph is connected (isConnected), judging whether there is a Euler circuit in the graph (hasEulerCircuit), finding the Euler circuit algorithm (findEulerCircuit) and solving the Euler circuit (solveEulerCircuit) and other methods.

3. Usage Example
The following is an example of how to use the above code to solve the Euler circuit problem of a specific graph:

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();
    }
}

In this example, we create a A graph of 5 nodes and establishes the relationships between nodes. Then we call the solveEulerCircuit method in the Graph class to solve the Euler circuit and output the result.

Summary:
This article introduces how to use Java language to implement the Euler loop algorithm of graphs. First, a suitable graph representation method was selected, and then core algorithms such as depth-first search and finding Euler circuits were implemented. Finally, a specific usage example is given. I hope readers can better understand and master the Euler loop algorithm of graphs through the introduction and examples of this article.

The above is the detailed content of How to use java to implement the Euler cycle algorithm of graphs. For more information, please follow other related articles on the PHP Chinese website!