Estoy tratando de resolver un problema gráfico (no es para la tarea, solo para practicar mis habilidades). Se da un DAG , donde es el conjunto de vértices y los bordes. El gráfico se representa como una lista de adyacencia, por lo que A v es un conjunto que contiene todas las conexiones de . Mi tarea es encontrar el que los vértices son accesibles desde cada vértice . La solución que uso tiene una complejidad de , con cierre transitivo, pero leí que en un blog puede ser más rápido, aunque no reveló cómo. ¿Alguien podría decirme otra forma (con mayor complejidad) para resolver el problema de cierre transitivo en un DAG?V Ev ∈ V O ( V 3 )
algorithms
graph-theory
graphs
Rontogiannis Aristofanis
fuente
fuente
Respuestas:
El hecho de que nuestro gráfico sea acíclico hace que este problema sea mucho más simple.
La ordenación topológica puede darnos una ordenación de los vértices manera que, si i < j , entonces no hay un borde de v j a v i . Hemos enumerado los vértices de modo que todos los bordes en "avance" en nuestra lista.v1, v2, ... , vnorte i < j vj vyo
(editado para corregir el análisis y dar un algoritmo ligeramente más rápido)
Ahora solo retrocedemos por esta lista, comenzando en el último vértice . El cierre transitivo de v n es solo en sí mismo. Agregue también v n al cierre transitivo de cada vértice con un borde para v n .vnorte vnorte vnorte vn
Para cada vértice , yendo desde el extremo hacia atrás, primero agregue v i a su propio cierre transitivo, luego agregue todo en el cierre transitivo de v i al cierre transitivo de todos los vértices con un borde a v i .vi vi vi vi
El tiempo de ejecución es en el peor de los casos, con n el número de vértices y m ∈ O ( n 2 ) el número de aristas. La ordenación topológica lleva tiempo O ( n + m ) . Luego hacemos otro trabajo O ( m n ) en el paso hacia atrás: a medida que avanzamos hacia atrás en la lista, para cada borde, tenemos que sumar nO(n+m+nm)=O(n3) n m∈O(n2) O(n+m) O(mn) n vértices al cierre transitivo de alguien.
fuente