Algoritmos y Estructuras de Datos (VJ1215)

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

En la solución del ejercicio 9 el problema se resolvió mediante búsqueda en anchura. La siguiente solución muestra cómo obtener el mismo resultado mediante búsqueda en profundidad.

El coste temporal, tanto mediante búsqueda en anchura como mediante búsqueda en profundidad, es O(|V| + |E|), gracias a la representación del grafo mediante listas de adyacencia.

void GrafoNoDirigido::contagiarDFS(int v,
				   vector<bool> & contagiado) const {
   
   contagiado[v] = true;

   for (Arco * arco = vertices[v].primerArco; arco != nullptr; arco = arco->siguiente)
      if (! contagiado[arco->vecino])
	 contagiarDFS(arco->vecino, contagiado);
   
}

int GrafoNoDirigido::contarPicaduras() const {

   int cantidadDeVertices = vertices.size();
   vector<bool> contagiado(cantidadDeVertices, false);
   
   int contador = 0;

   for (int origen = 0; origen < cantidadDeVertices; origen++)
      if (! contagiado[origen]) {
	 contador++;
	 contagiarDFS(origen, contagiado);
      }

   return contador;

}