Tengo el siguiente pseudocódigo para el algoritmo de búsqueda de amplitud
BFS(G,s)
1 for each vertex u ∈ V(G) \ {s}
2 color[u] = white
3 d[u] = ∞
4 π[u] = nil
5 color[s] = gray
6 d[s] = 0
7 π[s] = nil
8 Q = ∅
9 Enqueue(Q,s)
10 while q ≠ ∅
11 u = Dequeue(Q)
12 for each v ∈ Adj[u]
13 if color[v] == white
14 color[v] = gray
15 d[v] = d[u] + 1
16 π[v] = u
17 Enqueue(Q,v)
18 color[u] = black
No entiendo lo que indica la letra π en este contexto. No estoy familiarizado con este algoritmo y es difícil de adivinar.
Creo que dindica la distancia, colorpor supuesto , es el color, pero eso π... parece ser una variable de algún tipo, pero no entiendo su función en este pseudocódigo.
Respuestas:
Creo que el uso de π aquí es real "padre de". Entonces, en este caso, el "padre" de v es u porque estamos viendo todos los nodos adyacentes a u .
fuente
El vector π seguramente mantiene el nodo u con el que entró en el nodo v. Esto ayuda cuando tiene que construir el árbol BFS del gráfico. Aunque no es necesario, esta técnica reduce mucho la complejidad cuando tiene que realizar más tiempo el BFS (por ejemplo, el algoritmo Edmonds-Karp para calcular el flujo máximo entre dos nodos en un gráfico). En este caso, no tiene que ejecutar el BFS más veces, ya que tiene el árbol BFS construido y atravesarlo desde las hojas hasta la raíz.
fuente