> Java > java지도 시간 > 본문

Java를 사용하여 그래프의 해밀턴 사이클 알고리즘을 구현하는 방법

王林
풀어 주다: 2023-09-21 09:03:32
원래의
1489명이 탐색했습니다.

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;
    }
}
로그인 후 복사
    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]);
    }
}
로그인 후 복사
  1. 哈密顿回路算法
    接下来,我们将使用回溯法来实现哈密顿回路算法。定义一个名为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();
    }
}
로그인 후 복사
  1. 测试
    最后,我们可以使用以下代码来测试我们的实现:
rrreee

在这个测试示例中,我们创建了一个具有5个顶点的图,并添加了一些边。然后我们创建了一个HamiltonianCycle对象并调用findHamiltonianCycleHamiltonian Cycle Algorithm

다음으로 역추적 메서드를 사용하여 구현하겠습니다. 해밀턴 사이클 알고리즘. 다음 메서드를 사용하여 HamiltonianCycle이라는 클래스를 정의합니다. rrreee

    Test

    마지막으로 다음 코드를 사용하여 구현을 테스트할 수 있습니다.
rrreee🎜이 테스트 예에서는 5개의 정점이 있는 그래프를 만들고 일부 가장자리를 추가합니다. 그런 다음 HamiltonianCycle 개체를 만들고 findHamiltonianCycle 메서드를 호출하여 해밀턴 순환을 찾아 출력합니다. 🎜🎜위 단계를 통해 Java 프로그래밍 언어를 사용하여 그래프의 해밀턴 사이클 알고리즘을 성공적으로 구현했습니다. 필요에 따라 정점 및 가장자리 연결 수를 변경한 다음 코드를 실행하여 알고리즘의 정확성과 효과를 확인할 수 있습니다. 🎜

위 내용은 Java를 사용하여 그래프의 해밀턴 사이클 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