Обходы и структура графа: BFS, DFS, компоненты, топологическая сортировка, сильные компоненты — авторское изложение

ru · official · sha256:2f329a5f0f589a74bead2905caf2308a228233e54b63a4e4fe0b4fecbe36591b

§1. Граф, обход, цвета вершин и порядок выхода Граф задаётся конечным множеством вершин и множеством рёбер. Ребро ориентированного графа есть упорядоченная пара, неориентированного — неупорядоченная. Список смежности вершины перечисляет вершины, в которые из неё ведёт ребро; изложение всюду предполагает именно это представление, потому что от него зависят оценки. Обход посещает каждую вершину не более одного раза. Признак посещения обязателен: без него обход на графе с циклом не завершается, и это не оптимизация, а условие завершения. Три цвета вершины: белая — не посещённая, серая — посещённая, но её обработка не завершена, чёрная — обработка завершена. Трёхцветная разметка нужна не всем описаниям, но именно она позволяет обнаружить цикл в ориентированном графе: ребро в СЕРУЮ вершину есть обратное ребро, и оно равносильно наличию цикла. Порядок выхода — последовательность вершин в порядке их почернения при обходе в глубину. Обратный порядок выхода на ациклическом ориентированном графе есть топологический порядок; на этом стоит §6. Топологический порядок ориентированного графа — такая нумерация вершин, при которой всякое ребро ведёт от меньшего номера к большему. Он существует тогда и только тогда, когда граф ациклический; отсутствие порядка есть свидетельство цикла, а не сбой описания. Компонента связности неориентированного графа — класс эквивалентности отношения достижимости. Сильно связная компонента ориентированного графа — класс эквивалентности отношения взаимной достижимости: u и v в одной компоненте, когда есть путь из u в v и путь из v в u. Граф конденсации — граф, вершинами которого служат сильно связные компоненты исходного, а рёбрами — рёбра между разными компонентами. Он всегда ациклический; на этом свойстве стоят оба описания сильных компонент.

Ссылаются нормы: AnswersHere, f-04013f5fc51cf0024d2dd1c2, f-07073f3998defd5e63f59350, f-0d8349d6744320dd2fbe58ee, f-125dcb76912602463153f6b8, f-18ce22a6bac26c3350f4a5d0, f-1b089408702095685a28fc52, f-294c491800f71a73f086edd0, f-2d046175afebe4e46bb7d1f8, f-3201222c9bc1fc072a22ce11, f-336d0993091c25ad6694d3f0, f-34147830e9476b5f349427be, f-4938fa6ad4279d3335e2dec3, f-4c7a295a8d2035c59f3a9c46, f-512bb5e73b160c1ae30a6a0b, f-57aa14b7df9bb45aa6e575d5, f-57b84adef9523912275804cd, f-5a89bb40bbbe25b00a28e13e, f-5d7a1307c97c6cc4cd3bf50e, f-630416698a5f6f9156ff6be2, f-689805e41dcf099025305ade, f-69f86138460b704821842bd8, f-6e32785adadafba2f0fcfb98, f-7cf7168a15fb1e3690b4bc91, f-89fe11ba98b5c6a30568650b, f-8fa0cc7a3cdb80b974049f46, f-94bb22ae8e089774cd5d6255, f-973ac47628903ec15890eb3b, f-9cf0d2a0a4759c516797aa43, f-a187c8c5b2ddd67dfc693558, f-a31c2e5cf630bbac1b197558, f-ab74cde8f5c4d0914d8a2aa6, f-b24727a46c1808803852f51d, f-b534c80713e5ad05cd9a81bc, f-baa3117a9963c82cce910306, f-bc3f8a8809b4b0d7c7375d4e, f-be1160ad6ff003ee5e250588, f-bf7c0df520264cadd12ffee8, f-c798aa16a93178ddc2e95b3f, f-c852a330fd162c8fa4c80a2d, f-d228f52088d69c6cd1973746, f-d5835d7de9905dd740c473cf, f-da2340e2c4be161165ed1bb8, f-e099a292d528083195a0dec2, f-e52c557942b060aea732e336, f-ea6696cc2ad3ab807ccf6144, f-ed53843e4ffc51646d141957, f-f3a5fe571f830776a730bed0, f-fa95fdef222b3486258caf43, f-ff12a910bf89f8763490d1de

ru · official · sha256:f5880c56ca5486c51f303c58f4b9ffe251a964a98b5a9c84a5e18eec2ebba6e3

§2. Обход в ширину Задача: по графу и начальной вершине посетить все достижимые вершины, получив для каждой длину кратчайшего пути в рёбрах. Вариант — с очередью, слоями возрастающего расстояния. Начальная вершина помечается посещённой с расстоянием ноль и кладётся в очередь. Пока очередь непуста, из её начала берётся вершина, и все её непосещённые соседи помечаются посещёнными с расстоянием на единицу большим и кладутся в конец очереди. Пометка соседа выполняется В МОМЕНТ ПОМЕЩЕНИЯ в очередь, а не в момент извлечения. Это существенно: пометка при извлечении допускает повторное помещение одной вершины и разрушает как оценку, так и правильность расстояний. Инвариант: очередь содержит вершины не более чем двух соседних расстояний, причём меньшее стоит ближе к началу. Отсюда и следует, что расстояния присваиваются в порядке возрастания и каждое верно. Мера убывания — число непосещённых вершин; на каждом помещении в очередь оно строго убывает, а извлечений не больше помещений. Оценка: время порядка числа вершин плюс числа рёбер, память порядка числа вершин. Обход в ширину даёт кратчайшие пути только в графе БЕЗ весов; при весах он неверен, и это ограничение названо прямо.

