Testen / Identifizieren einer topologischen Sortierung

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

ds.algorithms graph-algorithms directed-acyclic-graph Hsien-Chih Chang 張顯之
quelle

Können Sie eine Datenstruktur basierend auf dem Diagrammsatz erstellen, bevor die Reihenfolge der Scheitelpunkte angezeigt wird? Sie müssen alle

n

$n$ Diagramme und alle

m - 1

$m-1$ 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:

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. $\pi = (v_1,\dots,v_m)$ $k = k(\pi)$ $(u,v)$ $\pi$ $M_i$ $G_i$ $\pi$ $O(kM_i)$ $O(k\sum M_i)$

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 . $\pi$ $k$ $m$ $\log\, m$ $(\log\ m)$ $a[w]$ $w$ $\pi$ $k = O(\log\, m)$ $O((\log\, m)\sum M_i)$

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. $\Omega(K\sum M_i)$ $K$ $K = o(\log\, m)$ $\Omega(\sum M_i)$

András Salamon
quelle

Welcher Algorithmus kann verwendet werden, um k = log m zu machen. Ist es Suffix Bäume?

Vincent Mathew

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