Java를 사용하여 위상 정렬 알고리즘을 구현하는 방법

Java를 사용하여 위상 정렬 알고리즘을 구현하는 방법

위상 정렬은 그래프 이론에서 흔히 사용되는 알고리즘으로 방향성 비순환 그래프(DAG)의 정점을 정렬하는 데 사용됩니다. 토폴로지 정렬은 종속성 또는 작업 예약과 같은 문제를 해결하는 데 사용할 수 있습니다. 이 기사에서는 Java를 사용하여 위상 정렬 알고리즘을 구현하는 방법을 소개하고 해당 코드 예제를 제공합니다.

위상 정렬의 구현 아이디어는 다음과 같습니다.

1. 먼저 인접 목록으로 표현할 수 있는 유방향 그래프의 데이터 구조를 정의해야 합니다. 인접리스트(Adjacency List)는 그래프를 저장하는 자료구조이다. 각 정점은 연결리스트(Linked List)에 해당하고, 연결리스트(Linked List)는 정점에 인접한 모든 정점을 저장한다.

class Graph {
    private int V; // 图的顶点数
    private LinkedList<Integer> adj[]; // 邻接表

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i) {
            adj[i] = new LinkedList<>();
        }
    }

    // 添加边
    void addEdge(int v, int w) {
        adj[v].add(w);
    }
}

2. 그런 다음 위상 정렬 방법을 구현해야 합니다. 위상 정렬의 구현 프로세스는 두 단계로 나눌 수 있습니다:

   a 그래프를 탐색하고, 각 정점의 차수를 계산하고(즉, 정점이 이를 가리키는 수), 정점을 저장하기 위해 대기열을 초기화합니다. 0도.

   b. 계속해서 큐에서 정점을 꺼내고 인접한 정점의 차수를 줄이세요. 정점의 차수가 0이 되면 대기열에 추가하세요.

   c. 대기열이 비어 있고 모든 정점의 차수가 0이 될 때까지 (b) 단계를 반복합니다. 이때 큐에 입력된 정점의 개수가 그래프의 정점 개수와 같지 않으면 그래프에 순환이 존재하여 토폴로지 정렬을 완료할 수 없다는 의미입니다.

import java.util.*;

class TopologicalSort {
    // 拓扑排序算法
    void topologicalSort(Graph graph) {
        int V = graph.V;
        LinkedList<Integer> adj[] = graph.adj;

        int[] indegree = new int[V];
        for (int i = 0; i < V; ++i) {
            for (int j : adj[i]) {
                indegree[j]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < V; ++i) {
            if (indegree[i] == 0) {
                queue.add(i);
            }
        }

        int count = 0;
        ArrayList<Integer> result = new ArrayList<>();

        while (!queue.isEmpty()) {
            int u = queue.poll();
            result.add(u);

            for (int v : adj[u]) {
                if (--indegree[v] == 0) {
                    queue.add(v);
                }
            }
            count++;
        }

        if (count != V) {
            System.out.println("图中存在环，无法进行拓扑排序");
            return;
        }

        System.out.println("拓扑排序结果：");
        for (int i : result) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

3. 마지막으로 그래프를 만들고 위상 정렬 방법을 호출하여 정렬할 수 있습니다.

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addEdge(5, 2);
        graph.addEdge(5, 0);
        graph.addEdge(4, 0);
        graph.addEdge(4, 1);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);

        TopologicalSort topologicalSort = new TopologicalSort();
        topologicalSort.topologicalSort(graph);
    }
}

위는 Java에서 위상 정렬 알고리즘을 구현하는 단계와 코드 예제입니다. 토폴로지 정렬 알고리즘을 통해 종속성이나 작업 스케줄링과 같은 문제를 효과적으로 해결할 수 있습니다.

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