How to implement topological sorting algorithm using java

How to use Java to implement topological sorting algorithm

Topological sorting is a commonly used algorithm in graph theory, used for directed acyclic graph (Directed Acyclic Graph, DAG for short) vertices are sorted. Topological sorting can be used to solve problems such as dependencies or task scheduling. In this article, we will introduce how to use Java to implement the topological sorting algorithm and give corresponding code examples.

The implementation idea of ​​topological sorting is as follows:

1. First, we need to define a data structure of a directed graph, which can be represented by an adjacency list. An adjacency list is a data structure that stores graphs. Each vertex corresponds to a linked list, and the linked list stores all vertices adjacent to the vertex.

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. Then, we need to implement topological sorting method. The implementation process of topological sorting can be divided into two steps:

   a. Traverse the graph, calculate the in-degree of each vertex (that is, how many vertices point to it), and initialize a queue to store the in-degree of 0 the apex.

   b. Continuously take out a vertex from the queue and reduce the in-degree of its adjacent vertices. If the in-degree of a vertex becomes 0, add it to the queue.

   c. Repeat step (b) until the queue is empty and the in-degree of all vertices becomes 0. If the number of vertices enqueued at this time is not equal to the number of vertices of the graph, it means that there is a cycle in the graph and topological sorting cannot be completed.

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. Finally, we can create a graph and call the topological sort method to sort it.

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

The above are the steps and code examples for using Java to implement the topological sorting algorithm. Through topological sorting algorithms, we can effectively solve problems such as dependencies or task scheduling.

The above is the detailed content of How to implement topological sorting algorithm using java. For more information, please follow other related articles on the PHP Chinese website!