Collaboration diagram for Graph Library:Classes | |
| struct | DefaultDFSVisitor< Graph > |
| Пустой посетитель алгоритма обхода графа в глубину. More... | |
| struct | DefaultBicompVisitor< Graph > |
| Посетитель алгоритма поиска блоков и точек сочленения в неориентированном графе. More... | |
| class | BicompDFSVisitor< Graph, BicompVisitor > |
| Посетитель обхода в глубину для поиска блоков и точек сочленения. More... | |
| class | MtBicompSearch< Graph > |
| Отображение реберных свойств для графов, поддерживающих концепцию смежности вершин (без явных ребер) More... | |
| class | MtStrongComponents< Graph, SCVisitor, NumVertexMap > |
| Algorithm for searching strongly connected components in a digraph. More... | |
| struct | DFS_element< Graph > |
| Стековый элемент для алгоритма обхода в глубину. More... | |
Functions | |
| template<class Graph , class Visitor , class ColourMap > | |
| void | DepthFirstSearch (const Graph &graph, Visitor &vis, ColourMap &colourMap) |
| Алгоритм обхода в глубину графа смежности. More... | |
| const std::vector< vertex_index > & | MtBicompSearch< Graph >::SearchCutnodes () |
| Найти все точки сочленения | |
Detailed Description
Function Documentation
◆ DepthFirstSearch()
template<class Graph , class Visitor , class ColourMap >
| void DepthFirstSearch | ( | const Graph & | graph, |
| Visitor & | vis, | ||
| ColourMap & | colourMap | ||
| ) |
Алгоритм обхода в глубину графа смежности.
Вычислительная сложность алгоритма практически линейная, если считать что методы визитера выполняются за константное время.
- Parameters
-
graph Граф смежных вершин. vis Посетитель алгоритма.
