Un vértice madre en un gráfico dirigido G = (V, E) es un vértice v tal que todos los demás vértices G se pueden alcanzar mediante una ruta dirigida desde v Proporcione un algoritmo O (n + m) para probar si el gráfico G contiene un vértice madre.¿Cómo encontrar el vértice madre en un gráfico dirigido en O (n + m)?
(c) a partir de manual de Skiena
encuentra sólo O (n (n + m)) forma
Cuando googling hecho, encontré la respuesta here. Si esto es tarea, debe pensarlo dos veces antes de mirar a escondidas :)
Vi la solución. No creo que necesitemos encontrar SCC. Simplemente haga un DFS desde un vértice aleatorio y luego haga el DFS desde el vértice con el último tiempo de finalización. Si hay un vértice madre, entonces tiene que ser esto.
paso1. Hacer la clasificación topológica de los vértices del gráfico dirigido.
paso2. Ahora comprobamos si podemos llegar a todos los vértices de primer vértice de vértices topológicamente ordenados en el paso 1.
para realizar un paso 2, de nuevo inicializar array descubierto [i] a falso y hacer dfs Startin de primer nodo de topológicamente vértices ordenados
Si se pueden alcanzar todos los vértices, el gráfico tiene el vértice madre y el vértice madre será el primero de los vértices clasificados topológicamente.
tiempo de complejidad: el paso 1 toma O(n + m), paso 2 toma O(n + m) tan total O(n+m) + O(n+m) = O(n+m)
Algoritmo ::
a) Hacer DFS/BFS del gráfico y no perder de vista el último vértice terminado 'X' .
b) Si existe algún vértice madre, entonces 'x' es una de ellas. Compruebe si 'x' es un vértice madre al hacer DFS/BFS desde el vértice 'x'.
Tiempo complejidad O (n + m) + O (n + m) = O (n + m)
hará este trabajo para la siguiente gráfica, si comienzo de B vértice como al azar? A-> B B-> A A-> C A-> D – learner