Публикация Школы траблшутеров

Алгоритм Косарайю: как найти круги, в которых все ждут друг друга

Время чтения: 6 мин 40 сек
08 ноября 2026 Просмотров: 15

После двух-трёх подписей возникает правка, и документ возвращается на «первый круг ада», а подписывающие делятся на коалиции и неделями ждут контрподписей друг друга. Основатель «Школы траблшутеров», экс-директор Альфа-Банка по процессам, Олег Брагинский рисует алгоритм Косарайю, который находит такие круги, в трёх нотациях.

Алгоритм Косарайю: как найти круги, в которых все ждут друг друга

Рис. 1. Алгоритм Косарайю: два обхода в глубину и развёрнутые связи

Согласование документа в корпоративных джунглях бывает бесконечным. После двух-трёх подписей возникает правка, после чего обязателен возврат на «первый круг ада».

Возникают коалиции подписывающих не глядя и не подписывающих, пока не увидят контрподписи. Бумага кружит, и каждый честно ждёт остальных.

Короткий ответ: алгоритм Косарайю находит группы объектов, замкнутых друг на друга, – из любого объекта группы можно дойти до любого другого и вернуться.

Рисовать круги руководителю удобнее всего графом с выделенными группами: круги видны сразу, а всё остальное выстраивается в прямую линию.

Что такое группа взаимных связей?

Сильно связная компонента – способ выделить группу, где каждый объект достижим из каждого. Для документа это круг согласования: правка в любой точке возвращает его ко всем.

Как работает алгоритм Косарайю?

Алгоритм Косарайю – способ найти все сильно связные компоненты за два обхода в глубину. Первый обход следует прямым связям и записывает, в каком порядке объекты завершены. Затем все связи разворачивают.

Второй обход идёт по развёрнутым связям с последнего завершённого объекта. Всё, до чего он дотянулся и что ещё без группы, – одна группа. По ГОСТ 19.701 – два действия и цикл с ромбом «Объект уже в группе?».

Алгоритм предложил Самбасива Рао Косарайю в 1978 году, но не опубликовал. Независимо его открыл и в 1981 году опубликовал Миха Шарир.

Как это выглядит у «Кедра»?

Сервисная компания «Кедр» согласует договор подряда: восемь участников от инициатора до архива. Закупки после правки возвращают документ юристам, а безопасность и директор ждут контрподписи друг друга.

image html

Рис. 2. Восемь участников согласования и два круга ожиданий

Первый обход начинается с инициатора, завершает архив первым, а инициатора – последним. Второй обход по развёрнутым связям находит пять групп: два круга и три одиночных участника, у которых нет возвратов.

image html

Рис. 3. Три шага и пять найденных групп

Сжатый граф – способ нарисовать каждую группу одним блоком. У «Кедра» он превращается в прямую цепочку из пяти блоков, и каждый круг согласуют как одно целое: одним совещанием, а не по кругу подписей.

image html

Рис. 4. Сжатый граф договора: пять блоков в одну линию

Матрица связей – способ записать связи таблицей, где строки и столбцы – одни и те же участники. Если упорядочить участников по группам, круги видны как закрашенные блоки у диагонали, а возвраты – точки над ней.

image html

Рис. 5. Матрица связей договора, упорядоченная по группам

Как найти денежные круги?

Мошенники устроили в местах отбывания наказания колл-центр и обманывали доверчивых граждан. Деньги гоняли по счетам со скоростью света, но в конечном итоге решили, что сотни транзакций будет достаточно, чтобы замести следы.

Мы же были готовы на 50 тысяч транзакций, поэтому смогли отследить почти всех кардеров.

Переводы – это граф, где счета – объекты, а платежи – связи. Деньги, которые ходят по кругу, образуют сильно связную компоненту, и алгоритм Косарайю выделяет её в общем потоке.

Почему группу нельзя менять по частям?

В ИТ-ландшафте иногда намечается выкорчёвывание «старого пня». Речь почти всегда идёт об этакой «священной корове», которую долго боятся трогать, так как «на неё завязано всё».

Одна биржа созрела к подобному решению, пригласила меня и пришла в ужас, когда я сказал, что увольнять придётся не одно подразделение, а всю группу смежных команд.

Подразделения, замкнутые друг на друга, – тоже сильно связная компонента. Убрать одно нельзя: остальные продолжат ждать от него результатов, поэтому меняют всю группу.

Как выдаёт себя круговая порука?

При групповом мошенничестве рука руку моет, поэтому трудно найти крайнего. Приходится выстраивать таймлайн событий по широкому списку людей в обширной группе систем.

Рано или поздно кто-нибудь что-нибудь делает плохо, не вовремя, с запозданием. Бумага всё стерпит, но полная схема множественных связей выдаёт хитрецов с головой.

Сколько стоит расчёт?

Алгоритм Косарайю проходит каждый объект и каждую связь дважды: для 50’000 транзакций – доли секунды. Дороже всего обходится сбор полной схемы связей, а не вычисления.

Когда уместен алгоритм Косарайю?

Там, где связи могут замыкаться в круг: согласования, денежные потоки, зависимости систем и команд. Алгоритм показывает, что придётся менять вместе.

Какую связь в круге разорвать, решает руководитель, а не алгоритм.

В следующей статье сборника – алгоритм Дейкстры: как найти самый короткий или самый дешёвый путь между двумя точками сети.

Какими нотациями рисовать круги?

ГОСТ 19.701 передаёт порядок двух обходов, его ценят авторы методик аудита.

Граф с выделенными группами показывает участников и круги. Его любят руководители: видно, кто кого ждёт и где согласование ходит по кругу.

Матрица связей компактна и не путается, когда участников сотни. Ею пользуются аналитики и ИИ: блоки и точки над диагональю читаются без потерь.

Какая нотация лучше?

Лучшая нотация для кругов ожиданий – граф с выделенными группами: 20 баллов против 19 у матрицы и 16 у ГОСТ. Руководитель за минуту видит, где документ ходит по кругу. Вес вопроса о руководителе удвоен: сборник написан для него.

image html

Рис. 6. Оценка трёх нотаций: 16, 20 и 19 баллов

Матрица отстала на балл и лучше на сотнях участников, где граф превращается в паутину. ГОСТ остаётся для методик аудита и расследований.

Что сделать руководителю?

Хватит четырёх шагов:

  1. Нарисуйте полную схему связей: кто кому передаёт документ, деньги или результат.
  2. Найдите алгоритмом Косарайю группы, замкнутые друг на друга.
  3. Каждый круг согласуйте или меняйте как одно целое.
  4. Разрывайте лишние связи внутри кругов: контрподписи и двойные проверки.

Что запомнить?

  • группа взаимных связей – участники, которые ждут друг друга по кругу
  • алгоритм Косарайю находит такие группы двумя обходами в глубину
  • сжатый граф превращает круги в блоки прямой цепочки
  • замкнутую группу меняют целиком, а не по частям
  • круги ожиданий лучше всего рисовать графом с выделенными группами.