Как получить доступ к вершине предка во время поиска в ширину с помощью библиотеки графов ускорения?

Question

Я пытаюсь написать свою собственную версию обнаружения подключенных компонентов, используя алгоритм поиска в ширину, включенный в библиотеку графов ускорения, и мне нужно получить доступ к вершине предка (вершина, которая приводит к открытию текущей вершины)от отмены обратного вызова Discover_vertex моего посетителя, чтобы установить номер компонента текущей вершины.В любом случае это легко сделать?

Answer 1

Создание обратного вызова exam_vertex, в котором записывается проверяемая вершина (извлеченная из очереди).Эта вершина будет предком любой обнаруживаемой вершины.

Из псевдокода в документации 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)