algorithm - profundidad - Uso del componente Algo fuertemente conectado para verificar si un vértice es alcanzable
grafo conexo (2)
Me gustaría ver si un vértice dado, digamos V0, puede ser alcanzado por todos los demás vértices en un grafo G.
Sé que puedo atravesar cada vértice en el gráfico y hacer BFS / DFS para ver si V0 es alcanzable.
Sin embargo, esto parece ser muy ineficiente.
Me preguntaba si hago algo de SCC en el gráfico y si v0 es parte de toda la scc, entonces puedo concluir con seguridad que v0 es alcanzable por todos los vértices. Esto sería genial porque el costo de SCC es solo O (V + E) con Tarjan y comprobar si v0 es parte de scc también costaría tiempo lineal.
Pensaría que esto tiene sentido porque SCC significa que los vértices son alcanzables. Cualquier confirmación a esta lógica?
o cualquier enfoque eficiente para esto?
Llamemos a un vértice desde el cual todos los demás vértices son alcanzables, un vértice de vista. Si el gráfico tiene un vértice de vista, entonces debe tener un solo origen SCC (ya que dos SCC de origen no son accesibles entre sí), que debe contener el vértice de vista (si está en cualquier otro SCC, no hay un camino de la vista vértice a la fuente SCC). Además, en este caso, cada vértice en el SCC de origen será un vértice de vista. El algoritmo es simplemente un DFS que comienza desde cualquier nodo y marca el vértice con el tiempo de finalización más alto. Esto debe estar en una fuente SCC. Ahora nuevamente ejecutamos un DFS desde este vértice para verificar si podemos alcanzar todos los nodos. Dado que el algoritmo simplemente utiliza la descomposición en SCC y DFS, el tiempo de ejecución es lineal. Este algoritmo es correcto. Tenga en cuenta que existirá un vértice de vista si y solo si hay un solo origen SCC. Cualquier vértice en un SCC de origen solo es alcanzable por otros vértices en el mismo SCC, por lo que ningún vértice puede alcanzar vértices en dos SCC de origen distintos. Además, si solo hay un SCC de origen, cualquier vértice en ese SCC es un vértice de vista ya que todos son accesibles el uno del otro. Tenga en cuenta que un DFS que se inicia en cualquier SCC particular no terminará hasta que se hayan explorado todos los SCC accesibles. Esto implica que el último nodo para terminar está en un SCC que no es accesible desde cualquier otro SCC, es decir, un SCC de origen. Por lo tanto, en la primera parte de nuestro algoritmo, encontramos un nodo en una fuente SCC. Al realizar DFS, determinaremos correctamente si es o no un vértice de vista, y si no es un vértice de vista, sabemos que no existe ninguno en nuestro gráfico.
V0 puede no pertenecer a SCC, pero aún así ser alcanzable por todos los demás vértices. Por ejemplo, el vértice d en el diagrama es alcanzable por todos los demás vértices, pero el único SCC no trivial contiene los vértices a , b , c y no contiene el vértice d .
Para verificar si V0 es alcanzable por todos los otros vértices, puede invertir la dirección de cada borde (en tiempo lineal), luego use BFS / DFS, comenzando desde V0, para verificar si cada otro vértice es alcanzable desde V0 (también en tiempo lineal) .