How to implement graph topological sorting algorithm using java

How to use Java to implement the topological sorting algorithm of graphs

Introduction:
Graph is a very common data structure and has a wide range of applications in the field of computer science . The topological sorting algorithm is a classic algorithm in graph theory that can sort a directed acyclic graph (DAG) to determine the dependencies between nodes in the graph. This article will introduce how to use the Java programming language to implement the topological sorting algorithm of graphs, with specific Java code examples.

1. Define the data structure of the graph
Before implementing the topological sorting algorithm, we first need to define the data structure of the graph. To simplify the problem, we can use an adjacency list to represent the graph.

import java.util.*;

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

    // 其他图操作方法...
}

In the above code, we define a Graph class, which contains an integer V representing the number of vertices in the graph, and an adjacency listadj[] , used to store the adjacent vertices of each vertex.

2. Implement the topological sorting algorithm
The basic idea of ​​the topological sorting algorithm is to continuously delete vertices with an in-degree of 0 in the graph until all vertices in the graph are deleted. The following is a code example that uses Java to implement the topological sorting algorithm:

class TopologicalSorting {
    private Graph graph;
    private int V;
    private LinkedList<Integer> resultList;

    TopologicalSorting(Graph g) {
        graph = g;
        V = g.V;
        resultList = new LinkedList<>();
    }

    void topologicalSortUtil(int v, boolean visited[], Stack<Integer> stack) {
        visited[v] = true;

        Iterator<Integer> it = graph.adj[v].iterator();
        while (it.hasNext()) {
            int i = it.next();
            if (!visited[i])
                topologicalSortUtil(i, visited, stack);
        }

        stack.push(v);
    }

    void topologicalSort() {
        Stack<Integer> stack = new Stack<>();
        boolean visited[] = new boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                topologicalSortUtil(i, visited, stack);

        while (stack.empty() == false)
            resultList.add(stack.pop());
    }

    // 输出结果
    void printResult() {
        System.out.println("拓扑排序结果：");
        for (int i : resultList)
            System.out.print(i + " ");
        System.out.println();
    }
}

In the above code, the TopologicalSorting class is the class used for topological sorting. Among them, the topologicalSortUtil method is a recursive method used to implement specific sorting logic. The topologicalSort method is the entry method of topological sorting, which uses recursive method to sort all vertices one by one. The final printResult method is used to output the sorted results.

3. Example
The following is an example of using the topological sorting algorithm:

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

        TopologicalSorting ts = new TopologicalSorting(graph);
        ts.topologicalSort();
        ts.printResult();
    }
}

The code creates a directed graph and adds some edges. Then perform topological sorting and output the results through the TopologicalSorting class.

Conclusion:
This article introduces how to use Java language to implement the topological sorting algorithm of graphs, and gives specific code examples. Topological sorting algorithm is a classic algorithm to solve the problem of sorting vertex dependencies in graphs, and it is of great significance in practical applications. Through the introduction of this article, I hope to help readers understand and master this algorithm.

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