Ссылаются нормы: f-02fa18eabb7f0256f2af5371, f-03cc482a2a51e98761f40141, f-0820244a9d0bdbe7d8180750, f-0ac5c8632c40df5c38bbf2a3, f-0d6bc8583910f733e6d04a3a, f-0d7e48ced51937371608dcf0, f-0f430740c7fcfcba10914002, f-11e3f8d6894ccc53df71eff5, f-122aea925fbf5cddc7c36d23, f-12c564d7891d76610fc60ee0, f-1b6fb95a479056dbaf7ca6f7, f-1ba00aaf76f71b73aff8db40, f-1cca29aeac4db69a669b6677, f-1dca281ca80b176b8beb34e5, f-1e96a9483b9e3ada548ebeb2, f-1f95bf112a02a0f9d949a99c, f-218a888b5cf77d18aebe802b, f-23f50815244f18dce5034e58, f-253472a4dc447bc7a92e0842, f-27152ee0028650b74c8c6070, f-299bbdad2ff170b4d17de76d, f-2d478e87265bbdc1343e49e7, f-2e3f5e0c32686ea64ccf8805, f-30f1468e616327ca7a2c5590, f-318a9fc5d2fd779ad6fd4231, f-34920421eda490be184a9e9a, f-36b81f050060a688a34d131f, f-3961eef774e3a9f7afc1705b, f-3b1386844ec067fcdab7237e, f-3b5adc8ec6e4255467424145, f-3f679abaf756b3fb9d5d9b0f, f-429d64c52b0993714175031b, f-46f12b82c431842084cfc66b, f-4993c8339ba1c9ba224dfa6e, f-4c43eaadfbae4c7fd8aa21aa, f-4dc790feae40ccae1f7926e2, f-4e2ad2721896123d367679bb, f-4fd1e2ca46841a3a3ed8c18c, f-502ae70006d1e47bca309db9, f-5383d82dc7cd85dc1f463bb2, f-55d30a969d81d70b6231bb1a, f-60efec50c3197d57cad38635, f-6340cad80763deb0c5dc2f0d, f-6c95e213cac059fbe573ca91, f-6f34bf89402c6df9cf3eb9de, f-73aed79b880a2fe32a4c974d, f-741ec3813d7a63976d34b265, f-7c35a27eb73116161552dcc3, f-7c7a6b8383a4dc6dbf0f3242, f-8330b144b954607f400edbe4, f-85b92f1c960c00e34fa220aa, f-8826d5604e1d64a2478047ee, f-8ab330bf6fecebf51e151836, f-8ce58d4a44337db6e8e9535d, f-8d29be4216deaad35c4c3c22, f-92f28cf124d2d73b8e5cf070, f-944072ecc911ae8b18c6a09d, f-9560798b905dee2f8c5fee76, f-993adddfa2454bb74c7750ea, f-9dfe29ef2baed7d3796d2c1e, f-9e80f166c45e89cb64e76457, f-9ec8532ad92a83e2c1a6966b, f-a2aab814a1d71c10cad934d8, f-a6c61c0dbd66eca211552b4d, f-a816c7c639bd9a70cffa4f70, f-ace295507f0fb44a5daa9750, f-b0981de784f45c82f6b4b719, f-c0a9b032132711a806417aeb, f-c888c36601911b06c3e6cb72, f-cf99124aba1a237392e339e7, f-d0703d3218175192d00add17, f-d119295976b4c316c74a6be8, f-d1f76efcba47a252c621e668, f-d67e0451422501a3610c6e96, f-dea00bf0dedd7e7660a21d53, f-e06de64e753427635a4c2108, f-e2031f83b437b0dc6db94d1e, f-e8fa7d4e71fffaf7a758cfc9, f-eb5d1a8aa9201f5ba9d010a7, f-ec72aced54242223c757f9e9, f-f6ba02a0bb1a69fa2c0ba0a5, f-f78b33e3b840fadfb7c48544, f-fd5fa2ca1f70dc684285c141

ru · official · sha256:2d074c44b97f4201ef1682ae3fa6aa4b6ecbd51900876ac05d242c7576046c07

§3. Обход в глубину Задача: по графу и начальной вершине посетить все достижимые вершины, получив порядок входа и порядок выхода. Вариант — рекурсивный, с трёхцветной разметкой. Вершина при входе становится серой, затем рекурсивно обрабатываются её непосещённые соседи, затем вершина становится чёрной и дописывается в порядок выхода. Классификация рёбер: ребро в белую вершину — древесное, в серую — обратное, в чёрную — прямое либо перекрёстное. Обратное ребро есть в точности признак цикла в ориентированном графе; в неориентированном графе ребром назад в родителя пренебрегают, и это исключение обязано быть названо, иначе всякий неориентированный граф с ребром объявляется циклическим. Инвариант: множество серых вершин в любой момент есть путь от начальной вершины к текущей. Отсюда и следует, что ребро в серую вершину замыкает цикл. Мера убывания — число белых вершин: при каждом рекурсивном вызове оно строго убывает, потому что вершина красится до вызовов. Крайние случаи: изолированная начальная вершина — рекурсия не углубляется; глубина рекурсии в худшем случае равна числу вершин, и итеративный вариант со стеком снимает это ограничение, оставаясь другим описанием.

