Wie wird die topologische Sortierung sortiert?

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.

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.

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!