Quando direcionado gráfico é linear, retornar os nós em ordem.Caso contrário falhar

Question

O Problema

Eu tenho um conjunto de edges (a, b), onde a e b são nós em um dirigido, gráfico acíclico (DAG).

O número de arestas é garantido para ser o número de nós - 1.

Eu estou procurando um algoritmo que encontra uma seqüência de nós [n_1, ... n_n] de modo que a seqüência contém todos nós do grafo, e que todas as arestas (n_i, n_i+1) para 0 < i < n existem no edges.Se essa sequência não é possível porque o conjunto de edges não é igual ao conjunto de arestas necessárias, então eu preciso de um erro a ser lançada.

Editar:o gráfico pode ter um número arbitrário de desligado componentes.Eu, obviamente, não considerar você pode encontrar um gráfico com vários desconectado componentes como linear.

As ideias até agora

Note que eu estou a verificação de que o número de edges é exatamente o número de arestas necessárias para tal uma sequência de existir.Como resultado, o algoritmo pode falhar quando há duas arestas que compartilham uma origem ou um destino.No entanto, eu ainda preciso para obter essa sequência.

Eu percebo que a classificação topológico retorna uma ordem linear de um gráfico direcionado, que satisfaz todas as minhas necessidades.No entanto, eu ainda quero falhar quando o gráfico não é exatamente linear, como a que, em vez de obter uma ordem linear de qualquer maneira.

Talvez eu possa validar, em seguida, fazer uma ordenação topológica.Mas que soa ineficiente.Também estou em dúvida sobre a formal nomes das coisas deste problema, por isso é difícil basta olhar um algoritmo.Eu sinto que eu estou faltando alguma ligação simples ou truque aqui.

Você poderia me fornecer um algoritmo que faz isso?Eu vou tomar pseudocódigo ou qualquer outro idioma de sua escolha.

Answer 1

Eu descobri um algoritmo que pelo menos passa a minha casos de teste:

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

$S(n)$ parece bastante razoável para mim.Há formas de melhorar?

Editar: Gostaria muito de receber alguma dicas sobre a correta termos técnicos para os conceitos que eu estou usando

Answer 2

Aqui é um bem não-algoritmo ótimo, para você começar.

Vá ao longo de todas as extremidades $(a,b)$.Para cada borda, vá novamente sobre todas as arestas, e verifique quantas vezes $a$ aparece.Parar uma vez que você descubra $a$ que aparece apenas uma vez (se é que isso nunca acontece, rejeitar).Vamos tomar $n_1 = us$.

Vá ao longo de todas as arestas de novo, olhando para a única borda $(n_1,b)$ em que $n_1$ aparece.Tomar $n_2 = b$.

Vá ao longo de todas as arestas de novo, procurando uma borda $(n_2,c)$ em que $n_2$ aparece na esquerda (se é que não existe tal aresta, rejeitar).Tomar $n_3 = c$.

Continue dessa forma, encontrar $n_4,\ldots,n_n$.

Este algoritmo é executado em $O(n^2)$.Usando hash, você deve ser capaz de melhorá-lo para $S(n)$.