Ссылаются нормы: f-0236ca6e0a789ba63ea571c8, f-04e88019515efb4e908f3a12, f-155fbd6e1360dcac2149663d, f-17afb3cf5afd4dc60eafd76f, f-18d041137d5e63de5b30a1b7, f-19d39855397ccbd409c2054d, f-1d23f039633ba89252bfc56b, f-29b0cfb6f824e10feb73c9cf, f-2a094a1635c10c276199c70d, f-2eee2e6e7e6e35baa9d39555, f-2ef84abca13579e36cd38976, f-333f5ee88895bb3e1a610e91, f-356d4907808a7977d39de440, f-39b3e31cdefc5bdbf55b03f2, f-3b4a27738374f1504557d9eb, f-4301bdee12a0e312b97decfd, f-4cde3143ef735a1a73a6963b, f-4da2bb4c9813093d51d65c72, f-53f67f73397e974acf76eb4b, f-59bf32a3838d7f2fbe00245a, f-5a183be2099a587fda1f2981, f-5af706ef3ba6a5f031970b9c, f-5f7193224858ef15dfc6ac33, f-64f65fb57feacfee90e982b9, f-69418cf5c7f5817b43fb7478, f-6af58c131c5d347945383d50, f-6f836375f0c8c84427228486, f-72db7f6b11dc81c6bfe2f7a4, f-7413718305dab6314f5d4b4f, f-7550558ba2e192e487ef8a23, f-776eb1e9c9083651cf36eff3, f-7e4a38dc0873b57f00314b5c, f-84697116d6ef1216cd469d8b, f-854d721daaac16d20e96cca0, f-85921fe49142452d015e9882, f-8a3245a0ae91c99f4ccceaae, f-8dc1d0d95ff1a83d11e39488, f-8e86115d1019137645ec719f, f-8f629b4291ea7a42a161f1af, f-8f9a019ab4c5d04f67f4ec69, f-91797eeda770e0e838b5ee52, f-987f2e9d0a0ac53af3917da4, f-99c4d6d858255f99aa545fac, f-9b82dfe81902ba47d6a821d2, f-9d64b8adf6b038c5f65240ad, f-9d6c6c4b3cc1fe2ef1677411, f-a1576a66b153c799b2220464, f-a3c2c192930896321b9c34e5, f-a433884f66b69d775347e629, f-a4b2abbc5ffb0d3fa1dc2fe5, f-a55fe7a5a86fb411d09a8eef, f-a5da11c4b09858743da1a369, f-a6817a52ec12c306cd991973, f-a7ae4141ee5758927a613b5d, f-a81d010742a61b718796ece3, f-ae4caf9444fc24d86839743a, f-b19a59836acf3f0da269d0eb, f-b696cb9530f8f4c8fb8c34be, f-b7cc5a862476f5f37b9ba00f, f-b8f980c5c46daca7bd20ee7f, f-bc1c3b5737f1fcc089122c82, f-bc99a8689b03a2132f2a64cd, f-bdb4a56a082848557cb3efb7, f-bdd4266c5ddc34b640fc4cc4, f-c1d42cf0d2ee090ff1160cdd, f-c2d19fc7a8f1539f3349a8dc, f-c2e83271e62d942e76a6ad01, f-c3b47146db14078834df091d, f-c88d07007f7bd90b62668bf5, f-c91314f25dd0de0a6b28c53f, f-cb8f8fd390437f3bb832153a, f-ce17ed14819271d8e00cd307, f-ce6e5972758471459594608d, f-ceaa92e7e61224e79bf463b9, f-d02cdd1177456e76b9441a73, f-d12e20cdb3b6e33ef09db287, f-d4e4414bb71cfd834f9983f8, f-d4e6787addb709416d8fafc6, f-da41e332d9581d2afa2ffd18, f-db43b593485e4a2fd501c618, f-dc6fb288750440286cc12d91, f-ddaed6b34f19154426b3f7bd, f-e339f7efbd28275629eb4306, f-e5347c679bfaea1d085009e7, f-ea0ae81f94be880bb9ccfc10, f-ed0d08d3362678d29a7ff82e, f-efe6f9d99775dd8c805d345b, f-f0b80ab8b9a20abf5ca43502, f-f59a515b28bfa77dcd50d9ff, f-fba79b282247b1db6b09fc0b, f-fcf8643affa450295d4c74c7, f-fd367460d165789fe415b30d, f-fe89b7318382a03dd7a57ad1, f-ffb52404c856c38148f7e1df

ru · official · sha256:c525f159190be0ce1d83e1c2ed5b6a852ce9d3c2bfc6333a013336373dab27c7

§4. Выделение компонент связности Задача: по неориентированному графу разбить вершины на компоненты связности. Вариант — внешний перебор вершин с запуском обхода из каждой непосещённой. Заводится счётчик компонент. Вершины перебираются по порядку; встретив непосещённую, описание увеличивает счётчик и запускает из неё обход, приписывая всем достигнутым вершинам номер текущей компоненты. Какой именно обход запускается — в ширину или в глубину, — на результат не влияет: обе достигают в точности множества достижимых вершин. Это утверждение существенно, потому что оно и позволяет называть описание независимым от выбора обхода. Инвариант: перед обработкой очередной вершины все ранее посещённые вершины получили верные номера компонент, и номера соответствуют классам эквивалентности достижимости на просмотренной части. Оценка: суммарно один обход по всему графу, то есть время порядка числа вершин плюс числа рёбер независимо от числа компонент. Крайние случаи: граф без рёбер — каждая вершина есть отдельная компонента; пустой граф — компонент ноль.

