Биографик Траверса путем следования за смежными узлами
[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 является вектором индексов узлов в том порядке, в котором они закрыты.
[...] = траверс вызывает (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] Sedgewick, R., (2002). Алгоритмы в C++, Алгоритмы графика части 5 (Эддисон-Уэсли).
[2] Siek, J.G., Lee, L-Q, and Lumsdaine, A. (2002). Руководство пользователя библиотеки График (Upper Saddle River, NJ: Pearson Education).
allshortestpaths | biograph | conncomp | graphtraverse | isdag | isomorphism | isspantree | maxflow | minspantree | shortestpath | topoorder
