Algoritmo eficiente para recuperar o fechamento transitivo de um gráfico acíclico direcionado

Estou tentando resolver um problema gráfico (não é para trabalhos de casa, apenas para praticar minhas habilidades). Um DAG é dado, onde é o conjunto de vértices e as arestas. O gráfico é representado como uma lista de adjacência, portanto é um conjunto que contém todas as conexões de . A minha tarefa é encontrar quais vértices são acessíveis a partir de cada vértice . A solução que eu uso tem uma complexidade de , com fechamento transitivo, mas li que em um blog pode ser mais rápido, embora não tenha revelado como. Alguém poderia me dizer outra maneira (com melhor complexidade) de resolver o problema do fechamento transitivo em um DAG? $G(V,E)$ $V$ $E$ $A_v$ $v$ $v\in V$ $O(V^3)$

algorithms graph-theory graphs Rontogiannis Aristofanis
fonte

Dê uma olhada em: stackoverflow.com/questions/3517524/…

AJed

e isso: cs.hut.fi/~enu/thesis.html

AJed 07/07/12

No entanto, minha sugestão é manter o

. mas tente diminuir o número de comparações em média. Ou seja, faça suposições e adicione regras simples ao seu algoritmo. Você pode usar a multiplicação de matrizes - mas se você estiver usando para pequenos gráficos - então é apenas uma bagunça e, na prática, seu método é melhor.

O (| V |^{3})

$O(|V|^3)$

precisa saber é

@AJed Neste problema em particular,

excederá o limite de tempo.

O (V^{3})

$O(V^3)$

Rontogiannis Aristofanis

@RondogiannisAristophanes Quando você diz limite de tempo, você quer dizer que este é um problema em alguns desafios de programação / algoritmo, como o topcoder etc.? Nesse caso, e se tiver certeza de que implementou corretamente uma solução

, convém examinar o problema novamente. Pode haver alguma outra propriedade oculta que possa simplificar as coisas, ou pode haver uma maneira melhor de expressar o problema para que um fechamento transitivo não seja necessário. Porque o fechamento transitivo é tão difícil quanto a multiplicação de matrizes. Leia student.cs.uwaterloo.ca/~cs466/Old_courses/F08/…

O (V^{3})

$O(V^3)$

Paresh

Respostas:

O fato de nosso gráfico ser acíclico torna esse problema muito mais simples.

A ordenação topológica pode nos dar uma ordenação dos vértices modo que, se , não há arestas de volta a . Listamos os vértices de forma que todas as arestas em "avançem" em nossa lista. $v_1,v_2,\dots,v_n$ $i < j$ $v_j$ $v_i$

(editado para corrigir a análise e fornecer um algoritmo um pouco mais rápido)

Agora apenas retrocedemos nesta lista, começando no último vértice . é fechamento transitivo é apenas em si. Adicione também ao fechamento transitivo de cada vértice com uma aresta para $v_n$ $v_n$ $v_n$ $v_n$ .

Para cada outro vértice , indo do final para trás, primeiro adicione ao seu próprio fechamento transitivo e, em seguida, adicione tudo no fechamento transitivo de ao fechamento transitivo de todos os vértices com uma aresta para $v_i$ $v_i$ $v_i$ $v_i$ .

O tempo de funcionamento é , no pior caso, com o número de vértices e o número de arestas. A ordenação topológica leva tempo . Em seguida, fazemos outro trabalho na passagem para trás: À medida que retrocedemos na lista, para cada borda, temos que somar $O(n+m+nm) = O(n^3)$ $n$ $m \in O(n^2)$ $O(n+m)$ $O(mn)$ $n$ vértices para o fechamento transitivo de alguém.

Observe que você pode obter uma boa aceleração de fator constante representando o fechamento transitivo de todos por matrizes de bits. Digamos que você tenha apenas ; então você deve usar um único int de 64 bits onde o bit é 1 se está no meu fechamento transitivo e 0 caso contrário. Em seguida, a parte em que adicionar tudo no 's fechamento transitivo para é é muito rápido: Nós apenas tomar | = . (Operação OR binária.) $n=64$ $i$ $i$ $i$ $j$ $c_j$ $c_i$

Para , você teria que mantê-los em matrizes e fazer alguma aritmética, mas seria muito mais rápido que um conjunto de objetos. $n > 64$

Além disso, eu sei que o grande no pior dos casos ainda é , mas para superar isso na prática você teria que ter algo muito mais complexo. Esse algoritmo também se sai muito bem em gráficos esparsos. $O$ $O(n^3)$

usul
fonte

Você provavelmente poderia usar uma representação de lista vinculada para os conjuntos e eles acabariam compartilhando caudas comuns.

Kyle Bundas