Número de vértices alcançáveis ​​no DAG para cada vértice

Seja um gráfico direcionado acíclico, de modo que o grau externo de qualquer vértice seja O ( log | V | ) . Para cada vértice de G , podemos contar o número de vértices alcançáveis, apenas executando dfs de cada vértice e isso levará tempo O ( | V | | E | ) . Existe uma maneira melhor de resolver este problema?$G(V,E)$$O(\log{|V|})$$G$$O(|V||E|)$

O melhor algoritmo exato será executado no tempo O (min {mn, n ^ 2,38}) usando multiplicação rápida de matriz binária. No entanto, existe um algoritmo aleatório, que é executado no tempo O (m + n) e estima o número de nós alcançáveis ​​de cada nó com um pequeno erro relativo, consulte o artigo " Estrutura de estimativa de tamanho com aplicativos para fechamento e acessibilidade transitivos "de Edith Cohen.

Eu não sou um especialista aqui, vou tentar.

1) Como é DAG, ele deve ter um vértice coletor, isto é, vértice com grau 0. 0. Encontre um vértice coletor, diga x e adicione {x} como vértice acessível ao vizinho (x). remova x e repita o processo até o gráfico ficar vazio

(Semelhante à solução de Prabu ... mas mais detalhada)

$N(v)$$v$$reach(v)$

1. $O(|V|+|E|)$
2. $v$$reach(v) = \sum_{n\in N(v)} reach(n)$

$|E|$$O(|V|+|E|)$