Ссылаются нормы: f-01046beb8b68dd665f1f4490, f-03c04d401e55889a8c2fdc95, f-08ff2fe05bda44b8440e8745, f-0a229c738a87b0ec366e9e3f, f-100071a9ec9368cdbfc4357a, f-19909916268d079ba0fc1d8c, f-1b360adc2b0b34cdbfc5aa04, f-1cb4f78fe5bb468ca6c0aff9, f-1d91acea0cdbf1a3515abd21, f-20d97a5db9995bfbf1d789d9, f-265eee064babc5da06c38a39, f-27192d09f8a84b89c05efbb8, f-29c09e2a6b4bb734b698bacc, f-2c878214093d66fb0030480d, f-2d4b0a4cb289e24fb7ac589b, f-2fd3a443ac560294f3eb8fa4, f-3004fd71927b097d44eb32d2, f-302cb485739e5dcfb8a07c62, f-329200f7182161edc159eff4, f-36e6c9863e5e4ac3ae85b4e0, f-3769fba506eb04b5133f7fc1, f-390043a1aecdc9bf2dc0e4aa, f-3c3f2cfb79a76cff21502bf7, f-3e3378520a59f305b8131770, f-4082dbee346e27ffae945060, f-42f2ad6ec4782fe476200c0e, f-49c37842098527cd882891a2, f-5185c9d81f9be779221c323e, f-55458ec1cf1e593b5d041f67, f-55dc638672be905bb32362e3, f-5f8669ad591450e22d9f5c48, f-61a0517745d7ba2d6399f599, f-62e3de73ebc7fe806110832d, f-6a61d88d4d3221b219f4d49c, f-77c9208a9051bdf14293eca3, f-7a42b11f55a3b7f3b3b70f52, f-7c1ea1403abe4d22a90eb2e7, f-7e00ee29f62746a19e5c7c35, f-7e2c26ca82a8e56bea15a606, f-7eafa7d0c9fb3fd90f94b29b, f-815c26545e469cd470413c35, f-8310412c5e5a71900c875abd, f-834fff9289ba7dbfb94acac9, f-84c24fea118d7a3d6dc58a5f, f-856256535458abffeaf38b57, f-8f0df561a487ba159871a611, f-98e3f2678bcc8dc6420c1aed, f-9aa601eaa7a8badbc35e0ca8, f-9c94e252ee0d29d1d071360e, f-9cd5d17b731566bcf5b76122, f-a18c49b84e945e252e82bc50, f-a1f92e9df41b277910eb1d8b, f-a5280e5427f067916b97128d, f-a741f72b446f0d9986ba909f, f-a8fcbd09ce8c82946d686769, f-ad565f38a9ae6f6cab9b06fd, f-b242f164cd69264a033cbe07, f-b314a2b55ba09baaed907c9b, f-b90f8bfaede0fadf4316233f, f-bcd05ca8ff6df1b5e42dc873, f-be36dc2e594b517f764d104b, f-be594ac3ab9726196a610f40, f-c379d56da9fd3b13b38a6dc5, f-c5365c58e178ec6fd8473a42, f-c8330f4fd0dd3c3b9cb138eb, f-c969ba7be0004367c21295d4, f-cbf299bf1312ca3b04581f2d, f-cca9bf3fa716546adc2079f9, f-ce710abbd3526efefc2dc499, f-dae44328d44bc0abb80401f1, f-de330cd5d49822d68dadf91a, f-e407145f599b2c3eadfc331c, f-ef671d8f6a0e8807ad74f408, f-f2aee1add9b88e3dee93577b, f-f2c03b227d1cb007508b2424, f-f2cc0eb671b7a755796a2f61, f-f37fefac83aee3686fa53f6c, f-f702ca2a56ff0d2c837de113, f-fcc996ed424ff3a96338a86b

ru · official · sha256:fc90d1c59878300db278291dd7f052d45f303d5323f7fc62eb31b1be0d510c20

§5. Топологическая сортировка методом Кана Задача: по ориентированному графу получить топологический порядок либо установить наличие цикла. Вариант — со счётчиками входящих степеней и очередью вершин нулевой степени. Для каждой вершины считается число входящих рёбер. Вершины с нулевой входящей степенью кладутся в очередь. Пока очередь непуста, вершина извлекается и дописывается в результат, а входящие степени всех её соседей уменьшаются на единицу; вершина, чья степень стала нулевой, кладётся в очередь. По завершении сравнивается длина результата с числом вершин. Меньшая длина означает, что оставшиеся вершины лежат на циклах; это НЕ ошибка описания, а его ответ, и он информативен: остаток и есть множество вершин, достижимых из цикла и достигающих его. Инвариант: результат есть топологический порядок уже извлечённых вершин, а входящая степень каждой оставшейся вершины равна числу её предшественников среди неизвлечённых. Мера убывания — число неизвлечённых вершин. Метод Кана даёт естественный контроль цикличности и позволяет выбирать среди вершин нулевой степени по дополнительному правилу — например, наименьшую по номеру, что даёт лексикографически наименьший топологический порядок. Обход в глубину такой свободы не даёт, и это существенное различие двух вариантов.

