Биографик Траверса путем следования за смежными узлами
[
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