Leetcode: 210. Programme II

Source du sujet

• leetcode

Description du sujet

Analyse du sujet

Seuls les graphiques acycliques dirigés ont l'ordre topologique

Le Tri topologique n'est pas un algorithme de tri pur,C'est juste pour une classe de graphiques,Trouver un ordre linéaire exécutable.

Pour quel type de diagramme?？Graphique acyclique dirigé.Même si：

• Les bords de ce graphique doivent être orientés;
• Pas d'anneau dans le dessin.

Alors quelle est la direction？

Par exemple, les amis de Wechat sont orientés,Tu as ajouté son ami, il t'a peut - être effacé et tu ne sais pas...Alors cette amitié est unidirectionnelle..

Qu'est - ce qu'un anneau？L'anneau est lié à la direction,Pour revenir à soi - même à partir d'un point,C'est un anneau..

Donc ce n'est pas l'anneau à gauche en bas,À droite..

Donc si un diagramme a des anneaux,Comme sur la photo de droite,Je veux exécuter1Il faut d'abord3,Je veux exécuter3Il faut d'abord2,Je veux exécuter2Il faut d'abord1,C'est un cercle vicieux.,Impossible de trouver le bon mode d'ouverture,Il n'y a donc pas d'ordre topologique..

Conclusions：

• Si ce n'est pas le cas, DAG,Donc il n'y a pas d'ordre topologique;
• Si oui DAG,Il a donc au moins un ordre topologique;
• Au contraire,S'il y a un ordre topologique,Donc cette image doit être DGA.

Pour cette question, Le Tri topologique signifie ： Résoudre un ordre réalisable ,Ça m'a permis d'apprendre toutes les leçons.

Alors comment faire？

（1）D'abord, nous pouvons le décrire avec des graphiques, Les deux éléments du graphique sont Sommets et bords,Alors voilà.：

• Vertex：Chaque cours
• Edge：Le cours de départ est la première étape du cours de fin

S'il y avait une telle image ：

Cette image s'appelleAOV(Activity On Vertex) Réseau,Dans cette image：

• Vertex：Activités de représentation;
• Edge：Représente la relation séquentielle entre les activités

Donc un AOV Le filet devrait être un DAG,Graphique acyclique dirigé,Sinon, certaines activités ne peuvent pas être menées.

Toutes les activités peuvent alors être rangées dans une séquence linéaire viable,Cette séquence est une séquence topologique.

La signification pratique de cette séquence est donc：

Dans cet ordre,Au début de chaque projet,Pour s'assurer que ses activités d'avant - garde sont terminées,Pour que l'ensemble du projet se déroule sans heurt.

Pour revenir à notre exemple：

• On peut le voir en un coup d'oeil. C1, C2,Parce qu'il n'y a pas de demande pour les deux cours.,En première année;
• En deuxième année, on peut apprendre la deuxième ligne C3, C5, C8 C'est,Parce que la première de ces trois leçons est C1, C2,On a fini.;
• La troisième année peut apprendre la troisième ligne C4, C9;
• Choisissez le reste de la dernière année C6, C7.

Voilà.,On va finir tous les cours,Et nous obtenons un ordre topologique de ce graphique.

Attention!,Parfois, l'ordre topologique n'est pas unique,Dans ce cas, par exemple,,Apprends d'abord. C1 On recommence. C2,Et le premier. C2 Après C1 C'est bon.,Est l'ordre topologique correct de ce graphique,Mais il y a deux ordres.

Alors demandez à l'intervieweur,Est une solution arbitraire,Ou Lister toutes les solutions.

Les bords de ce graphique représentent une dépendance,Si je dois suivre un cours,Il va falloir d'abord prendre le cours précédent

C'est la même chose qu'un jeu.,J'ai besoin d'un accessoire.,Il faut d'abord A Mission,Terminé. B Mission,Enfin, on arrive à destination.

Sur l'image ci - dessus,Vous pouvez facilement voir son ordre topologique,Mais quand le projet devient de plus en plus volumineux,Les dépendances peuvent aussi devenir complexes,Il faut donc une approche systématique pour résoudre.

Alors rappelons - nous le processus de recherche de l'ordre topologique par nous - mêmes,Pourquoi avons - nous commencé par C1, C2?

Parce qu'ils ne dépendent pas des autres,C'est - à - dire que son degré de pénétration est 0.

