¿Qué significa pi en este pseudocódigo del algoritmo BFS?

9

Tengo el siguiente pseudocódigo para el algoritmo de búsqueda de amplitud

BFS(G,s)
 1 for each vertex uV(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 vAdj[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

Imagen original

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.

nbro
fuente
2
@Snowman Me gustaría seguir el estilo utilizado en informática y publicaciones académicas en lugar de matemáticas específicamente, pero estoy de acuerdo con la idea general. Esta pregunta sobre este uso podría haber sido respondida leyendo la página de Wikipedia , y π no es algo de uso común, sino más bien específico de cómo el autor escribe el algoritmo. Me preocupa que haya demasiadas variaciones en el pseudocódigo y preguntar qué significa cada personaje en cada estilo podría salirse de control.
1
¿A menudo se usa la letra π en pseudocódigo? A veces, pero el significado variará según el contexto.
Rufflewind
1
@Snowman: π aquí no es una función. Es una matriz mutable de vértices indexados por vértices.
Rufflewind
1
En este contexto, π es solo un símbolo utilizado en el algoritmo, similar a dy color. A veces, a los escritores de algoritmos les gusta usar símbolos de una sola letra en lugar de nombres lindos como "parentVertices" o algo que podría usarse en un lenguaje de programación.
Brandin
@Snowman ¿Estás bromeando? No es una pregunta matemática. Se trata de interpretar un pseudocódigo para escribir un programa, por qué no debería tratarse del desarrollo de software, realmente no puedo entenderlo.
nbro

Respuestas:

17

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 .

J Trana
fuente
0

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.

Columb
fuente