graphconncomp

Найти сильно или слабо связанные компоненты в графике

Синтаксис

[S, C] = graphconncomp(G) [S, C] = graphconncomp(G, ...'Directed', DirectedValue, ...) [S, C] = graphconncomp(G, ...'Weak', WeakValue, ...)

Аргументы

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

Описание

Совет

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

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

Количество найденных компонентов возвращается в S, и C - вектор, указывающий, какому компоненту принадлежит каждый узел.

Алгоритм Тарьяна имеет временную сложность O(N+E), где N и E - количество узлов и рёбер соответственно.

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

[S, C] = graphconncomp(G, ...'Directed', DirectedValue, ...) указывает, направлен или не направлен график. Набор directedValue кому false для неориентированного графа. Это приводит к игнорированию верхнего треугольника разреженной матрицы. По умолчанию: true. Алгоритм на основе DFS вычисляет подключенные компоненты. Сложность времени O(N+E), где N и E - количество узлов и рёбер соответственно.

[S, C] = graphconncomp(G, ...'Weak', WeakValue, ...) указывает, нужно ли находить слабо связанные компоненты или сильно связанные компоненты. Слабо соединяемая составляющая - это максимальная группа узлов, которые взаимно достижимы путем нарушения краевых направлений. Набор WeakValue кому true найти слабо связанные компоненты. По умолчанию: false, который находит сильно связанные компоненты. Состояние этого параметра не влияет на неориентированные графы, потому что слабо и сильно связные компоненты одинаковы в неориентированных графах. Сложность времени O(N+E), где N и E - количество узлов и рёбер соответственно.

Примечание

По определению, один узел может быть сильно связанным компонентом.

Примечание

Направленный ациклический граф (DAG) не может иметь каких-либо сильно связных компонентов больше единицы.

Примеры

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

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

DG =

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

h = view(biograph(DG));

Найдите количество сильно связанных компонентов в направленном графе и определите, какому компоненту принадлежит каждый из 10 узлов.
```
[S,C] = graphconncomp(DG)

S =

     4


C =

     4     4     4     1     1     2     2     4     4     3
```
Цветить узлы для каждого компонента другим цветом.
```
colors = jet(S);
for i = 1:numel(h.nodes)
  h.Nodes(i).Color = colors(C(i),:);
end
```

Ссылки

[1] Тарджан, Р. Э., (1972). Алгоритм поиска по глубине и линейный график. SIAM Journal on Computing 1 (2), 146-160.

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

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

См. также

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