Boost Graph Library: Undirected Depth-First Search

Boost , ,

undirected_dfs

<

// named parameter version
template <typename Graph, typename P, typename T, typename R>
void undirected_dfs(Graph& G, const bgl_named_params<P, T, R>& params);
// non-named parameter version
template <typename Graph, typenameDFSVisitor, typename VertexColorMap, typename EdgeColorMap>
void undirected_dfs(const Graph& g, DFSVisitor vis, VertexColorMap vertex_color, EdgeColorMap edge_color)
template <typename Graph, typenameDFSVisitor, typename VertexColorMap, typename EdgeColorMap>
void undirected_dfs(const Graph& g, DFSVisitor vis,
                    VertexColorMap vertex_color, EdgeColorMap edge_color,
                    typename graph_traits<Graph>::vertex_descriptor start)

Theundirected_dfs()функция выполняет первый по глубине обход вершин в ненаправленном графе. Когда это возможно, первый по глубине проход выбирает вершину, прилегающую к текущей вершине, чтобы посетить следующую. Если все соседние вершины уже обнаружены или нет смежных вершин, то алгоритм возвращается к последней вершине, у которой были неоткрытые соседи. Как только все доступные вершины были посещены, алгоритм выбирает из любых оставшихся неоткрытых вершин и продолжает прохождение. Алгоритм заканчивается, когда все вершины были посещены. Глубина-первый поиск полезен для категоризации краев в графе и для наложения порядка на вершины. РазделПервый поиск глубиныописывает различные свойства DFS и проходит через пример.

Как и BFS, цветовые маркеры используются для отслеживания того, какие вершины были обнаружены. Белые знаки вершин, которые еще предстоит обнаружить, серые знаки вершины, которая обнаружена, но все еще имеет вершины, прилегающие к ней, которые не обнаружены. Обнаружена черная вершина, которая не примыкает ни к каким белым вершинам.

Ярусы также окрашены во время поиска, чтобы разъяснить дерево и задние края.

undirected_dfs()функция вызывает определяемые пользователем действия в определенных точках событий в алгоритме. Это обеспечивает механизм адаптации общего алгоритма DFS ко многим ситуациям, в которых он может быть использован. В псевдокоде ниже точки событий для DFS обозначены треугольниками и ярлыками справа. Определяемые пользователем действия должны быть предоставлены в виде объекта посетителя, то есть объекта, тип которого соответствует требованиям для посетителяDFS. В псевдокоде мы показываем алгоритм вычисления предшественниковp, обнаруживаем времяdи заканчиваем времяt. По умолчаниюundirected_dfs()функция не вычисляет эти свойства, однако есть предварительно определенные посетители, такие какПредшественник_рекордериtime_stamper, которые могут быть использованы для этого.

DFS(G)
  for each vertex u in V 
    vcolor[u] := WHITE
    p[u] := u 
  end for
  for each edge e in E 
    ecolor[u] := WHITE
  end for
  time := 0
  if there is a starting vertex s
    call DFS-VISIT(G, s)
  for each vertex u in V 
    if vcolor[u] = WHITE
      call DFS-VISIT(G, u)
  end for
  return (p,d_time,f_time) 

DFS-VISIT(G, u) 
  vcolor[u] := GRAY
  d_time[u] := time := time + 1 
  for each e in Out[u] 
    var ec := ecolor[e]
    ecolor[e] := BLACK
    if (vcolor[v] = WHITE)
      p[v] := u 
      call DFS-VISIT(G, v)
    else if (vcolor[v] = GRAY and ec = WHITE)
      ...
    ...
  end for
  vcolor[u] := BLACK
  f_time[u] := time := time + 1 

-
-
initialize vertex u
-
-
-
-
-
-
-
start vertex s
-
-
start vertex u
-
-
-
-
discover vertex u
-
examine edge (u,v)
-
-
(u,v) is a tree edge
-
-
(u,v) is a back edge
-
-
finish edge (u,v)
-
finish vertex u
-

Where Defined

boost/graph/undirected_dfs.hpp

Parameters

An undirected graph. The graph type must be a model of Incidence Graph, Vertex List Graph, and Edge List Graph.
Python: The parameter is named graph.

Named Parameters

A visitor object that is invoked inside the algorithm at the event-points specified by the DFS Visitor concept. The visitor object is passed by value [1].
Default: dfs_visitor<null_visitor>
Python: The parameter should be an object that derives from the DFSVisitor type of the graph.

This is used by the algorithm to keep track of its progress through the graph. The type VertexColorMap must be a model of Read/Write Property Map and its key type must be the graph's vertex descriptor type and the value type of the color map must model ColorValue.
Default: an iterator_property_map created from a std::vector of default_color_type of size num_vertices(g) and using the i_map for the index map.
Python: The color map must be a vertex_color_map for the graph.

This is used by the algorithm to keep track of which edges have been visited. The type EdgeColorMap must be a model of Read/Write Property Map and its key type must be the graph's edge descriptor type and the value type of the color map must model ColorValue.
Default: none.
Python: The color map must be an edge_color_map for the graph.

This specifies the vertex that the depth-first search should originate from. The type is the type of a vertex descriptor for the given graph.
Default: *vertices(g).first

This maps each vertex to an integer in the range [0, num_vertices(g)). This parameter is only necessary when the default color property map is used. The type VertexIndexMap must be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.
Default: get(vertex_index, g) Note: if you use this default, make sure your graph has an internal vertex_index property. For example, adjacency_list with VertexList=listS does not have an internal vertex_index property.
Python: Unsupported parameter.

Complexity

The time complexity is O(E + V).

Visitor Event Points

• vis.initialize_vertex(s, g) is invoked on every vertex of the graph before the start of the graph search.
• vis.start_vertex(s, g) is invoked on the source vertex once before the start of the search.
• vis.discover_vertex(u, g) is invoked when a vertex is encountered for the first time.
• vis.examine_edge(e, g) is invoked on every out-edge of each vertex after it is discovered.
• vis.tree_edge(e, g) is invoked on each edge as it becomes a member of the edges that form the search tree. If you wish to record predecessors, do so at this event point.
• vis.back_edge(e, g) is invoked on the back edges in the graph.
• vis.finish_edge(e, g) is invoked on the back edges in the graph as well as on each tree edge after its target vertex is finished.
• vis.finish_vertex(u, g) is invoked on a vertex after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before their out-edges have been examined).

Example

An example is in examples/undirected_dfs.cpp.

See Also

Notes

[1] Since the visitor parameter is passed by value, if your visitor contains state then any changes to the state during the algorithm will be made to a copy of the visitor object, not the visitor object passed in. Therefore you may want the visitor to hold this state by pointer or reference.

Статья Boost Graph Library: Undirected Depth-First Search раздела может быть полезна для разработчиков на c++ и boost.

:: Главная :: ::