Найти сильно или слабо связанные компоненты в объекте-биографе
[S, C] = conncomp(BGObj)
[S, C] = conncomp(BGObj, ...'Directed', DirectedValue, ...)
[S, C] = conncomp(BGObj, ...'Weak', WeakValue, ...)
BGObj | Объект-биограф, созданный biograph (конструктор объекта). |
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] Тарджан, Р. Э., (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).
allshortestpaths | biograph | graphconncomp | isdag | isomorphism | isspantree | maxflow | minspantree | shortestpath | topoorder | traverse