Encontrar una fuente de un gráfico acíclico dirigido en tiempo lineal

Dado un gráfico acíclico dirigido , un vértice es una fuente si su grado es cero, lo que significa que solo tiene arcos salientes. $D = (V,A)$ $v \in V$

¿Existe un algoritmo de tiempo lineal para encontrar una fuente en un gráfico acíclico dirigido dado?

Pregunta de seguimiento: ¿Puede uno en tiempo lineal encontrar todas las fuentes?

algorithms graph-theory breezeintopl
fuente

Por raíz, ¿te refieres a un nodo que tiene todos los bordes salientes y no tiene bordes entrantes? Si es así, puede haber más de una raíz.

Paresh

Sí, tiene usted razón. Por eso digo "una raíz" pero no "la raíz".

breezeintopl

En ese caso, ¿no es la definición suficiente para un algoritmo de tiempo lineal?

Paresh

¿Cuál es la estructura de datos? ¿Le dan una matriz de adyacencia, listas de vecindario, lista de adyacencia o qué? ¿Puedes verificar la vecindad (entrante) de un vértice en tiempo proporcional a su tamaño?

Pål GD

Si quiere decir lineal en el número de vértices, debe indicar eso. Además, las listas de adyacencia son ambiguas para los gráficos dirigidos: ¿enumera los bordes entrantes, los bordes salientes, ambos en listas separadas o ambos juntos?

Yuval Filmus el

Respuestas:

Como menciona Yuval, la estructura de datos es importante aquí. Trataré de dar una solución para algunos de los tipos de listas de adyacencia:

Lista de bordes entrantes : para cada nodo, hay una lista de vértices desde los cuales hay un borde entrante a este nodo. Simplemente puede escanear todos los vértices y verificar si el tamaño de su lista de adyacencia es $0$ o no. Un tamaño $0$ lista significa que no hay bordes entrantes, por lo que el nodo es una fuente o está desconectado. Suponiendo un gráfico conectado, este escaneo de cada vértice le dará una lista de todas las fuentes (o puede detenerse después de encontrar una) en $O(|V|)$ tiempo - lineal en el número de vértices .
Lista de bordes salientes : para cada nodo, hay una lista de vértices a los que hay un borde dirigido desde este nodo. Mantenga una cadena de bits con cada bit que represente un vértice, inicializado a 0. Comenzando desde el primer nodo, comience a escanear su lista en busca de vértices a los que hay un borde saliente de este. Cada uno de estos nodos (vecinos) no puede ser una fuente, por lo tanto, siga configurando su bit correspondiente en la cadena de bits. Al final, todos los vértices cuyos bits correspondientes aún están sin definir son los vértices de origen. Puede hacer esto en un tiempo lineal en el tamaño del gráfico : $O(|V| + |E|)$ .
Ambas listas juntas : para cada vértice, hay una lista mixta de vértices que tienen un borde hacia o desde este vértice, con algún otro atributo que indica cuál de los dos es realmente el caso. El enfoque es similar al 2 anterior, con la adición de que cualquier borde entrante descarta inmediatamente el vértice actual (y puede marcar su conjunto de bits). A diferencia del punto 2, donde debe atravesar todos los vértices, aquí puede encontrar alguna fuente antes. Si no te detienes, tendrás todas las fuentes. Para ambos casos, el tiempo es nuevamente lineal en el tamaño del gráfico : $O(|V| + |E|)$ .
Ambas listas por separado : simplemente elija la lista de borde entrante y siga 1.

Como nota al margen, si elegir la estructura de datos está en sus manos, es posible que desee analizar qué operaciones pretende realizar y con qué frecuencia, y elegir una estructura de datos adecuada.

Editar: para el caso 1, si tiene un dag donde el número de fuentes es muy pequeño en comparación con $|V|$ (por ejemplo, en un árbol con una fuente), y donde la distancia promedio desde cualquier vértice a una fuente es pequeña en comparación con $|V|$ y solo desea una fuente única, puede usar un algoritmo más rápido en promedio (aunque la peor complejidad asintótica será la misma). Seleccione cualquier vértice al azar, y vaya a cualquiera de sus padres (de la lista de borde entrante), y luego a su padre y así sucesivamente, hasta llegar a un nodo que no tiene padre - una fuente. Esta pequeña ganancia de eficiencia es para tipos muy limitados de gráficos con un algoritmo un poco más complejo.

Paresh
fuente

