Idées de conception d'algorithmes PHP : comment parvenir à une solution efficace au problème de tri topologique ?

Idées de conception d'algorithmes PHP : Comment parvenir à une solution efficace au problème de tri topologique ?

Le tri topologique est un problème classique de la théorie des graphes. Son objectif principal est de trier un graphe acyclique orienté (DAG) afin que tous les sommets du graphe satisfassent à la condition selon laquelle le degré entrant est inférieur ou égal au degré sortant. . Le tri topologique est largement utilisé dans de nombreux scénarios, tels que la planification des tâches, la conception du compilateur, etc.

Dans cet article, nous présenterons une solution efficace pour implémenter le tri topologique à l'aide du langage PHP. Tout d’abord, nous discuterons des principes de base des algorithmes de tri topologique, puis donnerons des exemples de code spécifiques.

1. Principe de l'algorithme de tri topologique

L'algorithme de tri topologique est principalement basé sur l'idée de recherche en profondeur d'abord (DFS) ou de recherche en largeur (BFS). Plus précisément, l'algorithme de tri topologique contient les étapes suivantes :

a) Tout d'abord, nous devons construire une représentation de liste de contiguïté du graphe orienté, où chaque sommet sert d'index du tableau, puis le sommet pointé par le sommet sert d'index. comme valeur du tableau.

b) Ensuite, nous sélectionnons un sommet avec un degré 0 dans le graphique comme sommet de départ et l'ajoutons à une file d'attente.

c) Ensuite, nous parcourons les sommets de la file d'attente et réduisons le degré entrant de ses sommets adjacents de 1. Si le degré en entrée d'un sommet adjacent est 0, ajoutez-le à la file d'attente.

d) Répétez le processus ci-dessus jusqu'à ce que la file d'attente soit vide. Enfin, les sommets de la file d’attente obtenue sont le résultat d’un tri topologique.

2. Implémentation du code de l'algorithme de tri topologique

Ce qui suit est un exemple de code utilisant le langage PHP pour implémenter l'algorithme de tri topologique :

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 . ' ';
}

Dans le code ci-dessus, une classe Graph est d'abord définie, qui contient le constructeur et la méthode addEdge. pour ajouter des arêtes et une méthode de tri topologique topologicalSort. Dans la fonction principale, nous créons un graphe orienté et effectuons un tri topologique, et enfin produisons les résultats selon le tri topologique.

Résumé :

En expliquant les principes et la mise en œuvre spécifique de l'algorithme de tri topologique, et en le combinant avec des exemples de code, une solution efficace est implémentée dans le langage PHP. Le tri topologique peut jouer un rôle important dans de nombreuses applications pratiques et nous aider à résoudre divers problèmes de planification des tâches et de dépendances.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!