Você é dado um conjunto de Directed acíclico Gráficos G 1 , G 2 , . . . , L n sobre o mesmo conjunto de m vértices V . Você também está dado uma permutação do conjunto de vértices ( v 1 , v 2 , . . . , V m ) . Qual é o melhor algoritmo que poderia identificar os gráficos entre G 1 , G 2 , . . . , G nque tem como uma espécie topológica? Poderia alguém teste se ( v 1 , v 2 , . . . , V m ) é um tipo topológica de um DAG L sobre V em vez de sub-linear?
ds.algorithms
graph-algorithms
directed-acyclic-graph
Hsien-Chih Chang 張顯 之
fonte
fonte
Respostas:
Isso pode ser feito em tempo quase linear.
fonte
Método trivial:
Não é tão rápido quanto você deseja. Mas resolve um problema que "pode haver vários pedidos topológicos válidos do DAG". E encontrar todos eles não é uma boa ideia.
fonte