Descripción general
En este tutorial, discutiremos el concepto de componentes conectados en un gráfico no dirigido.
Repasaremos algunos ejemplos simples para obtener una comprensión básica, y luego enumeraremos las propiedades de los componentes conectados.
Definición de componente conectado
Un componente conectado o simplemente un componente de un gráfico no dirigido es un subgrafo en el que cada par de nodos está conectado entre sí a través de una ruta.
Intentemos simplificarlo aún más. Un conjunto de nodos forma un componente conectado en un gráfico no dirigido si cualquier nodo del conjunto de nodos puede llegar a cualquier otro nodo atravesando bordes. El punto principal aquí es la accesibilidad.
En los componentes conectados, todos los nodos son siempre accesibles entre sí.
Algunos ejemplos
En esta sección, discutiremos un par de ejemplos simples. Intentaremos relacionar los ejemplos con la definición dada anteriormente.
3.1. Un componente conectado
En este ejemplo, el gráfico no dirigido dado tiene un componente conectado:
Vamos a nombrar este gráfico 
. Aquí 
denota el conjunto de vértices y 
denota el conjunto de aristas de 
. El gráfico tiene un componente conectado, vamos a nombre 
, que contiene todos los vértices de . Ahora vamos a comprobar si el conjunto se ajusta a la definición o no.
De acuerdo con la definición, los vértices en el conjunto deben llegar unos a otros a través de una ruta de acceso. Estamos eligiendo al azar dos vértices 
y 
:
- es accesible a a través de:
- es accesible a a través de:
Los vértices y satisfecho la definición, y podríamos hacer lo mismo con otros pares de vértices en el así.
3.2. Más de un componente conectado
En este ejemplo, el gráfico no dirigido tiene tres componentes conectados:
Let’s name this graph as 
, where 
, and 
. The graph 
has 3 connected components: 
and 
.
Ahora, vamos a ver si los componentes conectados 
y 
satisfacen la definición o no. Vamos a elegir aleatoriamente un par de cada y conjunto.
Desde el , vamos a elegir los vértices 
y .
- es accesible a a través de:
- es accesible a a través de:
Ahora vamos a elegir los vértices 
y 
desde el .
- is reachable to
- is reachable to
Finally, let’s pick the vertices 
and 
from the set .
- is reachable to
- es accesible a
Así que a partir de estos simples manifestaciones, está claro que el y siga el componente conectado definición.
Propiedades
Como ya hemos discutido la definición y demostrado un par de ejemplos de los componentes conectados, es un buen momento para enumerar algunas de las propiedades importantes que el componente conectado siempre tiene.
En primer lugar, el conjunto de componentes conectados siempre no está vacío.
Además, si hay más de un componente conectado para un gráfico dado, la unión de componentes conectados dará el conjunto de todos los vértices del gráfico dado.
Por ejemplo :
Finalmente, los conjuntos de componentes conectados se disocian en parejas. Eso significa que si tomamos la intersección entre dos conjuntos de componentes conectados diferentes, la intersección será igual a un conjunto vacío o a un conjunto nulo.
Consideremos de nuevo los componentes conectados de graph . En , vamos a comprobar esta propiedad:
Encontrar los Componentes Conectados
Dado un grafo no dirigido, es importante averiguar el número de componentes conectados a analizar la estructura de la gráfica – tiene muchas aplicaciones en la vida real. Podemos usar DFS o BFS para esta tarea.
En esta sección, discutiremos un algoritmo basado en DFS que nos da el número de componentes conectados para un gráfico no dirigido dado:
La variable Component_Count devuelve el número de componentes conectados en el gráfico dado.
Comenzamos inicializando todos los vértices a la bandera no visitada. Luego elegimos cualquier vértice aleatorio para comenzar y verificamos si hemos visitado el vértice o no. Si no lo hicimos, llamamos a la función DFS.
Una vez que todos los vértices marcados como visitados, el algoritmo termina e imprime el número de los componentes conectados.
En la función DFS, los argumentos que pasamos son un conjunto de vértices que contiene todos los vértices del gráfico dado y un vértice en particular que debe pertenecer al conjunto de vértices.
Primero, marcamos el vértice de entrada particular como visitado. Luego calculamos los vértices adyacentes del vértice de entrada particular dado. Para cada vértice adyacente, comprobamos si los visitamos o no. Si no, entonces llamamos a la función DFS recursivamente hasta que marcamos todos los vértices adyacentes como visitados.
El punto clave a observar en el algoritmo es que el número de componentes conectados es igual al número de llamadas a funciones DFS independientes. La variable Component_Count cuenta el número de llamadas. Por supuesto, esto no incluye las llamadas que se están haciendo bajo la función DFS() recursivamente.
Ejecución de prueba
Ejecutemos el algoritmo en un gráfico de muestra:
Dado un grafo no dirigido 
, donde 
y 
.
El primer paso del algoritmo es inicializar todos los vértices y marcarlos como no visitados.
El vértice rojo indica que no se visita. El vértice verde indica que es visitado por el algoritmo:
Podemos elegir cualquier vértice de la lista de vértices para iniciar el algoritmo. Vamos a elegir .
El algoritmo comprueba si se visita o no. En este caso, no se visita. Por lo tanto, llama a 
.
Dentro de DFS (), primero, etiqueta el vértice como visitado y busca los vértices adyacentes de . Todos los vértices adyacentes también están marcados como visitados. Cuando DFS termina de visitar todos los vértices adyacentes de , el Component_Count se convierte en 1 y se actualiza el estado de los vértices:
De nuevo, el algoritmo selecciona cualquier vértice aleatorio. Vamos a elegir esta vez.
Comprueba si ya está visitado o no. Como no se visita, el algoritmo llama a 
. De nuevo, el algoritmo marca el vértice como visitado, y DFS busca sus vértices adyacentes y los marca como visitados. Ahora el Component_Count se convierte en 2, y el estado de la lista de vértices se actualiza de nuevo:
El algoritmo continúa y elige , comprueba el estado, y las llamadas 
. El vértice y sus vértices adyacentes se etiquetan como visitados y el Component_Count aumenta a 3. El algoritmo actualiza el estado de la lista de vértices:
Finalmente, el algoritmo elige , llama a 
, y hace que como visitado. El vértice no tiene vértices adyacentes, por lo que DFS devuelve y Component_Count aumenta a 4. Finalmente, el algoritmo actualiza el estado de la lista de vértices:
A medida que el algoritmo termina de atravesar todos los vértices del gráfico 
, termina y devuelve el valor de Component_Count que es igual al número de componentes conectados en G3:
Hemos utilizado cuatro colores diferentes para ilustrar los componentes conectados en el , a saber: 
.
Análisis de complejidad temporal
El algoritmo que acabamos de ver para encontrar componentes conectados en un gráfico no dirigido utiliza la búsqueda DFS y cuenta el número de llamadas a la función DFS. Si el gráfico está representado por la lista de adyacencia, la búsqueda DFS visita todos los vértices una vez y cada arista dos veces en el caso de un gráfico no dirigido. La comprobación del estado del vértice toma 
tiempo. Por lo tanto, en total, nuestro algoritmo tomará 
tiempo.
En caso de que el gráfico esté representado por la matriz de adyacencia, la búsqueda DFS toma 
tiempo, ya que necesita recorrer toda la fila para evaluar los vértices vecinos. La comprobación del estado del vértice de nuevo toma tiempo. Por lo tanto, nos da un total de 
tiempo.
Conclusión
En este artículo, discutimos una definición simple de componente conectado seguida de un par de ejemplos simples y fáciles de entender. Además, enumeramos algunas propiedades comunes pero importantes de los componentes conectados.
Luego, discutimos un algoritmo basado en búsquedas DFS para encontrar el número de componentes conectados en un gráfico dado. Demostramos el algoritmo con la ayuda de un gráfico de muestra. Por último, analizamos la complejidad temporal del algoritmo.