Algoritmos y Estructuras de Datos (VJ1215)

El ejercicio planteado equivale a contar cuántas componentes conexas tiene un grafo no dirigido.

En ejercicios previos has aprendido a realizar la búsqueda en anchura partiendo de un vértice origen dado. Eso sirve para encontrar todos los vértices que están en la misma componente conexa que el vértice origen. Si aplicamos eso repetidamente, partiendo cada vez de un vértice origen que no haya sido visitado previamente, cada vez que iniciemos una nueva búsqueda en anchura estaremos recorriendo una nueva componente conexa del grafo. Para resolver eficientemente el ejercicio propuesto, basta añadir a eso un contador, como se muestra a continuación.

El coste temporal y espacial de esta solución es el propio de la búsqueda en anchura: O(|V| + |E|), gracias a la representación del grafo mediante listas de adyacencia. Es así porque, incluso con el nuevo bucle externo, cada vértice entra y sale una sola vez de la cola y todos los bucles anidados pasan una sola vez por cada arco del grafo.

int GrafoNoDirigido::contarPicaduras() const {

   vector<bool> contagiado(vertices.size(), false);
   queue<int> cola;
   
   int contador = 0;
   
   for (int origen = 0; origen < vertices.size(); origen++)
      if (! contagiado[origen]) {
	 contador++;
	 contagiado[origen] = true;
	 cola.push(origen);
	 
	 while (! cola.empty()) {
	    int v = cola.front();
	    cola.pop();
	    for (Arco * arco = vertices[v].primerArco; arco != nullptr; arco = arco->siguiente)
	       if (! contagiado[arco->vecino]) {
		  contagiado[arco->vecino] = true;
		  cola.push(arco->vecino);
	       }
	 }
	 
      }
	 
   return contador;
	 
}
      

También se puede separar en dos métodos que hacen lo mismo:

void GrafoNoDirigido::contagiarBFS(int origen,
				   vector<bool> & contagiado) const {
   
   queue<int> cola;

   contagiado[origen] = true;
   cola.push(origen);
   
   while (! cola.empty()) {
      int v = cola.front();
      cola.pop();
      for (Arco * arco = vertices[v].primerArco; arco != nullptr; arco = arco->siguiente)
	 if (! contagiado[arco->vecino]) {
	    contagiado[arco->vecino] = true;
	    cola.push(arco->vecino);
	 }
   }
}
   
int GrafoNoDirigido::contarPicaduras() const {

   vector<bool> contagiado(vertices.size(), false);
   
   int contador = 0;
   
   for (int origen = 0; origen < vertices.size(); origen++)
      if (! contagiado[origen]) {
	 contador++;
	 contagiarBFS(origen, contagiado);
      }
	 
   return contador;
	 
}
      

En el ejercicio 20 veremos que lo mismo se puede hacer sustituyendo búsqueda en anchura por búsqueda en profundidad.