Найдите строго или слабо соединенные компоненты в биообъекте диаграмм
[
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