Para las listas de borde entrantes, en caso de que solo necesite encontrar una sola fuente, ¿no sería más rápido seguir un borde arbitrario para obtener el predecesor, hasta llegar a una fuente? Especialmente si el gráfico es plano, es decir, la distancia promedio a cada fuente de cada vértice es mucho menor que

| V |

$|V|$ .

Simon S

@SimonS Aunque la peor complejidad del caso es la misma (por ejemplo, una cadena lineal), puede hacerlo más rápido si el gráfico tiene muy pocas fuentes (en comparación con

| V |

$|V|$ ) y la distancia promedio desde cualquier vértice a una fuente es muy pequeña, por ejemplo. un gráfico de estrellas con el centro como fuente. Solo tener la condición que usted menciona no es suficiente, por ejemplo, 1-> 2, 1-> 3, 4-> 2, 4-> 3 - (puede tener un gráfico con una distancia promedio de 0.5 y | V | / 2 fuentes) la distancia promedio es pequeña, pero ambos algoritmos darán el mismo tiempo esperado / similar. Aunque lo agregaré a mi respuesta.

Paresh

¡Gracias por su respuesta! Creo que lo que quiero decir es el segundo caso, la lista saliente. Por cierto, ¿por qué es O (| V | + | E |)? Sé | E |, porque tienes que escanear todos los bordes, pero donde el | V | ¿desde? ¡Gracias!

breezeintopl

@breezeintopl Es una forma de representación. Verifica cada borde una vez y cada vértice también un número constante de veces. Por lo menos, al final tienes que escanear todos los vértices una vez para ver qué bits no están configurados. Otra forma de verlo es que una lista de adyacencia utiliza

Θ (| V | + | E |)

$\Theta(|V| + |E|)$ espacio: almacena un vértice y su lista de aristas. Y estás recorriendo toda la lista. Por supuesto, desde

| E |

$|E|$ puede variar desde

O (| V |)

$O(|V|)$ a

O (| V |^{2})

$O(|V|^2)$ , podrías saltarte el

| V |

$|V|$ parte. Vea un ejemplo para BFS .

Paresh

Consideremos una pregunta más simple. Suponga que sabe que su gráfica es un árbol. Luego puede encontrar el nodo fuente en tiempo lineal. Simplemente seleccione un nodo aleatorio, si es la raíz, entonces tiene su respuesta, si no debe ser un niño o un padre, retroceda hasta llegar a la raíz. Esto se puede hacer en $O(|V|-1)$ .

Reza
fuente

Si su estructura de datos no incluye una lista de bordes internos para un nodo, encontrar el padre ya toma O (m) (en árboles, por lo tanto, O (n). Ya que la ruta a la raíz del árbol puede ser linealmente largo, esto es solo una solución cuadrática. Pero si tiene bordes, entonces encontrar algún nodo con 0 en los bordes es trivial.

adrianN

-1

Suponiendo que tiene un gráfico G = (V, E) en formato de lista de adyacencia. (para que quede claro aquí, la lista contiene todos los bordes salientes de la fuente). Puedes construir el inverso del gráfico G en tiempo lineal. Luego puede iterar sobre el gráfico inverso y recopilar todos los vértices que tienen una lista de adyacencia vacía. Estos vértices no tienen borde saliente en el gráfico inverso, lo que significa que no tienen bordes entrantes en el gráfico original, por lo tanto, estos son sus vértices de origen.

El tiempo de ejecución es lineal. La construcción de la inversa del gráfico requiere un tiempo máximo de O (| V | + | E |). Iterar sobre el inverso del gráfico toma tiempo O (| V |).

MGB
fuente

Honestamente, calcular el inverso del gráfico suena como un problema más difícil que encontrar las fuentes. Dudo que alguien que no pueda descubrir cómo obtener las fuentes pueda descubrir cómo invertir todos los bordes.

David Richerby

@DavidRicherby dijo que calcular el inverso del gráfico es más difícil. ¿Cómo se define más duro? Si es la complejidad del tiempo, se puede hacer en tiempo lineal. Puede buscar la solución aquí [enlace] ( stackoverflow.com/questions/40378152/… ). La pregunta es sobre una solución de tiempo lineal que encuentra la fuente de un gráfico y mi solución propuesta lo hace. Si cree que no, ¿puede ser específico y decirme cómo mi algoritmo no satisface el requisito de tiempo lineal?

MGB

Me refiero conceptualmente más difícil. Estás diciendo que, para resolver este ejercicio, el autor de la pregunta solo necesita resolver otro ejercicio, pero ese otro ejercicio parece más difícil que el primero.

David Richerby