graphtraverse

График теодолитного хода по следующим смежным узлам

Синтаксис

[disc, pred, closed] = graphtraverse(G, S) [...] = graphtraverse(G, S, ...'Depth', DepthValue, ...) [...] = graphtraverse(G, S, ...'Directed', DirectedValue, ...) [...] = graphtraverse(G, S, ...'Method', MethodValue, ...)

Аргументы

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

Описание

Совет

Вводные сведения о функциях теории графов см. в разделе Функции теории графов.

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

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

[...] = graphtraverse(G, S, ...'Depth', DepthValue, ...) указывает глубину поиска. DepthValue - целое число, указывающее узел в графе G. По умолчанию: Inf (бесконечность).

[...] = graphtraverse(G, S, ...'Directed', DirectedValue, ...) указывает, направлен или не направлен график. Набор DirectedValue кому false для неориентированного графа. Это приводит к игнорированию верхнего треугольника разреженной матрицы. По умолчанию: true.

[...] = graphtraverse(G, S, ...'Method', MethodValue, ...) позволяет указать алгоритм, используемый для прохождения графика. Возможны следующие варианты:

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

Примеры

Создайте направленный график с 10 узлами и 12 ребрами.

DG = sparse([1 2 3 4 5 5 5 6 7 8 8 9],...
              [2 4 1 5 3 6 7 9 8 1 10 2],true,10,10)

DG =

   (3,1)        1
   (8,1)        1
   (1,2)        1
   (9,2)        1
   (5,3)        1
   (2,4)        1
   (4,5)        1
   (5,6)        1
   (5,7)        1
   (7,8)        1
   (6,9)        1
   (8,10)       1

h = view(biograph(DG))
Biograph object with 10 nodes and 12 edges.

Пройдите по графу, чтобы найти порядок обнаружения DFS, начиная с узла 4.
```
order = graphtraverse(DG,4)

order =

     4     5     3     1     2     6     9     7     8    10
```

Маркируйте узлы порядком обнаружения DFS.

for i = 1:10
    h.Nodes(order(i)).Label =...
			sprintf('%s:%d',h.Nodes(order(i)).ID,i);
end
h.ShowTextInNodes = 'label'
dolayout(h)

Пройдите по графу, чтобы найти порядок обнаружения BFS, начиная с узла 4.
```
order = graphtraverse(DG,4,'Method','BFS')

order =

     4     5     3     6     7     1     9     8     2    10
```

Маркируйте узлы порядком обнаружения BFS.

for i = 1:10
    h.Nodes(order(i)).Label =...
			sprintf('%s:%d',h.Nodes(order(i)).ID,i);
end
h.ShowTextInNodes = 'label'
dolayout(h)

Найдите и раскрасьте узлы, близкие к узлу 4 (в пределах двух краев).

node_idxs = graphtraverse(DG,4,'depth',2)

node_idxs =

     4     5     3     6     7

set(h.nodes(node_idxs),'Color',[1 0 0])

Ссылки

[1] Седжевик, Р., (2002). Алгоритмы в C++, часть 5 Алгоритмы графов (Эддисон-Уэсли).

[2] Сиек, Дж. Г., Ли, L-Q, и Люмсдейн, А. (2002). Руководство пользователя и справочное руководство библиотеки Boost Graph (Upper Saddle River, NJ: Pearson Education).

См. также

Представлен в R2006b

Документация