O que pi significa nesse pseudocódigo do algoritmo BFS?

9

Eu tenho o seguinte pseudocódigo para o algoritmo de pesquisa da primeira largura

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

Imagem original

Não entendo o que a letra π indica nesse contexto. Não conheço esse algoritmo e é difícil adivinhar.

Acho que dindica a distância, coloré claro a cor, mas isso π... parece ser uma variável de algum tipo, mas não entendo sua função nesse pseudocódigo.

algorithms pseudocode notation nbro
fonte
2
@Snowman Eu adotaria o estilo usado nas ciências da computação e nas publicações acadêmicas, em vez de especificamente na matemática , mas concordo com a ideia geral. Esta pergunta é sobre esse uso pode ter sido respondida lendo a página da Wikipedia , e π não é algo de uso comum, mas específico de como o autor escreve o algoritmo. Eu me preocupo que haja muitas variações no pseudocódigo e perguntando sobre o que cada personagem de cada estilo significa que poderia ficar fora de controle.
11
Geralmente, a letra π é usada no pseudocódigo? Às vezes, mas o significado varia dependendo do contexto.
Rufflewind
11
@ Snowman: π aqui não é uma função. É uma matriz mutável de vértices indexados por vértices.
Rufflewind
11
Nesse contexto, π é apenas um símbolo usado no algoritmo, semelhante a d e cor. Às vezes, os criadores de algoritmos gostam de usar símbolos de letra única em vez de nomes fofos como "parentVertices" ou algo que possa tender a ser usado em uma linguagem de programação.
Brandin
@Snowman Você está brincando? Não é uma questão de matemática. Trata-se de interpretar um pseudocódigo para escrever um programa, por que não se trata de desenvolvimento de software, eu realmente não consigo entender.
N /

Respostas:

17

Eu acredito que o uso de π aqui é "pai de" real. Portanto, neste caso, o "pai" de v   é u porque estamos vendo todos os nós adjacentes a u .

J Trana
fonte
0

O vetor π certamente mantém o nó u com o qual você entrou no nó v. Isso ajuda quando você precisa construir a árvore BFS do gráfico. Embora não seja necessário, essa técnica reduz muito a complexidade quando você precisa executar mais tempo o BFS (por exemplo, o algoritmo Edmonds – Karp para calcular o fluxo máximo entre dois nós em um gráfico). Nesse caso, você não precisa executar o BFS mais vezes, já que a árvore do BFS foi construída e atravessá-la das folhas para a raiz.

Columb
fonte