Ссылаются нормы: f-00cded03e5a0c83385085026, f-03a05ab6b0d02736d6f02398, f-0416b76d7a625438702fc887, f-05e69b7f6856772d6585bd0d, f-073aab9e3a0493e83cbf499e, f-087a70bdc3e6ddf5a7688418, f-0a9437680a277e6ce67ae366, f-0b6f026bfee46b0e6ff21100, f-0d08cd7ee92a7ccd8bdda8b6, f-0e3f14ec739d79ce5223eeb8, f-0f3dd48623791219570fdd67, f-0ff7bbf68d35b9ef0baa769c, f-1096ac09161db9ef5269b533, f-1619c75b0d86e68b19a882a4, f-18dc770eafb5f53b1d500f1a, f-1f1275a0e3a494beaa28a83c, f-22e3c2c7e84918f7007efe49, f-2401dbaf96e8ec63d84bc78e, f-280588e050ec27e7c9a5b7db, f-2c4581c798978ddbd0f2a082, f-2f8d890ab302e3272ce0b631, f-3198b4b55e17fd7311cdaa0a, f-32e44f459da7560de5dc12b9, f-3368e960ac3dd6a32d270385, f-3681b4ef151b7a7d9d50cc61, f-3a1d1c12da1ad9bd85235495, f-3f1ae14991c376e7285f4bd3, f-411f5bfbdef5ec5415a3cf74, f-41ec2783cb90c17bea81ed62, f-431a0975d186e8c1a6c7da13, f-483197c860018abfb39ad6c1, f-4bcb0a5292ec5ff499c9a66e, f-4c6d90f46f1333c64eaf2176, f-4e74dac0543adfea9e0bcd26, f-4fb9a578c65d905284ab614b, f-508f09f3fa7090e20f909683, f-55f02716dc37da73695bdf48, f-596c922daf50533ace4f8e4e, f-59cb91c2112cd00793aba824, f-5a3bc41f9b5742406ba009bc, f-6afe387165c98780473a2abc, f-6b8b7ee0f1885fbd611ab3ef, f-6cee69facbc7111f2951e2be, f-6e553ec87265ee2ec0930edb, f-6eb01deebc04ff019009247e, f-6f43f2d594b8a370a533fe7d, f-78a84c064ab6f573e035546c, f-7ad55a1497a2fad47e8f8923, f-7afec5a8bf27482fd25cf5f2, f-7cf1498a44190585622c56c7, f-7e3f09d6facb4641297d1ced, f-7e7631557e8475ae6c96b4de, f-8088f0d21b8b57c31abc13e6, f-833f5c3c1e9192f0ba02b4f1, f-854919a75541f2d66a5e7175, f-87e37aa211b0d4efde8c41b4, f-8f41c040ef27fd4e92732a26, f-8f82e74521a67638dd9318cb, f-936805206783ec978a06c28a, f-95a08ff64617812b0ba8c8df, f-991c72da6a1bc14699ab90a6, f-9ade38efc70606a996c773fb, f-9c5731079aa210de997e80c5, f-a41ad6b07ea7f821a6d8815e, f-a54674b9520b6acde1ec7425, f-a9cee9fcdbed38f0725ed0a8, f-ab50dce50e6b24d308a2adda, f-ab8e681cc76ea7ac569784eb, f-b17b390e3fddbc36ca565720, f-b837060b5853fa505ac0c2b5, f-baf058533ae5d5dcb48ccb88, f-bd5092e58e2cfc7b40fb2ddd, f-c0c6b18088756f329ebb78c5, f-c2af2633c7adb4f1541e6292, f-c59d0dcdb36112ab11e9f94f, f-c93ef7a9a5d0508862d14821, f-cabd6e0c883fa2e8202f68d8, f-ce55b88edc592d1791c6ea2b, f-cff172ec25efa779c9d53c3d, f-d47b459dbd3fb06e17293f8c, f-d7392e83c08d346d58ed3811, f-dcc09f43f02c320f0cb856f5, f-e07354fc2db1e7c662b3f04d, f-e2ed6803aceb8abb70f32570, f-e4c575259d3821b753cf38cd, f-e543942e2767978c34299b4d, f-e5597ee003f18180c71e4489, f-e57d7a704243541d65b38479, f-e84ab82ceaca26a3e7c4ae14, f-f4e1c470e81ba2b53240c545, f-f89547c6cc8391cb90bb5f56, f-f91562b349ad77c42e220546, f-f9d316151470cf549fcc418b

ru · official · sha256:7511989e071d8f939bc6d28520c4e0ab79b4e0532ddc5f229762e8fa7f1198c2

§6. Топологическая сортировка через обход в глубину Задача та же. Вариант — обход в глубину со всех вершин, результат есть ОБРАЩЁННЫЙ порядок выхода. Обход в глубину запускается из каждой ещё белой вершины. Вершина дописывается в список при почернении. По завершении список обращается, и обращённый список есть топологический порядок. Основание: если есть ребро из u в v, то v чернеет раньше u. При белой v это верно потому, что v обрабатывается внутри обработки u; при чёрной v — потому, что она уже почернела. Случай серой v означает цикл, и тогда топологического порядка не существует вовсе. Отсюда следует, что описание обязано ПРОВЕРЯТЬ наличие обратного ребра. Вариант без проверки выдаёт на циклическом графе последовательность, топологическим порядком не являющуюся, и молчит об этом; такое умолчание есть дефект изложения, а не упрощение. Оценка та же, что у метода Кана: время порядка числа вершин плюс числа рёбер. Различие вариантов — не в стоимости, а в свойствах: Кан даёт контроль порядка выбора, обход в глубину даёт порядок выхода, полезный сам по себе.

