Как получить доступ к вершине предка во время поиска в ширину с библиотекой графика Boost?
-
29-09-2019 - |
Вопрос
Я пытаюсь написать свою собственную версию подключенных компонентов Discovery, используя алгоритм поиска, включенный в библиотеку Graph Boost, и мне нужно получить доступ к предку (вершина, которая приводит к обнаружению вершины вершины). Discover_vertex обратный вызов моего посетителя, чтобы установить номер компонента текущей вершины. В любом случае это можно сделать легко?
Решение
Создайте обратный вызов examine_vertex, который записывает изучаемую вершину (выпавшую из очереди). Эта вершина будет предком любой вершины, обнаруженной.
От псевдода в BGL Документация BFS:
vis.examine_vertex (u, g) вызывается в каждой вершине, когда она удаляется из очереди.
BFS(G, s)
for each vertex u in V[G]
color[u] := WHITE
d[u] := infinity
p[u] := u
end for
color[s] := GRAY
d[s] := 0
ENQUEUE(Q, s)
while (Q != Ø)
u := DEQUEUE(Q) # `u` is recorded in examine_vertex callback
for each vertex v in Adj[u]
if (color[v] = WHITE)
color[v] := GRAY
d[v] := d[u] + 1
p[v] := u
ENQUEUE(Q, v) # `v` is discovered, `u` is its ancestor.
else
if (color[v] = GRAY)
...
else
...
end for
color[u] := BLACK
end while
return (d, p)
Не связан с StackOverflow