"Die Anordnung der Scheitelpunkte einer DAG nach steigender Vornummer führt zu einer topologischen Sortierung." ist anscheinend keine wahre Aussage, aber ich sehe nicht, warum es nicht ist. Wenn der Graph gerichtet ist und keine Zyklen hat, sollte dann nicht die Reihenfolge, in der wir die Scheitelpunkte besuchen, die richtige Reihenfolge sein, in der wir sie topologisch sortieren?DAG und Top Sort
Die Anordnung durch Erhöhung der Vornummer garantiert keine gültige topologische Sortierung. Betrachten Sie diese Grafik:
A
↓
B → C → D
Die beiden gültigen topologischen Aufträge dieses Graphen sind:
A, B, C, D
B, A, C, D
Wenn Sie die Knoten beginnend mit C, eine mögliche vorgeNummer bestellen wäre zu besuchen waren:
C, D, A, B
Das ist keine gültige topologische Reihenfolge. Ein noch einfacheres Beispiel ist diese Graph:
B → A
Es gibt eindeutig eine gültige topologische Ordnung, aber wenn wir waren A erste und sortierte nach Pre-Nummer zu besuchen, würde die resultierende Ordnung rückwärts sein.