En aquest tema, explorarem els algoritmes de cerca en grafs, que són fonamentals per a moltes aplicacions en informàtica, des de la navegació per xarxes fins a la resolució de problemes de camins. Ens centrarem en dos dels algoritmes més comuns: la Cerca en Amplada (BFS) i la Cerca en Profunditat (DFS).

La Cerca en Amplada (Breadth-First Search, BFS) és un algoritme de cerca que explora els veïns d'un node abans de moure's als seus descendents. És especialment útil per trobar el camí més curt en un graf no ponderat.

1. Inicialització:

   • Comença des d'un node inicial.
   • Utilitza una cua per mantenir els nodes que s'han de visitar.
   • Marca el node inicial com visitat.

2. Exploració:

   • Treu un node de la cua.
   • Afegeix tots els seus veïns no visitats a la cua.
   • Marca aquests veïns com visitats.

3. Repetició:

   • Repeteix el procés fins que la cua estigui buida.

• Inicialització: Creem una cua (deque) i afegim el node inicial. També marquem el node inicial com visitat.
• Exploració: Mentre la cua no estigui buida, traiem un node de la cua, imprimim el node i afegim els seus veïns no visitats a la cua.
• Repetició: El procés es repeteix fins que la cua estigui buida.

La Cerca en Profunditat (Depth-First Search, DFS) és un algoritme de cerca que explora tan profundament com sigui possible abans de retrocedir. És útil per explorar totes les possibilitats en un graf.

1. Inicialització:

   • Comença des d'un node inicial.
   • Utilitza una pila per mantenir els nodes que s'han de visitar.
   • Marca el node inicial com visitat.

2. Exploració:

   • Treu un node de la pila.
   • Afegeix tots els seus veïns no visitats a la pila.
   • Marca aquests veïns com visitats.

3. Repetició:

   • Repeteix el procés fins que la pila estigui buida.

• Inicialització: Creem una pila i afegim el node inicial.
• Exploració: Mentre la pila no estigui buida, traiem un node de la pila, imprimim el node i afegim els seus veïns no visitats a la pila.
• Repetició: El procés es repeteix fins que la pila estigui buida.

1. Implementació de BFS i DFS:

   • Implementa BFS i DFS per a un graf donat.
   • Prova amb diferents grafs i nodes inicials.

2. Aplicació de BFS:

   • Utilitza BFS per trobar el camí més curt en un graf no ponderat.

3. Aplicació de DFS:

   • Utilitza DFS per detectar cicles en un graf.

1. Implementació de BFS i DFS:

   • Ja hem proporcionat exemples de BFS i DFS en Python. Prova'ls amb diferents grafs.

2. Aplicació de BFS:

   def bfs_cami_mes_curt(graf, inici, final):
       cua = deque([(inici, [inici])])
       visitats = set()
   
       while cua:
           (node, cami) = cua.popleft()
           visitats.add(node)
           for veí en graf[node]:
               if veí en visitats:
                   continue
               if veí == final:
                   return cami + [veí]
               else:
                   cua.append((veí, cami + [veí]))
       return None
   
   # Exemple de graf
   graf = {
       'A': ['B', 'C'],
       'B': ['A', 'D', 'E'],
       'C': ['A', 'F'],
       'D': ['B'],
       'E': ['B', 'F'],
       'F': ['C', 'E']
   }
   
   print(bfs_cami_mes_curt(graf, 'A', 'F'))
   

3. Aplicació de DFS:

   def dfs_detectar_cicles(graf):
       visitats = set()
       pila = []
   
       def dfs(node, pare):
           visitats.add(node)
           pila.append(node)
           for veí en graf[node]:
               if veí no està en visitats:
                   if dfs(veí, node):
                       return True
               elif veí != pare:
                   return True
           pila.pop()
           return False
   
       for node en graf:
           if node no està en visitats:
               if dfs(node, None):
                   return True
       return False
   
   # Exemple de graf
   graf = {
       'A': ['B', 'C'],
       'B': ['A', 'D', 'E'],
       'C': ['A', 'F'],
       'D': ['B'],
       'E': ['B', 'F'],
       'F': ['C', 'E']
   }
   
   print(dfs_detectar_cicles(graf))
   

En aquesta secció, hem après sobre dos dels algoritmes de cerca en grafs més comuns: la Cerca en Amplada (BFS) i la Cerca en Profunditat (DFS). Hem vist com implementar-los en Python i hem explorat les seves aplicacions i diferències. Aquests algoritmes són fonamentals per a moltes aplicacions en informàtica i són eines essencials per a qualsevol programador.