algorithm - representacion - representar raices en la recta real ejercicios resueltos

Encontrar todas las raíces en un gráfico dirigido

Question

Necesito encontrar un algoritmo para encontrar todas las raíces en un gráfico dirigido, en O (n + m).

Tengo un algoritmo para encontrar una sola raíz:

1. Ejecute DFS (v) en alguna v en V. Si el resultado es un único árbol de expansión, entonces v es una raíz. De lo contrario, el resultado es un bosque de árboles. Entonces:
2. Ejecute DFS (u) en la raíz del último árbol. Si el resultado es un único árbol de expansión, entonces u es una raíz. De lo contrario, no hay raíces en el gráfico.

Ahora, si quiero encontrar todas las raíces, ¿es la mejor manera de ejecutar el algoritmo anterior O (n) veces, en un vértice diferente en el último árbol cada vez? Suponiendo que encontré una raíz, si existe otra raíz, entonces debe estar en el último árbol, entonces ¿es O (n + m) si continúo ejecutando el algoritmo anterior hasta recibir "no existe raíz" o hasta pasar por todos los vértices?

Gracias por adelantado !

Answer 1

Dos enfoques:

1. Invierta el gráfico y calcule DFS-loop () y observe los vértices que no tienen bordes salientes (como dijo Abhishek).

2. Más eficiente: ejecute DFS-loop () en el gráfico y realice un seguimiento de los vértices sin bordes entrantes utilizando una tabla verdadera, falsa.

El método 1 toma el doble de tiempo en el peor de los casos.

Answer 2

Primero debes encontrar todos los componentes fuertemente conectados en el gráfico. Para construirlo en un tiempo menor, puedes usar el algoritmo de Kosaraju o el algoritmo de Tarjan . Todas las raíces deberían estar ubicadas en uno de esos componentes. A continuación, encontrará componentes fuertemente conectados sin bordes entrantes. Si tiene más de un componente, el gráfico no tiene vértices raíz. Como tiene un solo componente, debe verificar que puede llegar a otros componentes, en este caso, este componente contiene todas las raíces en el gráfico.

Antigua variante.

Debe calcular el número de bordes entrantes en el vértice, esto se puede hacer en O (m). Todos los vértices con un número cero de bordes entrantes serán una raíz del gráfico, para esto necesitarás O (n) tiempo.