У меня есть следующий псевдокод для алгоритма поиска в ширину
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
Я не понимаю, что буква π указывает в этом контексте. Я не знаком с этим алгоритмом, и его трудно угадать.
Я думаю, dуказывает на расстояние, colorэто, конечно, цвет, но это π... кажется, что это какая-то переменная, но я не понимаю ее функции в этом псевдокоде.
Ответы:
Я считаю, что использование π здесь является фактическим «родителем». Так что в этом случае «родителем» v является u, потому что мы смотрим на все узлы, смежные с u .
источник
Вектор π, безусловно, сохраняет узел u, с которым вы попали в узел v. Это помогает, когда вам нужно построить дерево BFS графа. Хотя в этом нет необходимости, этот метод значительно снижает сложность, когда вам нужно больше времени выполнять BFS (например, алгоритм Эдмондса-Карпа для вычисления максимального потока между двумя узлами в графе). В этом случае вам не нужно больше запускать BFS, так как у вас уже есть построенное дерево BFS и пройти его от листьев к корню.
источник