Найдите строго или слабо соединенные компоненты в биообъекте диаграмм
[S, C]
= conncomp(BGObj)
[S, C]
= conncomp(BGObj, ...'Directed', DirectedValue,
...)
[S, C]
= conncomp(BGObj, ...'Weak', WeakValue,
...)
BGObj | Биообъект диаграмм создается biograph Конструктор Object. |
DirectedValue | Свойство, которое указывает, направлен ли график или неориентированный. Введите false для неориентированного графа. Это приводит к верхнему треугольнику проигнорированной разреженной матрицы. Значением по умолчанию является true. Основанный на DFS алгоритм вычисляет связанные компоненты. Временной сложностью является |
WeakValue | Свойство, которое указывает, найти ли слабо соединенные компоненты или строго соединенные компоненты. Слабо связанный компонент является максимальной группой узлов, которые взаимно достижимы путем нарушения направлений ребра. Установите WeakValue к true найти слабо соединенные компоненты. Значением по умолчанию является false, который находит строго соединенные компоненты. Состояние этого параметра не оказывает влияния на неориентированных графов, потому что слабо и строго связанные компоненты то же самое в неориентированных графах. Временной сложностью является O(N+E), где N и E количество узлов и ребер соответственно. |
Дополнительные сведения о функциях теории графов см. в Функциях Теории графов.
[ находит строго связанные компоненты N на n матрицы смежности извлеченными из биообъекта диаграмм, S, C]
= conncomp(BGObj)BGObj использование алгоритма Тарьяна. Строго связанный компонент является максимальной группой узлов, которые взаимно достижимы, не нарушая направления ребра. N на n разреженная матрица представляет ориентированного графа; все ненулевые записи в матрице указывают на присутствие ребра.
Количество найденных компонентов возвращено в S, и C указание вектора, которому компоненту принадлежит каждый узел.
Алгоритм Тарьяна имеет временную сложность O(N+E), где N и E количество узлов и ребер соответственно.
SC] = conncomp (BGObjPropertyName ', PropertyValue, ...)conncomp с дополнительными свойствами, которые используют имя свойства / пары значения свойства. Можно задать одно или несколько свойств в любом порядке. Каждый PropertyName должен быть заключен в одинарные кавычки и нечувствительный к регистру. Это имя свойства / пары значения свойства следующие:
[ указывает, направлен ли график или неориентированный. Установите S, C]
= conncomp(BGObj, ...'Directed', DirectedValue,
...)DirectedValue к false для неориентированного графа. Это приводит к верхнему треугольнику проигнорированной разреженной матрицы. Значением по умолчанию является true. Основанный на DFS алгоритм вычисляет связанные компоненты. Временной сложностью является O(N+E), где N и E количество узлов и ребер соответственно.
[ указывает, найти ли слабо соединенные компоненты или строго соединенные компоненты. Слабо связанный компонент является максимальной группой узлов, которые взаимно достижимы путем нарушения направлений ребра. Установите S, C]
= conncomp(BGObj, ...'Weak', WeakValue,
...)WeakValue к true найти слабо соединенные компоненты. Значением по умолчанию является false, который находит строго соединенные компоненты. Состояние этого параметра не оказывает влияния на неориентированных графов, потому что слабо и строго связанные компоненты то же самое в неориентированных графах. Временной сложностью является O(N+E), где N и E количество узлов и ребер соответственно.
По определению один узел может быть строго связанным компонентом.
Направленный граф без петель (DAG) не может иметь никаких строго связанных компонентов, больше, чем один.
[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). Руководство пользователя библиотеки графика повышения и справочник, (верхний Сэддл-Ривер, образование НДЖ:ПИРСОНА).
allshortestpaths | biograph | graphconncomp | isdag | isomorphism | isspantree | maxflow | minspantree | shortestpath | topoorder | traverse