Lo que está buscando es un algoritmo para verificar si el dígrafo está fuertemente conectado . Esto significa que para dos vértices en el dígrafo, hay un camino entre ellos. Esto está en contraste con débilmente conectado, donde ignora la dirección en los bordes y como la misma pregunta.
Aquí hay un algoritmo que lo hará por usted: compruebe si un gráfico está fuertemente conectado | Conjunto 1 (Kosaraju usando DFS) – GeeksforGeeks
También puede resultarle útil: Algoritmo para verificar si el gráfico dirigido está fuertemente conectado
- ¿Dónde puedo encontrar un algoritmo de ordenación que maneje los números dentro de las cadenas correctamente?
- Cómo hacer para recolectar datos de entrenamiento para un algoritmo de aprendizaje automático
- ¿El conocimiento de algoritmos codiciosos a veces influye en la forma de tomar decisiones?
- ¿Cuál es el concepto de la función recursiva en matemáticas?
- ¿Cuál es la explicación de este código?
Aquí hay una lista de algoritmos que también harán el trabajo (se usan para encontrar todos los componentes fuertemente conectados en el dígrafo): Componente fuertemente conectado – Wikipedia
El algoritmo de Tarjan debería ser el enfoque más eficiente para adoptar aquí. Se puede hacer en tiempo lineal y requiere un recorrido transversal primero en profundidad.
Aquí hay más discusión: ¿Hay alguna diferencia, ventajas o desventajas entre el algoritmo de Kosaraju y el algoritmo de Tarjan para encontrar componentes fuertemente conectados? ¿Cuál es más útil?
¡Espero que esto ayude!