Ссылаются нормы: f-030cbb6d403c2aa98e098131, f-0c587e450c0f367d92bb9bbb, f-0f48b4054181bd85ef2cac2a, f-0f66b71809d5e13251b6eeb5, f-10cb6d3e2fb18210e7c908b9, f-115ebb3245202e7d5c8f748f, f-12159569f10b6f3fb2d66ce6, f-1241d585a7611f226516a99d, f-13a9c0bcdfe990a581208e35, f-192fd082c46bad097b501069, f-25df93d728a82bec2a98eb8c, f-262e8d00826f0b1f6d5001ab, f-29c87cf0a6a1e7016a34c136, f-2bb5ddf96da3ef236f209004, f-2bdc69a59e66a985744fa336, f-2d238eb6d318ddb2b0203a6d, f-2d883571ab30c099e622e612, f-2f62f2e990f9632ded07a53e, f-2f80240e92318a80af3ae864, f-2f925e1d457e04f1396b77a7, f-3411f2f371d9ecc23ce0ea72, f-38175045f59f7d843fc9795a, f-3b3b223aa869bc8bcff9acca, f-4273f6f2df778296595a549a, f-4effc34a1366f57ab3e45b3e, f-50a49235f2581039d43cddb2, f-5755e570e28a030426415a07, f-5ea893b780cc5bd8ef497b61, f-66099b801b09886e68762fb9, f-66debe1fcffb983b5832358a, f-737d1b3518c5ccbc8627fcfa, f-75be73a4f83072ad1ee0771a, f-80349af186c889de9f78c16c, f-81188a4e8c006d56c1c7cf98, f-8171888d59945534bea1d642, f-887e705106c02aa82a5b4702, f-8ca1bc4d8a2430aff45afdbe, f-8f0837e240d61d759c2cc00a, f-95a9183c2e855a78889b8af9, f-98018a30e0a535bcb33d0073, f-9c146747e55f6037ddac2f2c, f-9c67a786806adec46be9ec21, f-a44f13f335546aca1a27adcb, f-a4c569ad6f935330fab3e926, f-ace0ba5054cfe939ec674545, f-b127a2af96f914299261e60c, f-b38b711eba7d76d4678dbc08, f-b39a3e229582acdb5c6a3602, f-b4154d9207cd252ffb927f12, f-b55bac7f257acb564f1644ad, f-b5a855a33cce81ba78ea1bca, f-b5c0bda43a1bef4ea14884ed, f-b8aecd872816886f1a973a0b, f-ba8d3a7f0be77a998aba1aeb, f-bd1d3b78d5beb8698f53cd5a, f-bedd9755cc5a7405fd6a7e75, f-c3487d41fd9e2489294682b0, f-c51b84941a0c54309f7fd591, f-cd27f6bad1b15cc2a5027804, f-ce286210245fbd2591ae4b38, f-ce29f643ead23e02fcf96e65, f-cf026cb17dd69b8a233f3af3, f-d0b722ac2feaa73c7398d536, f-d22f46fe895e5c3fc625b2a3, f-d8ca017c4713ffe30eed505e, f-dbcb5570530947b83337ee44, f-dd8fd1804214b199b46ffc48, f-dfcd35e22b113cd4c44fb4db, f-e3b8e67bae2b0e0e5165ec33, f-e4992e752d1788940cb01dc8, f-ead3c54d7850d78a2a809e2f, f-ee9563077806841b8a48d256, f-f62f55fbbf3a615d4802ad12, f-f65a41bc4df1fe965d64b7e1, f-f83470e675f981da1f692bf7, f-f8ed8940b64ba13d4b858da9, f-f953adc2e5b94fe4f4c1f683, f-fd1b03f2a7a667349c723155, f-fe3a83c909502fa9775ccf88, f-fee1aa39218a7888aeb16b19

ru · official · sha256:bb1d0c47008b6ff0bd4d6619996999c9daf5c971defc51fa9b7d1f533fdbfe69

§7. Сильно связные компоненты алгоритмом Косарайю Задача: по ориентированному графу разбить вершины на сильно связные компоненты. Вариант — два обхода в глубину: первый по исходному графу для получения порядка выхода, второй по обращённому графу в обратном порядке выхода. Первый обход в глубину проходит все вершины и записывает порядок выхода. Затем строится обращённый граф, в котором направление каждого ребра изменено. Второй обход идёт по обращённому графу, начиная с вершин в порядке, ОБРАТНОМ порядку выхода первого обхода; каждое дерево второго обхода и есть сильно связная компонента. Основание корректности: вершина с наибольшим временем выхода лежит в компоненте-истоке графа конденсации, а обход по обращённому графу из неё не выходит за пределы её компоненты. Утверждение опирается на ацикличность графа конденсации и остаётся доказанным в источнике. Обращение графа — не удобство, а существо метода: без него второй обход выходил бы за пределы компоненты. Хранение обращённого графа есть дополнительная память порядка числа рёбер, и это цена варианта. Оценка: два обхода и одно построение обращённого графа, то есть время порядка числа вершин плюс числа рёбер и такая же дополнительная память.

