Wenn der gerichtete Graph linear ist, geben Sie die Knoten der Reihe nach zurück.Andernfalls fehlschlagen

Question

Problem

Ich habe eine Reihe von edges (a, b), wo a und b sind Knoten in einem gerichteten, azyklischen Graphen (DAG).

Die Anzahl der Kanten ist garantiert die Anzahl der Knoten - 1.

Ich suche nach einem Algorithmus, der eine Folge von Knoten findet [n_1, ... n_n] damit die Sequenz enthält aller knoten im Graphen, und dass alle Kanten (n_i, n_i+1) für 0 < i < n existieren in edges.Wenn diese Reihenfolge nicht möglich ist, weil die angegebene Menge von edges entspricht nicht der Menge der erforderlichen Kanten, dann muss ein Fehler ausgegeben werden.

Bearbeiten:der Graph kann eine beliebige Anzahl von getrennten Komponenten aufweisen.Ich betrachte einen Graphen mit mehreren getrennten Komponenten offensichtlich nicht als linear.

Bisherige Ideen

Beachten Sie, dass ich überprüfe, ob die Anzahl der edges ist genau die Anzahl der Kanten, die erforderlich sind, damit eine solche Sequenz existiert.Infolgedessen kann der Algorithmus fehlschlagen, wenn zwei Kanten vorhanden sind, die sich eine Quelle oder ein Ziel teilen.Ich brauche diese Sequenz jedoch noch.

Mir ist klar, dass die topologische Sortierung eine lineare Ordnung eines gerichteten Graphen zurückgibt, die meinen Anforderungen entspricht.Ich möchte jedoch immer noch scheitern, wenn der Graph nicht genau so linear ist, anstatt sowieso eine lineare Ordnung zu erhalten.

Vielleicht kann ich validieren und dann eine topologische Sortierung durchführen.Aber das klingt ineffizient.Ich bin mir auch nicht sicher über die formalen Namen der Dinge in diesem Problem, daher ist es schwierig, einfach einen Algorithmus nachzuschlagen.Ich habe das Gefühl, dass mir hier eine einfache Verbindung oder ein Trick fehlt.

Könnten Sie mir einen Algorithmus zur Verfügung stellen, der dies erreicht?Ich nehme Pseudocode oder eine beliebige Sprache Ihrer Wahl.

Answer 1

Ich habe einen Algorithmus gefunden, der zumindest meine Testfälle besteht:

let N = set of all nodes
let E = set of all edges

if (|E| != |N|-1) fail

let possibleStartNodes = new set containing all of N
let nexts = new dictionary from node -> node

foreach (prev, next) in E:
  if (next not in possibleStartNodes) fail 
  remove next from possibleStartNodes
  nexts[prev] = next
end foreach

if (|possibleStartNodes| != 1) fail

let currentNode = the one node in possibleStartNodes
let ordering = new list
ordering.push(currentNode)

while (nexts contains value for currentNode) 
  ordering.push(next)
  currentNode = next
end while

return ordering

$A(n)$ sieht für mich ziemlich vernünftig aus.Gibt es Möglichkeiten zur Verbesserung?

Bearbeiten: Ich würde mich über Hinweise zu den richtigen Fachbegriffen für die von mir verwendeten Konzepte freuen

Answer 2

Hier ist ein ziemlich nicht optimaler Algorithmus, um Ihnen den Einstieg zu erleichtern.

Über alle Kanten gehen $(ein, b)$.Gehen Sie für jede Kante erneut über alle Kanten und überprüfen Sie, wie oft $ein$ erscheint.Stoppen Sie, sobald Sie entdecken $ein$ das erscheint nur einmal (wenn das nie passiert, ablehnen).Wir werden nehmen $ n_1 = ein $.

Gehen Sie noch einmal über alle Kanten und suchen Sie nach der einzigartigen Kante $(n_1,b)$ in welchem $n_1$ erscheint.Nehmen $n_2 = b$.

Gehen Sie noch einmal über alle Kanten und suchen Sie nach einer Kante $(n_2,b)$ in welchem $n_2$ erscheint links (wenn es keine solche Kante gibt, ablehnen).Nehmen $n_3 = c$.

Fahren Sie auf diese Weise fort und finden Sie $n_4,\punkte,n_n$.

Dieser Algorithmus läuft in $O(n^2)$.Mit Hashing sollten Sie in der Lage sein, es zu verbessern $A(n)$.