Найдите строго или слабо соединенные компоненты в биообъекте диаграмм
[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 являются количеством узлов и ребер соответственно.
[S, C] = conncomp(BGObj, ...'PropertyName', 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