Heim  >  Artikel  >  Wie wird die topologische Sortierung sortiert?

Wie wird die topologische Sortierung sortiert?

醉折花枝作酒筹
醉折花枝作酒筹Original
2021-07-02 14:19:203204Durchsuche

Methode: 1. Suchen Sie im Diagramm einen Knoten mit einem In-Grad von 0, entfernen Sie diesen Knoten aus dem Diagramm und fügen Sie ihn zur Sequenz E hinzu. 2. Entfernen Sie alle zugehörigen Kanten des in 1 gefundenen Knotens aus dem Diagramm Entfernen; 3. Wiederholen Sie die Schritte 1 und 2, bis alle Knoten im Diagramm entfernt sind oder kein Knoten mit einem In-Grad von 0 gefunden werden kann.

Wie wird die topologische Sortierung sortiert?

Die Betriebsumgebung dieses Tutorials: Windows 7-System, Dell G3-Computer.

  1. Suchen Sie im Diagramm einen Knoten mit In-Grad 0, entfernen Sie diesen Knoten aus dem Diagramm und fügen Sie ihn der Sequenz E hinzu.

  2. Entfernen Sie alle zugehörigen Kanten des in 1 gefundenen Knotens aus dem Diagramm

  3. Wiederholen Sie 1 und 2, bis alle Knoten im Diagramm entfernt sind oder kein Knoten mit einem In-Grad von 0 gefunden werden kann.

Wenn die Anzahl der Knoten im Diagramm zu diesem Zeitpunkt 0 beträgt, wird die topologische Sequenz gefunden Wenn dies der Fall ist Wenn die Anzahl der Knoten im Diagramm nicht 0 ist, bedeutet dies, dass im Diagramm ein Zyklus vorhanden ist und keine topologische Sortierung durchgeführt werden kann.

Erweiterte Informationen:

Um eine topologische Sortierung für einen gerichteten azyklischen Graphen (kurz DAG) G durchzuführen, müssen alle Scheitelpunkte in G in einer linearen Reihenfolge angeordnet werden, sodass jedes Scheitelpunktpaar u und v im Graphen vorhanden ist, falls Kante ∈E(G), dann erscheint u vor v in der linearen Folge. Normalerweise wird eine solche lineare Folge als Folge bezeichnet, die die topologische Ordnung erfüllt, oder als topologische Folge bezeichnet. Vereinfacht ausgedrückt wird dieser Vorgang von einer Teilordnung einer Menge zu einer Gesamtordnung der Menge als topologische Sortierung bezeichnet.

Ausführungsschritte

Der topologische Sortieralgorithmus, der eine topologische Sequenz aus dem AOV-Netzwerk erstellt, führt hauptsächlich die folgenden zwei Schritte in einer Schleife aus, bis kein Scheitelpunkt mit einem In-Grad von 0 mehr vorhanden ist.

(1) Wählen Sie einen Scheitelpunkt mit In-Grad 0 aus und geben Sie ihn aus.

(2) Löschen Sie diesen Scheitelpunkt und alle ausgehenden Kanten aus dem Netzwerk.

Wenn nach dem Ende der Schleife die Anzahl der Ausgabescheitelpunkte geringer ist als die Anzahl der Scheitelpunkte im Netzwerk, werden die „Schleifen“-Informationen ausgegeben, andernfalls handelt es sich bei der Ausgabescheitelpunktsequenz um eine topologische Sequenz.

Wie wird die topologische Sortierung sortiert?

Weitere Computerkenntnisse finden Sie in der Rubrik FAQ!

Das obige ist der detaillierte Inhalt vonWie wird die topologische Sortierung sortiert?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn