Теодолитный объект-биограф путем следования за соседними узлами
[disc, pred, closed] = traverse(BGObj, S)
[...] = traverse(BGObj, S, ...'Depth', DepthValue, ...)
[...] = traverse(BGObj, S, ...'Directed', DirectedValue, ...)
[...] = traverse(BGObj, S, ...'Method', MethodValue, ...)
BGObj | Объект-биограф, созданный biograph (конструктор объекта). |
S | Целое число, указывающее исходный узел в BGObj. |
DepthValue | Целое число, указывающее узел в BGObj указывает глубину поиска. По умолчанию: Inf (бесконечность). |
DirectedValue | Свойство, указывающее, представлен ли граф матрицей близости N-на-N, извлеченной из объекта-биографа, BGObj является направленным или неориентированным. Войти false для неориентированного графа. Это приводит к игнорированию верхнего треугольника разреженной матрицы. По умолчанию: true. |
MethodValue | Символьный вектор, указывающий алгоритм, используемый для прохождения по графу. Возможны следующие варианты:
|
Совет
Вводные сведения о функциях теории графов см. в разделе Функции теории графов.
[ пересекает направленный граф, представленный матрицей смежности N-на-N, извлеченной из объекта-биографа, disc, pred, closed] = traverse(BGObj, S)BGObj, начиная с узла, обозначенного целым числом S. В разреженной матрице N-на-N все ненулевые записи указывают на наличие ребра. disc - вектор индексов узлов в порядке их обнаружения. pred является вектором индексов узлов-предшественников (перечисленных в порядке индексов узлов) результирующего покрывающего дерева. closed - вектор индексов узлов в порядке их закрытия.
[...] = traverse( требования BGObj, S, ...'PropertyName', PropertyValue, ...)traverse с необязательными свойствами, использующими пары имя/значение свойства. Можно указать одно или несколько свойств в любом порядке. Каждый PropertyName должен быть заключен в одинарные кавычки и не чувствителен к регистру. Эти пары имя/значение свойства следующие:
[...] = traverse( указывает глубину поиска. BGObj, S, ...'Depth', DepthValue, ...)DepthValue - целое число, указывающее узел в графе, представленном матрицей близости N-на-N, извлеченной из объекта-биографа, BGObj. По умолчанию: Inf (бесконечность).
[...] = traverse( указывает, был ли график представлен матрицей близости N-на-N, извлеченной из объекта-биографа, BGObj, S, ...'Directed', DirectedValue, ...)BGObj является направленным или неориентированным. Набор DirectedValue кому false для неориентированного графа. Это приводит к игнорированию верхнего треугольника разреженной матрицы. По умолчанию: true.
[...] = traverse( позволяет задать алгоритм, используемый для прохождения графика, представленного матрицей смежности N-на-N, извлеченной из объекта-биографа, BGObj, S, ...'Method', MethodValue, ...)BGObj. Возможны следующие варианты:
'BFS' - Широтно-первый поиск. Сложность времени O(N+E), где N и E - количество узлов и рёбер соответственно.
'DFS' - Алгоритм по умолчанию. Поиск по глубине. Сложность времени O(N+E), где N и E - количество узлов и рёбер соответственно.
[1] Седжевик, Р., (2002). Алгоритмы в C++, часть 5 Алгоритмы графов (Эддисон-Уэсли).
[2] Сиек, Дж. Г., Ли, L-Q, и Люмсдейн, А. (2002). Руководство пользователя и справочное руководство библиотеки Boost Graph (Upper Saddle River, NJ: Pearson Education).
allshortestpaths | biograph | conncomp | graphtraverse | isdag | isomorphism | isspantree | maxflow | minspantree | shortestpath | topoorder