Ссылаются нормы: f-01b804e1a8c92fa10f37ea1f, f-064bdd09282e282663ff51d3, f-06fdc29a490206162c7ca25f, f-071ca4d8401ee4a6b6d89802, f-08098609d68792e025b4049d, f-080f3e01f9077f09736b8ea0, f-0db495dee8f7c4980e54ccbb, f-0f7db9c71c86633b1c9f1932, f-0f933d7501768068e1067c5c, f-1305f87f8761ad5b164b6f96, f-1360ae922e416bba16527886, f-1e71bcebdfa6ca31f5b61d30, f-1ea561c51412c5cc41f656a7, f-20b918135275ca5b39471224, f-2226e2fb62edcd3776cff72f, f-2274ab432840df5fb3413a6d, f-23b5e5336573bf1c6785f72a, f-2407c9f4406f56012f62d9f7, f-2961092b0645eed581799d9f, f-2a3663427e7f51f20fd8239a, f-311a2cec7f16e2601d528b4c, f-32d22f236d4148e60298da2d, f-3b981908b7b61d99fcab457e, f-4558e041f1c0d25e5b975b03, f-4768451a654cee6a9e272fc3, f-480aae06dffe821c03cb9120, f-49f04c4b39900308ce6f9a86, f-4a103c1e787bcfdfe1a9b4b6, f-4d6d4c80abcc682ce54270fb, f-4e2d2a76c111cb6ffecf82ed, f-53581d70c6e15cba67ebc5f9, f-57fceca9771e1e49e9daf9b1, f-5a4eb2a79ce8b17ceaea8895, f-6577dc6392e1e464580b1ac3, f-65d5a00ad28625949d834efe, f-6d83b07c4f098abbcc0a0629, f-6dd3071d89074521db52ffd0, f-73063a2946ef3ba73b03afc4, f-737d474bf8f21047ef2d92e0, f-751a6b19c555c7c5ac12207d, f-7897772b7ced0f6c5299b80a, f-7a2600c2d47464b6a66f0b55, f-7c0c9dd4f7393dc4b927520e, f-810b6f7f640db6a9b7d31ef1, f-856c462c5e14bf086244fc2f, f-894bdd4d72bc4fad898ffbb3, f-89f65b99a490a1d2c94198ae, f-8a910044514e4fe845da5cf1, f-8ad0137b0e3134d70471dc95, f-8c9e7ba6faa6b2d5d6fe0c0f, f-8cc7776ca3d8ff2930de1963, f-8fb70a027a1713f89ebdc4d7, f-90916514773dfce107780b5b, f-9585ec0a60c6fa3fa92d331b, f-96e5e6fbc9462ae29e70b2d6, f-9f5d5834e51e4ef9aaf918ee, f-a35284134ca85fc93844ebb1, f-a4b02ade9d379ea422d2d85b, f-a80672f227ed59a2464cd0ce, f-ac391581281243f7165b010e, f-addaf6d6540170332c83a78a, f-aecd4e3421daccca31073c0d, f-afcbc4631a34016000fce19d, f-b330fcf3a84340142c673a7a, f-b53bba6b543b060c4ac018ef, f-b78ef2da32055e6d318d76ea, f-b9a78f82cb6611a5c6734c69, f-b9d350e4662c68a30084fbd0, f-bd3d8d1b4e866bf23805f453, f-c7e97b4420cd80dac6d0e4cd, f-cc30f146594a6cb5aa0f9b3f, f-cd5afa90eae8b5b41b039f63, f-d19b567c306197a372decba2, f-d2728bb2dde53ce2c9c118ff, f-d724ddd3db48efd614ab813d, f-d733953a354b0ea983d49e45, f-d796fdf1e969f4b0aa2cd3e9, f-d9ff09b2a5ee5d72e5b322d5, f-da41a43f4e86e7956438363b, f-daac7a102d42e53e79b1ad27, f-dbd18baa03d169afe9dbebaf, f-dc35a49b79ad67f93b313400, f-dc56d8e6a70653d56b99cbcc, f-dd8473013fe683cf68dc5bce, f-df9f8ff4daf5ea844c5706c2, f-e08e739829d968b2e2996376, f-e2965b8795ea6d4d7089d04a, f-e58212a08addc50432c35fad, f-e5a5f7a1fb66ad06c255ba07, f-e975d3a2f24560345c4a7784, f-f041ab25d51234ade7db7a4b, f-f1f9648351fe2d2b8761e88e, f-f3bf9aa6707278412d04952d, f-f55d4f4bbb3dc585fb720725, f-fdb1809ddd0679a130f2be09

ru · official · sha256:7bc98374f5d599541d43b71c8cf493aeeb4c382da3be5e0801f134f147a21fce

§8. Сильно связные компоненты алгоритмом Тарьяна Задача та же. Вариант — один обход в глубину со стеком вершин и двумя номерами у каждой вершины: временем входа и наименьшим достижимым временем входа. При входе в вершину ей присваивается очередное время входа, и то же значение — наименьшему достижимому; вершина кладётся на стек и помечается как находящаяся на нём. Для каждого соседа: если он бел, он обрабатывается рекурсивно, и наименьшее достижимое текущей вершины уменьшается до наименьшего достижимого соседа; если он на стеке, наименьшее достижимое уменьшается до ВРЕМЕНИ ВХОДА соседа. Различие двух случаев существенно: во втором берётся именно время входа, а не наименьшее достижимое. Использование наименьшего достижимого во втором случае даёт неверный результат на некоторых графах, и это самая частая ошибка изложений. Если по завершении обработки вершины её наименьшее достижимое равно её времени входа, вершина есть корень компоненты: со стека снимаются вершины до неё включительно, и они образуют сильно связную компоненту. Сосед, уже почерневший и НЕ находящийся на стеке, игнорируется: он принадлежит другой, уже выделенной компоненте, и учитывать его значило бы объединить две компоненты в одну. Оценка: один обход, время порядка числа вершин плюс числа рёбер, дополнительная память порядка числа вершин. Против Косарайю вариант выигрывает один обход и хранение обращённого графа, проигрывая в простоте обоснования; компоненты он выдаёт в порядке, обратном топологическому порядку графа конденсации, и это свойство иногда полезно само по себе.

