graphconncomp

(Чтобы быть удаленным), Находят строго или слабо соединенные компоненты в графике

graphconncomp будет удален в будущем релизе. Использование conncomp вместо этого.

Синтаксис

[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 количество узлов и ребер соответственно.

SC] = graphconncomp (GPropertyName ', 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) не может иметь никаких строго связанных компонентов, больше, чем один.

Вопросы совместимости

развернуть все

Не рекомендуемый запуск в R2021b

Поведение изменяется в R2021b

Ссылки

[1] Тарьян, R.E., (1972). Поиск в глубину и линейные алгоритмы графика. SIAM Journal при Вычислении 1 (2), 146–160.

[2] Sedgewick, R., (2002). Алгоритмы на C++, алгоритмы графика части 5 (Аддисон-Уэсли).

[3] Siek, J.G., Ли, L-Q и Lumsdaine, A. (2002). Руководство пользователя библиотеки графика повышения и справочник, (верхний Сэддл-Ривер, образование НДЖ:ПИРСОНА).

Смотрите также

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