• Pénétration：La Pénétrance d'un Vertex est「Bord pointant vers le Sommet」Nombre de;
• Sortie：La sortie d'un Vertex est le nombre de bords que le Vertex pointe vers d'autres points.

Donc nous commençons par le degré de pénétration de 0 Ces points,C'est pourquoi nous Pour enregistrer l'intensité de chaque Vertex . Parce que ce n'est que si son degré est 0Quand,On peut l'exécuter..

Dans l'exemple précédent,,Au début. C1, C2 Le degré de pénétration est 0,Donc nous pouvons commencer par les deux.

La première étape de cet algorithme est d'obtenir l'intensité de chaque Vertex.

（1）Le prétraitement donne la pénétration de chaque point

On peut utiliser un HashMap Pour stocker cette information,Ou un tableau serait plus élaboré.

Après avoir eu ça,,Vous pouvez effectuer une entrée de 0 Ces points,C'est - à - dire C1, C2.

Alors nous allons mettre en œuvre ces points,Mets - en un. Dans le récipient à exécuter ,Après ça, nous prendrons les sommets de ce conteneur un par un.

Quelle structure de données ce conteneur choisit - il exactement?,Ça dépend de ce qu'il faut faire.,Et voir quelle structure de données peut servir.

Donc d'abord, vous pouvez mettre**[C1, C2]**Dans un contenant,

Et pensez à ce qu'il faut faire.！

Ce que nous faisons le plus souvent, c'est Mets le point. ,J'ai pris le point et je l'ai exécuté,Donc vous pouvez utiliser unqueue

Les autres aussi.,Les sommets placés dans ce récipient ont le même statut,Tout est exécutable,Ça n'a rien à voir avec l'ordre d'arrivée,Mais pourquoi vous embêter?？Simple dans un ordre régulier queue Ça suffit..

Et puis il y a des choses à faire..

Quand on met C1 Sortez - le et exécutez - le.,Ça veut dire quoi?？

Réponse：Ce qui signifie「Par C1 Pour les sommets」De「Pointez vers un autre point」De「Edge」Tout a disparu,C'est - à - dire C1 La sortie de 0.

Comme le montre la figure ci - dessous:,C'est - à - dire que ces deux côtés peuvent disparaître.

Alors nous pouvons mettre à jour C1 Ces points sont C3 Et C8 De Pénétration C'est,Le tableau mis à jour est le suivant：

Alors nous voyons ici une étape cruciale,C8 Est devenu 0！

Ce qui signifie C8 Il n'y a plus de dépendance pour le moment,On peut le mettre sur nous. queue En attente d'exécution.

En ce moment queue Oui.：[C2, C8].

Ensuite, on fera C2

Alors C2 Pointé C3, C5 De Pénétration-1,

Mise à jour des tableaux：

C'est - à - dire C3 Et C5 Il n'y a plus de liens.,Peut être placé dans queue C'est fait..

queue C'est devenu：[C8, C3, C5]
Ensuite, nous allons C8

Correspondant C8 La référence à C9 Pénétration-1.Mise à jour des tableaux：

Alors C9 Il n'y a pas de demande.,Peut être placé dans queue C'est fait..

queue C'est devenu：[C3, C5, C9]

Exécution suivante C3,

Correspondant C3 La référence à C4 Pénétration-1.Mise à jour des tableaux：

Mais C4 Le degré de pénétration n'est pas devenu 0,Donc il n'y a rien à ajouter à cette étape queue.

queue C'est devenu [C5, C9]

Re - exécution C5

Alors C5 La référence à C4 Et C6 Pénétration- 1.Mise à jour des tableaux：

Ici. C4 La dépendance a disparu,Alors vous pouvez mettre C4 Mets - le dedans. queue C'est parti.：

queue = [C9, C4]

Step6

Et ensuite exécuter C9

Alors C9 La référence à C7 Pénétration- 1

Ici. C7 N'est pas 0,Pas encore queue,

En ce moment queue = [C4]
Et ensuite C4

Alors... C4 Pointé C6 Et C7 Pénétration-1,Mise à jour des tableaux：

C6 Et C7 Les degrés de pénétration 0 C'est bon.！！Mettez - les dans queue,Continuer jusqu'à queue Vide.

Complexité temporelle

Complexité spatiale