Algoritmos y Estructuras de Datos

Algoritmo de Búsqueda en Profundidad (DFS)

Imagina que estás controlando un robot que se encuentra en algún punto de un grafo con n vértices y e aristas. Quieres empezar desde un vértice y recorrer gradualmente todo el grafo visitando todos los vértices que sean alcanzables desde ese punto inicial. El algoritmo DFS te permite hacer exactamente esto: comienza en cierto vértice, luego explora un camino hasta que ya no haya más vértices en ese trayecto, y después regresa a los nodos anteriores para continuar explorando otras rutas desde allá.
Video preview
Video de Reducible - Depth First Search (DFS) Explained: Algorithm, Examples, and Code
Una forma muy útil de entender el algoritmo DFS es imaginarse un robot que recorre un grafo y solo puede ver los vecinos del nodo actual y los nodos que ya ha visitado (el robot va registrando todo el camino). Este proceso es recursivo: en cada paso, el robot se mueve a un nuevo vértice que no haya sido explorado antes y repite el procedimiento hasta que no haya más vértices en ese camino. La idea de un pequeño robot explorando el grafo resulta muy útil a la hora de implementar este algoritmo.
La implementación se puede hacer de forma recursiva, donde llevamos un registro del vértice actual (marcado como v) y de todos los vértices que ya han sido visitados (marcados como used):
import sys

sys.setrecursionlimit(10 ** 6)          # Aumentar el límite de recursión para que DFS se ejecute correctamente

n, e = map(int, input().split())        # n: vértices, e: aristas
g = [[] for _ in range(n)]              # grafo - lista de adyacencia
used = [False] * n                      # vértices utilizados (visitados)

for _ in range(e):                      # leer aristas
    a, b = map(int, input().split())    # a -> b y b -> a
    g[a].append(b)
    g[b].append(a)


def dfs(v):                             # búsqueda en profundidad
    used[v] = True                      # marcar vértice como visitado
    print(v, end=' ')                   # imprimir vértice
    for to in g[v]:                     # para cada vértice conectado con v
        if not used[to]:                # si no está visitado
            dfs(to)                     # llamar a dfs en ese vértice


start = int(input())                    # vértice de inicio
dfs(start)                              # llamar a dfs con el vértice de inicio
Aquí primero inicializamos el grafo y comenzamos el recorrido a partir del vértice start. Al principio, todos los valores de used están en False. Después de visitar cada vértice, lo marcamos con used[v] = True para indicar que ya fue visitado, y luego nos movemos a los vecinos del vértice actual v.
Observa cómo la recursividad desempeña el papel de explorar un camino y luego retroceder al punto anterior para seguir explorando a partir de ahí. Cuando retrocedemos dentro de la recursión, esencialmente volvemos al vértice previo.
Veamos cómo funciona el algoritmo en varios ejemplos:
n = 4, e = 4
Las parejas de entrada a, b son: [(0, 1), (0, 2), (1, 2), (3, 2)]
El vértice de inicio es 3
  1. v = 3 → used = [False, False, False, True]
  1. Explorar todos los vecinos de 3 ⇒ [2]
  1. v = 2 → used = [False, False, True, True]
  1. Explorar todos los vecinos de 2 ⇒ [0, 1]
  1. v = 0 → used = [True, False, True, True]
  1. Explorar todos los vecinos de 0 ⇒ [1, 2]
  1. v = 1 → used = [True, True, True, True]
  1. Explorar todos los vecinos de 1 ⇒ [0, 2] ⇒ Todos están visitados
  1. Retroceder desde 1
  1. Retroceder desde 0
  1. Retroceder desde 2
  1. Retroceder desde 3 → terminar DFS
  1. Fin
n = 5, e = 4
Las parejas de entrada a, b son: [(0, 1), (0, 2), (1, 2), (3, 4)]
El vértice de inicio es 0
  1. v = 0 → used = [True, False, False, False, False]
  1. Explorar todos los vecinos de 0 ⇒ [1, 2]
  1. v = 1 → used = [True, True, False, False, False]
  1. Explorar todos los vecinos de 1 ⇒ [0, 2]
  1. v = 2 → used = [True, True, True, False, False]
  1. Explorar todos los vecinos de 2 ⇒ [0, 1] ⇒ Todos están visitados
  1. Retroceder desde 2
  1. Retroceder desde 1
  1. Retroceder desde 0 → termina el DFS
  1. Fin
      2. Notice how nodes 3 and 4 were never visited.
      They were not connected to the initial node 0.
n = 10, e = 11 (ejemplo del video)
Las parejas de entrada a, b son: [(0, 1), (0, 2), (1, 2), (1, 4), (1, 3), (3, 5), (6, 5), (5, 8), (5, 7), (7, 8), (8, 9)]
El vértice de inicio es 0
  1. v = 0 → used = [T, F, F, F, F, F, F, F, F, F] ⇒ explorar [1, 2]
  1. v = 1 → used = [T, T, F, F, F, F, F, F, F, F] ⇒ explorar [0, 2, 3, 4]
  1. v = 2 → used = [T, T, T, F, F, F, F, F, F, F] ⇒ explorar [0, 1]
  1. Retroceder desde 2
  1. v = 1 → used = [T, T, T, F, F, F, F, F, F, F] ⇒ explorar [x, x, 3, 4]
  1. v = 3 → used = [T, T, T, T, F, F, F, F, F, F] ⇒ explorar [1, 5]
  1. v = 5 → used = [T, T, T, T, F, T, F, F, F, F] ⇒ explorar [3, 6, 7, 8]
  1. v = 6 → used = [T, T, T, T, F, T, T, F, F, F] ⇒ explorar [5]
  1. Retroceder desde 6
  1. v = 7 → used = [T, T, T, T, F, T, T, T, F, F] ⇒ explorar [5, 8]
  1. v = 8 → used = [T, T, T, T, F, T, T, T, T, F] ⇒ explorar [5, 7, 9]
  1. v = 9 → used = [T, T, T, T, F, T, T, T, T, T] ⇒ explorar [8]
  1. Retroceder desde 8
  1. Retroceder desde 7
  1. Retroceder desde 6
  1. Retroceder desde 5
  1. Retroceder desde 3
  1. v = 1 → used = [T, T, T, T, F, T, T, T, T, T] ⇒ explorar [x, x, x, 4]
  1. v = 4 → used = [T, T, T, T, T, T, T, T, T, T] ⇒ explorar [1]
  1. Retroceder desde 4
  1. Retroceder desde 1
  1. Retroceder desde 0
  1. Fin
 

Desafío: Contar el número de componentes conectados en un grafo

Dado un grafo no dirigido con v vértices y e aristas, se te pide calcular cuántas componentes conectadas tiene el grafo. Se considera que un conjunto de vértices forma una componente conectada si es posible viajar entre todos ellos.

Entrada

La primera línea de la entrada contiene dos enteros v (1 ≤ v ≤ 100 000) y e (1 ≤ e ≤ 100 000).
Las siguientes e líneas contienen pares de enteros v1, v2 (1 ≤ v1, v2 ≤ v) que indican que el vértice v1 está conectado con el vértice v2 y viceversa.

Salida

El programa debe imprimir el número de componentes conectados en el grafo.

Ejemplos

Entrada
Salida
7 6 1 2 2 3 1 3 4 5 5 6 4 6
3
2 1 1 2
1
2 0
2
 

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue