How to write a topological sorting algorithm using PHP

How to write a topological sorting algorithm using PHP

Topological sorting is an algorithm for sorting directed acyclic graphs (DAG). Its principle is to sort the nodes in the graph according to dependencies to ensure that the directions of all edges in the sorting results are consistent. In actual development, topological sorting is often used to solve problems such as task scheduling and dependency analysis. This article will introduce how to write a topological sorting algorithm using PHP, with code examples.

Algorithm idea:

1. Create an in-degree array to save the in-degree of each node (that is, how many nodes point to the node);
2. Create a result array to save the sorting results;
3. Traverse the nodes in the graph, calculate the in-degree of each node, and store it in the in-degree array;
4. Initialize a queue , put all nodes with an in-degree of 0 into the queue;
5. When the queue is not empty, dequeue one node from the queue in turn and add it to the result array;
6. Traverse For the neighbor nodes of this node, reduce the in-degree of each neighbor node by 1;
7. If the in-degree of the neighbor node is reduced to 0, add it to the queue;
8. Repeat steps 5 to 7 , until the queue is empty;
9. If the number of nodes in the result array is equal to the number of nodes in the graph, the sorting is successful; otherwise, there is a cycle in the graph and topological sorting cannot be performed.

The following is a code example of the PHP topological sorting algorithm written based on the above ideas:

<?php

function topologicalSort($graph) {
    $inDegree = []; // 入度数组
    $result = []; // 排序结果
    $queue = new SplQueue(); // 队列

    // 初始化入度数组
    foreach ($graph as $node => $neighbors) {
        $inDegree[$node] = 0;
    }

    // 计算入度数组
    foreach ($graph as $node => $neighbors) {
        foreach ($neighbors as $neighbor) {
            $inDegree[$neighbor]++;
        }
    }

    // 将入度为0的节点入队
    foreach ($inDegree as $node => $degree) {
        if ($degree == 0) {
            $queue->enqueue($node);
        }
    }

    // 队列不为空时
    while (!$queue->isEmpty()) {
        $node = $queue->dequeue();
        $result[] = $node;

        // 遍历邻居节点
        foreach ($graph[$node] as $neighbor) {
            $inDegree[$neighbor]--;
            if ($inDegree[$neighbor] == 0) {
                $queue->enqueue($neighbor);
            }
        }
    }

    // 判断是否成功排序
    if (count($result) == count($graph)) {
        return $result;
    } else {
        return false;
    }
}

// 测试用例
$graph = [
    'A' => ['B', 'C'],
    'B' => ['C', 'D'],
    'C' => ['E'],
    'D' => ['F'],
    'E' => [],
    'F' => ['G'],
    'G' => []
];

$result = topologicalSort($graph);
if ($result) {
    echo "拓扑排序结果: " . implode(' -> ', $result) . "
";
} else {
    echo "图中存在环，无法进行拓扑排序。
";
}

?>

In the above code, $graph represents the directed graph The relationship between nodes and their neighbor nodes. We perform topological sorting on the graph by calling the topologicalSort function, return the sorting result or determine whether there is a cycle. In the above example, the nodes in the graph are A, B, C, D, E, F, G, and the corresponding neighbor node relationships are defined in the $graph array. After running the code, the results of topological sorting will be output.

Summary:
This article introduces how to use PHP to write a topological sorting algorithm and gives corresponding code examples. Topological sorting is a practical algorithm often used to solve problems such as task scheduling. Mastering the topological sorting algorithm will help improve the processing capabilities of directed acyclic graphs and provide support for various dependency analysis during development. Hope this article is helpful to you.

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