Que signifie pi dans ce pseudocode d'algorithme BFS?

9

J'ai le pseudocode suivant pour l' algorithme de recherche en largeur

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

Image originale

Je ne comprends pas ce que la lettre π indique dans ce contexte. Je ne connais pas cet algorithme et il est difficile à deviner.

Je pense dqu'indique la distance, colorc'est bien sûr la couleur, mais ça π... ça semble être une variable quelconque mais je ne comprends pas sa fonction dans ce pseudocode.

algorithms pseudocode notation nbro
la source
2
@Snowman J'adopterais le style utilisé dans les publications informatiques et universitaires plutôt que les mathématiques en particulier, mais je suis d'accord avec l'idée générale. Cette question demande à propos de cette utilisation aurait pu être répondue en lisant la page wikipedia , et π n'est pas quelque chose d'usage courant mais plutôt spécifique à la façon dont l'auteur écrit l'algorithme. Je crains qu'il y ait beaucoup trop de variations sur le pseudocode et je demande ce que chaque personnage de chaque style signifie pourrait devenir incontrôlable.
1
La lettre π est-elle souvent utilisée dans le pseudocode? Parfois, mais la signification variera selon le contexte.
Rufflewind
1
@Snowman: π ici n'est pas une fonction. Il s'agit d'un tableau mutable de sommets indexés par des sommets.
Rufflewind
1
Dans ce contexte, π n'est qu'un symbole utilisé dans l'algorithme, similaire à d et à color. Parfois, les rédacteurs d'algorithmes aiment utiliser des symboles d'une seule lettre plutôt que des noms mignons comme "parentVertices" ou quelque chose qui pourrait avoir tendance à être utilisé dans un langage de programmation.
Brandin
@Snowman Vous plaisantez? Ce n'est pas une question mathématique. Il s'agit d'interpréter un pseudocode pour écrire un programme, pourquoi ne devrait-il pas s'agir de développement logiciel, je ne comprends vraiment pas.
nbro

Réponses:

17

Je crois que l'utilisation de π ici est réellement «parent de». Donc dans ce cas, le «parent» de v   est u parce que nous regardons tous les nœuds adjacents à u .

J Trana
la source
0

Le vecteur π conserve sûrement le nœud u avec lequel vous êtes venu dans le nœud v. Cela aide lorsque vous devez construire l'arborescence BFS du graphique. Bien qu'elle ne soit pas nécessaire, cette technique réduit considérablement la complexité lorsque vous devez exécuter plus de temps le BFS (par exemple, l' algorithme Edmonds – Karp pour calculer le flux maximal entre deux nœuds dans un graphique). Dans ce cas, vous n'avez pas besoin d'exécuter le BFS plusieurs fois car vous avez déjà construit l'arborescence BFS et le traversez des feuilles à la racine.

Columb
la source