Найдите сильно или слабо связанные компоненты в объекте биографика
[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] Sedgewick, R., (2002). Алгоритмы в C++, Алгоритмы графика части 5 (Эддисон-Уэсли).
[3] Siek, J.G., Lee, L-Q, and Lumsdaine, A. (2002). Руководство пользователя библиотеки График (Upper Saddle River, NJ: Pearson Education).
allshortestpaths | biograph | graphconncomp | isdag | isomorphism | isspantree | maxflow | minspantree | shortestpath | topoorder | traverse