La frase “conectado” en este sentido es algo ambigua. Por ejemplo, alguien puede usar el término “conectado” aquí para decir “adyacente”, o en el sentido de que es probable que se pregunte qué pregunta realmente, ¿cómo puedo saber si dos vértices en un gráfico tienen una ruta donde están los dos vértices? los extremos del camino? (puede definir esto como “conectado”)
Para determinar si existe una ruta de este tipo, puede atravesar el gráfico utilizando la mayoría de los algoritmos de recorrido de gráficos (los que recomendaría son Breadth-First Search o Depth-First Search , un algoritmo de ruta más corto funcionará, pero sería imprudente) es menos eficiente ya que puede tener una ruta entre dos vértices que no tienen relación con el cálculo de una ruta más corta). Si no existe ese camino y el gráfico no está dirigido, lo que se puede inferir es que el gráfico no está conectado y los dos vértices pertenecen a dos componentes conectados diferentes.
Tenga en cuenta que algo se indica en la respuesta de Sean Francis Ballais a ¿Cómo encuentro si dos nodos están conectados? eso es incorrecto es decir que la búsqueda de Breadth first es un algoritmo de ruta más corta, esto no es cierto. La búsqueda de amplitud se puede usar para calcular rutas más cortas en situaciones tales como si el gráfico tiene los mismos pesos en cada borde, esto generalmente no es cierto para el problema de la ruta más corta .
- ¿Cuál es la importancia de un puerto de computadora?
- ¿Cuáles son los usos de la topología en estrella?
- ¿Las antenas de la red celular están conectadas entre sí por cable?
- ¿Cuáles son los pros y los contras de la conmutación de paquetes versus la conmutación de circuitos en redes de comunicación?
- Para ser un buen administrador del sistema, ¿qué cosas debo saber (tanto prácticas como teóricas)?
¡Espero que esto ayude!
