Quando il grafico diretto è lineare, restituire i nodi in ordine.Altrimenti fallire

Question

il problema

Ho un set di edges (a, b), dove a e b sono nodi in un grafico aciclico diretto (DAG).

Il numero di bordi è garantito per essere il numero di nodi - 1.

Sto cercando un algoritmo che trova una sequenza di nodi [n_1, ... n_n] in modo che la sequenza contiene tutti i nodi nel grafico e che tutti i bordi (n_i, n_i+1) per 0 < i < n esistono in edges. Se quella sequenza non è possibile perché il set datato di edges non è uguale al set di bordi richiesti, allora ho bisogno di un errore da lanciare.

Modifica: il grafico potrebbe avere un numero arbitrario di componenti disconnessi. Ovviamente non considero un grafico con più componenti disconnessi come lineari.

Idee finora

Nota che sto controllando che il numero di generatoriTagCode sia esattamente il numero di bordi richiesti per tale sequenza di esistere. Di conseguenza, l'algoritmo può fallire quando ci sono due bordi che condividono una fonte o una destinazione. Tuttavia, ho ancora bisogno di ottenere quella sequenza.

Mi rendo conto che il tipo topologico restituisce un ordine lineare di un grafico diretto, che soddisfi le mie esigenze. Tuttavia, voglio ancora fallire quando il grafico non è esattamente lineare in quel modo, invece di ottenere comunque un ordine lineare.

Forse posso convalidare, quindi fai un tipo topologico. Ma questo sembra inefficiente. Inoltre non sono sicuro dei nomi formali delle cose in questo problema, quindi è difficile cercare semplicemente un algoritmo. Mi sento come se mi manca una semplice connessione o un trucco qui.

Potresti fornirmi un algoritmo che lo realizza? Prenderò pseudocode o qualsiasi lingua di tua scelta.

Answer 1

Ho capito un algoritmo che passa almeno i miei casi di test:

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

.

$ o (n) $ sembra abbastanza ragionevole per me.Ci sono modi per migliorare?

Modifica: Apprezzerei tutti i suggerimenti sui termini tecnici corretti per i concetti che sto usando

Answer 2

Ecco un algoritmo abbastanza non ottimale, per iniziare.

Vai su tutti i bordi $ (a, b) $ . Per ogni bordo, vai di nuovo su tutti i bordi e controlla quante volte Viene visualizzato $ A $ . STOP Una volta scoperta $ A $ appare solo una volta (se questo non succede mai, rifiutare). Prenderemo $ n_1= a $ .

Vai di nuovo tutti i bordi, cercando il bordo unico $ (n_1, b) $ in cui $ n_1 $ appare. Take $ n_2= B $ .

Vai di nuovo tutti i bordi, cercando un bordo $ (n_2, c) $ in cui $ n_2 $ < / span> appare a sinistra (se non c'è tale bordo, rifiutare). Prendere $ n_3= c $ .

Continua in questo modo, trovare $ n_4, \ ldots, n_n $ .

Questo algoritmo funziona in $ o (n ^ 2) $ . Utilizzando l'hashing, dovresti essere in grado di migliorarlo a $ o (n) $ .