Algorithme efficace pour récupérer la fermeture transitive d'un graphe acyclique dirigé

J'essaie de résoudre un problème de graphique (ce n'est pas pour les devoirs, juste pour pratiquer mes compétences). Un DAG est donné, où est l'ensemble des sommets et les arêtes. Le graphe est représenté comme une liste d'adjacence, donc est un ensemble contenant toutes les connexions de . Ma tâche est de trouver quels sommets sont accessibles à partir de chaque sommet . L'utilisation de la solution I a une complexité de , avec fermeture transitive, mais je lis que dans un blog , il peut être plus rapide, mais il n'a pas révélé comment. Quelqu'un pourrait-il me dire une autre façon (avec une meilleure complexité) pour résoudre le problème de fermeture transitive dans un DAG?$G(V,E)$E A v v v ∈ V O ( V 3$V$$E$$A_v$$v$$v\in V$$O(V^3)$

Le fait que notre graphique soit acyclique rend ce problème beaucoup plus simple.

Le tri topologique peut nous donner un ordre des sommets tels que, si i < j , alors il n'y a pas d'arête de v j vers v i . Nous avons répertorié les sommets de manière à ce que toutes les arêtes soient "avancées" dans notre liste.$v_1,v_2,\dots,v_n$$i < j$$v_j$$v_i$

(édité pour corriger l'analyse et donner un algorithme légèrement plus rapide)

Nous allons maintenant revenir en arrière dans cette liste, en commençant par le dernier sommet . La fermeture transitive de v n est juste elle-même. Ajoutez également v n à la fermeture transitive de chaque sommet avec une arête à v n .$v_n$$v_n$$v_n$$v_n$

Pour chaque autre sommet , en allant de la fin vers l'arrière, ajoutez d'abord v i à sa propre fermeture transitive, puis ajoutez tout dans la fermeture transitive de v i à la fermeture transitive de tous les sommets avec une arête à v i .$v_i$$v_i$$v_i$$v_i$

Le temps d'exécution est dans le pire des cas, avec n le nombre de sommets et m ∈ O ( n 2 ) le nombre d'arêtes. Le tri topologique prend le temps O ( n + m ) . Ensuite, nous effectuons un autre travail O ( m n ) dans la passe arrière: Lorsque nous revenons en arrière dans la liste, pour chaque bord, nous devons additionner à $O(n+m+nm) = O(n^3)$$n$$m \in O(n^2)$$O(n+m)$$O(mn)$$n$ sommets à la fermeture transitive de quelqu'un.

Notez que vous pouvez obtenir une belle accélération à facteur constant en représentant la fermeture transitive de tout le monde par des tableaux de bits. Disons que vous n'aviez que ; alors vous utiliseriez un seul entier 64 bits où le bit i est 1 si i est dans ma fermeture transitive et 0 sinon. Ensuite , la partie où l' on ajoute tout i « s fermeture transitive j » s est vraiment rapide: Nous prenons juste c j | = c i . (Opération binaire OU.)$n=64$$i$$i$$i$$j$$c_j$$c_i$

Pour , vous devez les conserver dans des tableaux et faire de l'arithmétique, mais ce serait beaucoup plus rapide qu'un ensemble d'objets.$n > 64$

$O$$O(n^3)$