Ссылаются нормы: f-025ad82d4722cc118d144f8c, f-04f8e1b3791012a8d2403de4, f-0a33e9988d05d35606b7649b, f-0ab5ffde648c162b1f899681, f-0abcb3d58c88c275ff86f2d6, f-0af52db2c99ba4900488bbfb, f-0ceff0795e58a0985d4d8323, f-0e0457da5507009144d6c124, f-0e7738c425dbf97b8004171f, f-1983ffde55bfa3ce97516a3c, f-1a78e29735f3ee2ad69592a7, f-1cc46454fc540efefdcdd4dc, f-1d296141a4781c75c8829c7d, f-2019855a2ce6661c2332abd4, f-240a41ea43004d96764e0fef, f-2590782bda63ca2baecb861c, f-25b6349e370a55f3d84f9070, f-2bb4d75cc44b78c7c7ae6b0a, f-2fff02ae21ea93f8ab34a34a, f-316f6842145bb4495f80f971, f-35822d6da2c4e5eb1bef1ab3, f-39d0b93e3083f1c39c08d149, f-3b067e7583a66e1dcbefcdce, f-3d830e9a4a5f88122bf12c20, f-4190fb1736ca23c337653089, f-41fa3a5ac2b9f1a34d73c1a2, f-42d02c66d744fa24a733bd4f, f-4514f716bfb333c9833f7117, f-46e62de83b202a447b5a212f, f-4926cd3143ccc13f673db46c, f-503cdc79fbdf33eeabfa16e4, f-506dc7ad8b0a66036672a6d9, f-50d89972e867cd84d8fe9226, f-5440550c3e34469d3d203767, f-56fd8baa8913cd960368c880, f-5796b1dd7f29e81364711dc4, f-5b3486a2f684b2bce1b1b9c1, f-5e04feab2cd8236af072c58c, f-5f7345066471b7032cf14c48, f-6b6aae2332ce0b689c347474, f-6bb428e718c3109cfdd2ac84, f-6bdb961d517bbf3eab4180c3, f-6be74fa457a411115b75378f, f-6e6dec8469802ac607784543, f-6f752f84b0422e3260ef90ba, f-70249f53525a711060b7bbd6, f-71f32a013afff52360adbb35, f-73077c122f79b6ad9438e557, f-756ca693fe79bbc85ea12621, f-7822e056928a7f1131dfe5d5, f-79bd2ebc56c30c8756461757, f-7aa91b762cc9f7632b202f39, f-7f0e4c29a2a630030ffc178d, f-81eb84f271bf48f7a6b65d83, f-84387204819e4b753f6dd6bc, f-8477eb693b44f764b7037033, f-87238dee5c085af14143615d, f-88166e62571cd0f5d37e9a85, f-8b5076ee29acd02932bbe179, f-8cc36957ffa9a2bde5fc6fca, f-91bcdeff0c56eea604ba178a, f-926c09c30e264cf15efcfd0a, f-92dd9631763972c808485839, f-94b966a417064f49634d7c75, f-95a3f8976aec6094e75b8027, f-95bedd441074d00e7112316c, f-98dd0a5519965507fd1162d9, f-9aabdda602347407be7a2052, f-a02b740294c6454f59187b29, f-a048a3363ac03c40d4acbc72, f-a055a2db4a66d6d929fcbe98, f-a5866155c20b81e20ef81a95, f-a619d3dcdb81cf09edcfce5c, f-ad14dccfe1c5679f21621f8d, f-ad60503255dc3ecbcc0c02f2, f-b042e3075459b88be91f62a7, f-b2fd51a6e3d90599b9f95d0c, f-b4e679ac4cdc4a96dd5deca3, f-b66632537caa874424da3289, f-bfd6ab69a6967299d13e8afc, f-c39a2a2596eee0cffde63001, f-c39f656e5c0ecfdc8daceffb, f-c3a7bc02cb387aad9197b278, f-c62d9de8274bd166f35b9d25, f-c8ee8ff7c36feb018f95e1bc, f-cb7b19791fb0ed2bdc0c126e, f-cf35059e4d49afa777df4cf3, f-d0f84eea83b229a393e0094c, f-d2cc03b85f9639e9a9c4ef23, f-d5a2da6fcd8b53d94705efaa, f-d7aa3477e5ffb881a805493e, f-deba2fe030f9461df1117d02, f-debe67b3f2152cc4f415c0cb, f-e078b4a72326622922d8c662, f-e1b53dd4d5845631c9dd6716, f-e28680a5c9c1c0d9209b4e7b, f-e7359fce79528bef3227769a, f-e99c52d4de8e5828aacd38c0, f-ebeefdd6f633d376b9b74d6b, f-ed6f26241613e2c37c45207e, f-eeb32c4adf027af325a802e8, f-f16ff5b18c6c490f3ae7c614, f-f174f3a12b51407f21c440b2, f-f8e73deedda9fd519017a6d6

ru · official · sha256:18615c53c2d97e933933277d74b39f9292e1801fdd8d6da752589b1473005c6a

ОБХОДЫ И СТРУКТУРА ГРАФА: BFS, DFS, КОМПОНЕНТЫ, ТОПОЛОГИЧЕСКАЯ СОРТИРОВКА И СИЛЬНЫЕ КОМПОНЕНТЫ Настоящий документ является АВТОРСКИМ ИЗЛОЖЕНИЕМ, составленным для целей формализации. Он описывает устройство семи алгоритмов: обхода в ширину, обхода в глубину, выделения компонент связности, двух топологических сортировок — методом Кана и через обход в глубину — и двух алгоритмов сильно связных компонент — Косарайю и Тарьяна. Изложение не воспроизводит ни один учебник; происхождение каждого алгоритма названо при его описании локатором. Описание отвечает на вопрос об устройстве алгоритма и не выполняет его: ни один граф здесь не обходится.