traverse (biograph)

Биографик Траверса путем следования за смежными узлами

Синтаксис

[disc, pred, closed] = traverse(BGObjS)
[...] = traverse(BGObjS, ...'Depth', DepthValue, ...)
[...] = traverse(BGObjS, ...'Directed', DirectedValue, ...)
[...] = traverse(BGObjS, ...'Method', MethodValue, ...)

Аргументы

BGObj Объект биографика, созданный biograph (конструктор объектов).
SЦелое число, которое указывает исходный узел в BGObj.
DepthValueЦелое число, указывающее узел в BGObj , задающий глубину поиска. По умолчанию это Inf (бесконечность).
DirectedValueСвойство, которое указывает, представлен ли график матрицей смежности N на N, извлеченной из объекта биографика, BGObj направлен или неориентирован. Введите false для неориентированного графа. Это приводит к игнорированию верхнего треугольника разреженной матрицы. По умолчанию это true.
MethodValueВектор символов, который задает алгоритм, используемый для прохождения графика. Варианты:
  • 'BFS' - Широта - первый поиск. Сложность во времени O(N+E), где N и E являются числом узлов и кромками соответственно.

  • 'DFS' - Алгоритм по умолчанию. Поиск глубины - первый. Сложность во времени O(N+E), где N и E являются числом узлов и кромками соответственно.

Описание

Совет

Для получения вводной информации о функциях теории графиков, см. «Функции теории графиков».

[disc, pred, closed] = traverse(BGObjS) проходит ориентированный граф, представленный N-на-N матрицей смежности, извлеченной из объекта биографика, BGObj, начиная с узла, обозначенного целым числом S. В разреженной матрице N на N все ненулевые значения указывают на наличие ребра. disc является вектором индексов узлов в том порядке, в котором они обнаружены. pred является вектором индексов предшествующих узлов (перечисленных в порядке индексов узлов) получившегося покрывающего дерева. closed является вектором индексов узлов в том порядке, в котором они закрыты.

[...] = траверс (BGObjS ... 'PropertyName', PropertyValue, ...) вызывает traverse с необязательными свойствами, которые используют пары имя/значение свойства. Можно задать одно или несколько свойств в любом порядке. Каждый PropertyName должны быть заключены в одинарные кавычки и нечувствительны к регистру. Эти имена свойства/пары значения свойств следующие:

[...] = traverse(BGObjS, ...'Depth', DepthValue, ...) задает глубину поиска. DepthValue - целое число, указывающее узел в графике, представленном матрицей смежности N на N, извлеченной из объекта биографика, BGObj. По умолчанию это Inf (бесконечность).

[...] = traverse(BGObjS, ...'Directed', DirectedValue, ...) указывает, извлечен ли из объекта биографика графиков, представленный матрицей смежности N на N BGObj направлен или неориентирован. Задайте DirectedValue на false для неориентированного графа. Это приводит к игнорированию верхнего треугольника разреженной матрицы. По умолчанию это true.

[...] = traverse(BGObjS, ...'Method', MethodValue, ...) позволяет вам задать алгоритм, используемый для прохождения графика, представленной матрицей смежности N на N, извлеченной из объекта биографика, 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).

Введенный в R2006b
Для просмотра документации необходимо авторизоваться на сайте