PHP algorithm design ideas: How to achieve an efficient solution to the topological sorting problem?

PHP algorithm design ideas: How to achieve an efficient solution to the topological sorting problem?

Topological sorting is a classic problem in graph theory. Its main goal is to sort a directed acyclic graph (DAG) so that all vertices in the graph satisfy the condition that the in-degree is less than or equal to the out-degree. Topological sorting is widely used in many scenarios, such as task scheduling, compiler design, etc.

In this article, we will introduce an efficient solution to implement topological sorting using PHP language. First, we will discuss the basic principles of topological sorting algorithms, and then give specific code examples.

1. Principle of topological sorting algorithm

The topological sorting algorithm is mainly based on the idea of ​​depth-first search (DFS) or breadth-first search (BFS). Specifically, the topological sorting algorithm contains the following steps:

a) First, we need to construct an adjacency list representation of the directed graph, where each vertex serves as an index of the array, and then the vertex pointed by the vertex as an array value.

b) Then, we select a vertex with in-degree 0 from the graph as the starting vertex and add it to a queue.

c) Next, we traverse the vertices in the queue and reduce the in-degree of its adjacent vertices by 1. If the in-degree of an adjacent vertex is 0, add it to the queue.

d) Repeat the above process until the queue is empty. Finally, the vertices in the obtained queue are the results of topological sorting.

2. Topological sorting algorithm code implementation

The following is a code example using PHP language to implement the topological sorting algorithm:

class Graph {
    private $adjList;

    public function __construct() {
        $this->adjList = [];
    }

    public function addEdge($src, $dest) {
        if (!isset($this->adjList[$src])) {
            $this->adjList[$src] = [];
        }
        $this->adjList[$src][] = $dest;
    }

    public function topologicalSort() {
        $inDegree = [];
        foreach ($this->adjList as $src => $destList) {
            $inDegree[$src] = 0;
        }

        foreach ($this->adjList as $src => $destList) {
            foreach ($destList as $dest) {
                $inDegree[$dest]++;
            }
        }

        $queue = new SplQueue();
        foreach ($inDegree as $src => $in) {
            if ($in == 0) {
                $queue->enqueue($src);
            }
        }

        $result = [];

        while (!$queue->isEmpty()) {
            $src = $queue->dequeue();
            $result[] = $src;

            if (isset($this->adjList[$src])) {
                foreach ($this->adjList[$src] as $dest) {
                    $inDegree[$dest]--;
                    if ($inDegree[$dest] == 0) {
                        $queue->enqueue($dest);
                    }
                }
            }
        }

        return $result;
    }
}

$g = new Graph();
$g->addEdge(1, 3);
$g->addEdge(1, 4);
$g->addEdge(2, 4);
$g->addEdge(3, 5);
$g->addEdge(4, 5);

$result = $g->topologicalSort();

foreach ($result as $vertex) {
    echo $vertex . ' ';
}

In the above code, a Graph class is first defined , which contains the constructor, the method addEdge for adding edges, and the method topologicalSort for topological sorting. In the main function, we create a directed graph and perform topological sorting, and finally output the results according to the topological sorting.

Summary:

By explaining the principles and specific implementation of the topological sorting algorithm, and combining it with code examples, an efficient solution is implemented in the PHP language. Topological sorting can play an important role in many practical applications and help us solve various task scheduling and dependency problems.

The above is the detailed content of PHP algorithm design ideas: How to achieve an efficient solution to the topological sorting problem?. For more information, please follow other related articles on the PHP Chinese website!