Testen / Identifizieren einer topologischen Sortierung

8

Sie sind eine Reihe von bestimmten gerichteten azyklischen Graphs über den gleichen Satz von m Ecken V . Sie erhalten auch eine Permutation der Menge der Eckpunkte (v_1, v_2, ..., v_m) . Was ist der beste Algorithmus, um die Graphen unter G_1, G_2, ..., G_n zu identifizieren , die (v_1, v_2, ..., v_m) als topologische Sortierung haben? Könnte jemand testen, ob (v_1, v_2, ..., v_m) eine topologische Art einer DAG G über V in sublinearer Zeit ist? nG1,G2,...,GnmV(v1,v2,...,vm)G1,G2,...,Gn(v1,v2,...,vm)(v1,v2,...,vm)GV

Hsien-Chih Chang 張顯 之
quelle
6
Können Sie eine Datenstruktur basierend auf dem Diagrammsatz erstellen, bevor die Reihenfolge der Scheitelpunkte angezeigt wird? Sie müssen alle n Diagramme und alle m1 Kanten in der Reihenfolge betrachten. Wenn Sie die Diagramme also nicht irgendwie vorverarbeiten dürfen, scheint es nicht so, als könnten Sie die lineare Zeit übertreffen.
mjqxxxx
Hsien-Chih Chang, was wäre eine gute Vorverarbeitungstechnik, die eine bessere Lösung ermöglichen kann? Irgendeine Art von Hashing? Ich denke, Sie können die lineare Zeit schlagen, wenn Sie sich der Lösung annähern können (probabilistischer Algorithmus).
user2471
@ user2471: Wie ich in Ihrer vorherigen Antwort sagte, ist dieser Beitrag von @Steve geschrieben, nicht von mir;)
Hsien-Chih Chang 張顯 之
Sorry Hsien-Chih Chang, meine Frage war für alle gedacht :)
user2471
@ user2471, keine Notwendigkeit, sich zu entschuldigen! Hoffe, jemand, der mit dieser Frage vertraut ist, wird eine nette Antwort posten: D
Hsien-Chih Chang 21 之

Antworten:

3

Dies kann in nahezu linearer Zeit erfolgen.

Sei die Permutation und sei die Anzahl der Schritte, die erforderlich sind, um eine einzelne Kante gegen zu prüfen . Es reicht dann aus, zu überprüfen, ob jede der Kanten von mit kompatibel ist, was in oder insgesamt erfolgen kann.π=(v1,,vm)k=k(π)(u,v)πMiGiπO(kMi)O(kMi)

Durch Vorverarbeitung von kann man auf zwei Suchvorgänge in einem Array reduzieren , das Einträge mit jeweils Größe und einen Vergleich zwischen zwei -Bit-Einträgen im Array enthält. Das Array-Element enthält den Index von in , der als geordnete Liste betrachtet wird. Dies bedeutet, dass was insgesamt Zeit für die Obergrenze ergibt .πkmlogm(log m)a[w]wπk=O(logm)O((logm)Mi)

Wie @mjqxxxx hervorhebt, kann jede Kante jedes Diagramms relevant sein. Dies erzeugt eine Untergrenze von -Schritten, wobei der geringste Arbeitsaufwand ist, der für jede Diagrammkante ausgeführt werden muss. Es ist möglich, dass einige Ansätze die Kosten amortisieren können, so dass . Dies wird bestenfalls immer noch , so dass keine große Lücke mehr besteht.Ω(KMi)KK=o(logm)Ω(Mi)

András Salamon
quelle
Welcher Algorithmus kann verwendet werden, um k = log m zu machen. Ist es Suffix Bäume?
Vincent Mathew
0

Triviale Methode:

GS = {G1,G2...G3}
for v in (v1,v2,...vm)
      remove all graphs from GS where indegree(v) != 0
      remove v and attached edges from remaining GS

Es ist nicht so schnell wie du willst. Es löst jedoch ein Problem, dass "es mehrere gültige topologische Ordnungen der DAG geben kann". Und sie alle zu finden, ist keine gute Idee.

Pratik Deoghare
quelle