Nombre de sommets accessibles en DAG pour chaque sommet

Soit un graphe dirigé acyclique, tel que le degré extérieur de tout sommet soit . Pour chaque sommet de nous pouvons compter le nombre de sommets accessibles, simplement en exécutant dfs à partir de chaque sommet et cela prendra du temps . Existe-t-il une meilleure façon de résoudre ce problème?O ( log | V | ) $G(V,E)$$O(\log{|V|})$$G$$O(|V||E|)$

Le meilleur algorithme exact s'exécutera dans le temps O (min {mn, n ^ 2,38}) en utilisant une multiplication matricielle binaire rapide. Cependant, il existe un algorithme aléatoire, qui s'exécute dans le temps O (m + n) et estime le nombre de nœuds accessibles à partir de chaque nœud avec une petite erreur relative, veuillez vous reporter à l'article " Cadre d'estimation de la taille avec des applications à la fermeture et à l'accessibilité transitives" "par Edith Cohen.

Je ne suis pas un expert ici je vais essayer.

1) Puisqu'il s'agit de DAG, il devrait avoir un sommet de puits, c'est-à-dire un sommet avec un degré 0. Trouver un sommet de puits dire x et ajouter {x} comme sommet accessible au voisin (x). supprimer x et répéter le processus jusqu'à ce que le graphique devienne vide

(Similaire à la solution de Prabu ... mais plus détaillée)

Soit les voisins (sortants) de et dénote le nombre de sommets accessibles depuis v.$N(v)$$v$$reach(v)$

1. faire un tri topologique. (possible en )$O(|V|+|E|)$
2. à partir de la fin de la liste (à l'extrémité d'un puits): Pour chaque sommet (à partir de l'extrémité de la liste): .r e a c h ( v ) = ∑ n ∈ N ( v ) r e a c h ( n $v$$reach(v) = \sum_{n\in N(v)} reach(n)$

La deuxième partie traverse chaque arête une fois, en ajoutant une autre, donc au total je reçois .O ( | V | + $|E|$$O(|V|+|E|)$