Cuando el gráfico dirigido es lineal, devuelve los nodos en orden.De lo contrario falla

Question

El problema

tengo un conjunto de edges (a, b), dónde a y b son nodos en un gráfico acíclico dirigido (DAG).

Se garantiza que el número de aristas será el número de nodos: 1.

Estoy buscando un algoritmo que encuentre una secuencia de nodos. [n_1, ... n_n] para que la secuencia contenga todo nodos en el gráfico, y que todos los bordes (n_i, n_i+1) para 0 < i < n existe en edges.Si esa secuencia no es posible porque el conjunto dado de edges no es igual al conjunto de aristas requerido, entonces necesito que se genere un error.

Editar:el gráfico puede tener un número arbitrario de componentes desconectados.Obviamente, no considero lineal un gráfico con múltiples componentes desconectados.

Ideas hasta ahora

Tenga en cuenta que estoy comprobando que el número de edges es exactamente el número de aristas necesarias para que exista tal secuencia.Como resultado, el algoritmo puede fallar cuando hay dos aristas que comparten un origen o un destino.Sin embargo, todavía necesito obtener esa secuencia.

Me doy cuenta de que la clasificación topológica devuelve un orden lineal de un gráfico dirigido, que satisface mis requisitos.Sin embargo, todavía quiero fallar cuando el gráfico no es exactamente lineal, en lugar de obtener un orden lineal de todos modos.

Tal vez pueda validar y luego hacer una clasificación topológica.Pero eso suena ineficiente.Tampoco estoy seguro de los nombres formales de las cosas en este problema, por lo que es difícil simplemente buscar un algoritmo.Siento que me falta alguna conexión o truco simple aquí.

¿Podría proporcionarme un algoritmo que logre esto?Tomaré pseudocódigo o cualquier idioma de su elección.

Answer 1

Descubrí un algoritmo que al menos pasa mis casos de prueba:

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)$ Me parece bastante razonable.¿Hay alguna manera de mejorar?

Editar: Agradecería cualquier sugerencia sobre los términos técnicos correctos para los conceptos que estoy usando.

Answer 2

Aquí hay un algoritmo que no es óptimo para comenzar.

Recorrer todos los bordes $(a,b)$.Para cada borde, repase nuevamente todos los bordes y verifique cuántas veces $a$ aparece.Detente una vez que descubras $a$ que aparece sólo una vez (si esto nunca sucede, rechazar).Nosotros lo tomaremos $n_1 = un$.

Repasa todos los bordes nuevamente, buscando el borde único. $(n_1,b)$ en el cual $n_1$ aparece.Llevar $n_2 = b$.

Repasa todos los bordes nuevamente, buscando un borde. $(n_2,c)$ en el cual $n_2$ aparece a la izquierda (si no existe tal borde, rechazar).Llevar $n_3 = c$.

Continúe de esta manera, encontrando $n_4,\lpuntos,n_n$.

Este algoritmo se ejecuta en $O(n^2)$.Usando hash, deberías poder mejorarlo para $O(n)$.