Към съдържанието
wannacode

DFS: острови и кръгове

Накратко: DFS (търсене в дълбочина) върви по един път докрай и се връща, с рекурсия или със стек; намира свързаните компоненти и кръговете в граф за O(V + E).

Проблем

Градът, разрязан от реката

Общината затваря двата моста за ремонт. Куриерите вече не могат да минат реката, и диспечерът трябва да знае на колко части се разпада градът и кои спирки са във всяка част: всяка част ще обслужва отделен бус.

От урока за BFS знаеш как да намериш докъде се стига от склада. Но частите може да са много, и всяка трябва да се намери цялата. Трябва обход, който тръгва от всяка спирка, още без част, и маркира всичко, до което стига.

Има и втори проблем в същия град. Планът на доставките има правила „А се доставя преди Б“. Някой е добавил грешно правило, и вече няма ред, който да спазва всички. Кое правило е виновно?

Идеята

Докъдето стига улицата

DFS (depth-first search, обхождане в дълбочина) върви като човек в лабиринт: тръгва по първата улица към непозната спирка, оттам по първата към следващата непозната, и така, докато стигне спирка, около която всичко е видяно. Тогава се връща една спирка назад и опитва следващата ѝ улица.

С рекурсия връщането назад става само: visit за спирката вика visit за първия непознат съсед, и когато той свърши, цикълът продължава със следващия. Стекът на извикванията помни докъде е стигнала всяка спирка.

  • Всяка спирка получава номера на острова си веднага при влизане. Това е и множеството на видените: спирка с номер не се посещава втори път.
  • Остров (свързана компонента) е всичко, до което стига един visit. Цикълът по всички спирки пуска нов visit от всяка спирка без номер.

Виж го

Надолу и назад

static void Visit(Dictionary<string, List<string>> graph,
                  string stop, int island,
                  Dictionary<string, int> islandOf)
{
    islandOf[stop] = island;
    foreach (string next in graph[stop])
    {
        if (!islandOf.ContainsKey(next))
        {
            Visit(graph, next, island, islandOf);
        }
    }
}


static Dictionary<string, int> Islands(
    Dictionary<string, List<string>> graph, string[] stops)
{
    var islandOf = new Dictionary<string, int>();
    int count = 0;
    foreach (string stop in stops)
    {
        if (islandOf.ContainsKey(stop)) continue;
        count++;
        Visit(graph, stop, count, islandOf);
    }
    return islandOf;
}

static void Visit(Dictionary<string, List<string>> graph,
                  string stop, int island,
                  Dictionary<string, int> islandOf)
{
    islandOf[stop] = island;
    foreach (string next in graph[stop])
    {
        if (!islandOf.ContainsKey(next))
        {
            Visit(graph, next, island, islandOf);
        }
    }
}


static Dictionary<string, int> Islands(
    Dictionary<string, List<string>> graph, string[] stops)
{
    var islandOf = new Dictionary<string, int>();
    int count = 0;
    foreach (string stop in stops)
    {
        if (islandOf.ContainsKey(stop)) continue;
        count++;
        Visit(graph, stop, count, islandOf);
    }
    return islandOf;
}
Стъпка по стъпка, с думи
  1. Двата моста са затворени. islands минава спирките по ред: Склад още няма остров, затова count = 1 и visit тръгва от него.
  2. visit(Склад) му дава остров 1 и веднага слиза в първия съсед без остров: Гара. Склад чака сив в стека на извикванията.
  3. Все по-надълбоко: Гара → Площад → Пазар. Четири извиквания са отворени едновременно и всяко чака по-горното.
  4. Около Пазар всичко вече има остров. visit се връща и Пазар почернява. Назад по стека: и при Площад и Гара няма нищо ново.
  5. Склад пак е отгоре. Последният му съсед Пазар вече е видян и първият обход свършва: остров 1 е Склад, Гара, Пазар, Площад. Затворените мостове са го спрели на реката.
  6. Цикълът в islands продължава: Гара, Пазар и Площад вече имат остров и се прескачат. Парк няма: count = 2.
  7. Същият обход на другия бряг: Парк → Стадион → Болница → Кино, после назад до Парк.
  8. Два острова: по 4 спирки на всеки бряг. Всяка спирка получи номер веднъж, всяка улица беше погледната от двата края: O(V + E).

Програмата затваря мостовете, пуска Islands и печата островите:

(string, string)[] closed =
[
    ("Пазар", "Парк"), ("Площад", "Кино"),
];
foreach (var (a, b) in closed)
{
    graph[a].Remove(b);
    graph[b].Remove(a);
}
var islandOf = Islands(graph, stops);
int count = islandOf.Values.Max();
Console.WriteLine("Острови: " + count);
for (int i = 1; i <= count; i++)
{
    var members = stops.Where(s => islandOf[s] == i);
    Console.WriteLine($"Остров {i}: {string.Join(", ", members)}");
}
Изход
Острови: 2
Остров 1: Склад, Гара, Пазар, Площад
Остров 2: Парк, Кино, Болница, Стадион

Номерът на острова пази Dictionary<string, int>, а броят им е най-големият номер в него.

Пробвай

Предвиди изхода

Мостът Пазар – Парк е отворен, но около Кино се копае: затворени са Площад – Кино и Кино – Болница. Колко острова печата програмата?

(string, string)[] closed =
[
    ("Площад", "Кино"), ("Кино", "Болница"),
];
foreach (var (a, b) in closed)
{
    graph[a].Remove(b);
    graph[b].Remove(a);
}
var islandOf = Islands(graph, stops);
int count = islandOf.Values.Max();
Console.WriteLine("Острови: " + count);
Отговор

Идеята

Свой стек вместо рекурсия

Тук островите са по 4 спирки и рекурсията е дълбока 4 извиквания. В град-решетка от 100 000 кръстовища обходът в дълбочина може да слезе на десетки хиляди нива, а всяко ниво е рамка в стека на извикванията. Стекът е малък и се препълва. Как се превръща рекурсия в цикъл, е в урока „От рекурсия към цикъл“. Тук е същото: стекът става обикновена колекция.

static List<string> Walk(Dictionary<string, List<string>> graph,
                         string start)
{
    var order = new List<string>();
    var seen = new HashSet<string>();
    var stack = new Stack<string>();
    stack.Push(start);
    while (stack.Count > 0)
    {
        string stop = stack.Pop();
        if (!seen.Add(stop)) continue;
        order.Add(stop);
        var next = graph[stop];
        for (int i = next.Count - 1; i >= 0; i--)
        {
            if (!seen.Contains(next[i])) stack.Push(next[i]);
        }
    }
    return order;
}

Две неща са по-различни от рекурсията:

  • Спирка може да влезе в стека два пъти: от двама съседи, преди да е посетена. Затова проверката „видяна ли е“ е и при взимането: втория път се прескача.
  • Съседите влизат наобратно. Последният сложен излиза пръв, затова първият съсед трябва да е най-отгоре. Така редът е същият като при рекурсията:
var islandOf = new Dictionary<string, int>();
Visit(graph, "Склад", 1, islandOf);
Console.WriteLine("Рекурсия: " + string.Join(", ", islandOf.Keys));
Console.WriteLine("Свой стек: " + string.Join(", ", Walk(graph, "Склад")));
Изход
Рекурсия: Склад, Гара, Площад, Пазар, Парк, Стадион, Болница, Кино
Свой стек: Склад, Гара, Площад, Пазар, Парк, Стадион, Болница, Кино
По-точно, за любопитните

Ако сложиш съседите в реда на списъка, обходът пак е в дълбочина и пак намира същите острови, само редът на посещение е друг. За островите редът няма значение. За кръговете в насочен граф по-долу има: там трябва да знаеш кога свършва всяка спирка, а със стек от спирки това е по-трудно. Затова findCycle е рекурсивен, а при дълбоки графи в стека се слага двойка (спирка, докъде е стигнала в списъка си).

Идеята

Кръг в плана на доставките

Правилата на плана са насочен граф: стрелката Пазар → Парк значи „Пазар преди Парк“. Ако стрелките образуват кръг, няма ред, който да ги спазва: всяка спирка от кръга трябва да е преди себе си.

Само „видена“ не стига, за да хванеш кръг. Пазар → Площад води до видена спирка, но кръг няма: от Площад не се стига обратно до Пазар. Затова спирките имат три цвята:

  • бяла: още не е виждана;
  • сива: на текущия път, извикването ѝ още е отворено;
  • черна: всичко след нея е проверено и кръг няма.

Стрелка към сива спирка води обратно в собствения път: това е кръгът.

static List<string>? FindCycle(
    Dictionary<string, List<string>> plan, string stop,
    Dictionary<string, string> color, List<string> path)
{
    color[stop] = "grey";
    path.Add(stop);
    foreach (string next in plan[stop])
    {
        string c = color.GetValueOrDefault(next, "white");
        if (c == "grey")
        {
            var cycle = path[path.IndexOf(next)..];
            cycle.Add(next);
            return cycle;
        }
        if (c == "white")
        {
            var found = FindCycle(plan, next, color, path);
            if (found != null) return found;
        }
    }
    color[stop] = "black";
    path.RemoveAt(path.Count - 1);
    return null;
}

static List<string>? FindCycle(
    Dictionary<string, List<string>> plan, string stop,
    Dictionary<string, string> color, List<string> path)
{
    color[stop] = "grey";
    path.Add(stop);
    foreach (string next in plan[stop])
    {
        string c = color.GetValueOrDefault(next, "white");
        if (c == "grey")
        {
            var cycle = path[path.IndexOf(next)..];
            cycle.Add(next);
            return cycle;
        }
        if (c == "white")
        {
            var found = FindCycle(plan, next, color, path);
            if (found != null) return found;
        }
    }
    color[stop] = "black";
    path.RemoveAt(path.Count - 1);
    return null;
}
Стъпка по стъпка, с думи
  1. Всяка стрелка е правило: спирката, от която излиза, се доставя първа. Всички спирки са бели, никой не е виждан. Обходът тръгва от Склад.
  2. Сиво значи „на текущия път“: Склад → Гара → Площад. Тези извиквания още са отворени.
  3. От Площад не излизат правила: почернява, всичко след нея е проверено и тя излиза от пътя. И Гара е готова.
  4. И Пазар сочи към Площад, но Площад е черна: от нея няма път обратно до Пазар. Две правила към една спирка не са кръг.
  5. Отвъд реката пътят расте: Парк → Кино → Болница → Стадион, всички сиви.
  6. Стадион → Парк: Парк е сив, още е на пътя. Стрелката води обратно в самия път, а това е кръг.
  7. Кръгът е пътят от Парк до края: Парк → Кино → Болница → Стадион → Парк. Никой ред на тези четири спирки не спазва всички правила, затова правилото Стадион → Парк трябва да отпадне.

Цикълът пуска findCycle от всяка бяла спирка, както islands пуска visit:

static List<string>? AnyCycle(
    Dictionary<string, List<string>> plan, string[] stops)
{
    var color = new Dictionary<string, string>();
    foreach (string stop in stops)
    {
        if (color.ContainsKey(stop)) continue;
        var found = FindCycle(plan, stop, color, []);
        if (found != null) return found;
    }
    return null;
}
(string, string)[] rules =
[
    ("Склад", "Гара"), ("Гара", "Площад"),
    ("Склад", "Пазар"), ("Пазар", "Площад"),
    ("Пазар", "Парк"), ("Парк", "Кино"),
    ("Кино", "Болница"), ("Болница", "Стадион"),
    ("Стадион", "Парк"),
];
var cycle = AnyCycle(plan, stops);
Console.WriteLine(cycle == null ? "Няма кръг" : "Кръг: " + string.Join(" → ", cycle));
Изход
Кръг: Парк → Кино → Болница → Стадион → Парк

Махни последното правило, и програмата печата Няма кръг. Тогава редът, в който спирките почерняват, е обърнатият ред на доставките. На това стъпва топологичното сортиране, следващият урок.

static List<string>? FindCycle(
    Dictionary<string, List<string>> plan, string stop,
    Dictionary<string, string> color, List<string> path)
{
    color[stop] = "grey";
    path.Add(stop);
    foreach (string next in plan[stop])
    {
        string c = color.GetValueOrDefault(next, "white");
        if (c == "grey")
        {
            var cycle = path[path.IndexOf(next)..];
            cycle.Add(next);
            return cycle;
        }
        if (c == "white")
        {
            var found = FindCycle(plan, next, color, path);
            if (found != null) return found;
        }
    }
    color[stop] = ;
    path.RemoveAt(path.Count - 1);
    return null;
}
По-точно, за любопитните

В двупосочен граф всяка улица е стрелка и в двете посоки, и всеки съсед, от който си дошъл, е „видян“. Там кръг има, ако стигнеш видена спирка, която не е тази, от която току-що идваш. Трите цвята трябват за насочен граф.

Идеята

Колко струва

Всяка спирка получава номер веднъж и се посещава веднъж. При посещението си поглежда своите улици, а двупосочна улица се вижда от двата края. Общо: V посещения и 2E погледа, O(V + E), колкото BFS.

Линейно е само ако номерът на острова е общ за целия обход. Ако за всяка спирка питаш „на кой остров съм?“ с нов обход и празно множество на видените, правиш n обхода. Пусни и двата върху град-решетка от n кръстовища, която реката реже на две:

  • Един общ islandOf за целия град O(n)
  • Нов обход за всяко кръстовище O(n²)
Алгоритъмn = 10n = 1000n = 2000n = 100 000
Един общ islandOf за целия град2848089730498 100
Нов обход за всяко кръстовище1482 405 4409 730 980≈ 24 327 450 000
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.
static Dictionary<string, int> Islands(
    Dictionary<string, List<string>> graph, string[] stops)
{
    var islandOf = new Dictionary<string, int>();
    int count = 0;
    foreach (string stop in stops)
    {
        if (islandOf.ContainsKey(stop)) continue;
        count++;
        Visit(graph, stop, count, islandOf);
    }
    return islandOf;
}

Броят се всяка спирка, взета от стека, и всеки поглед към съсед. И двата са със свой стек: при 100 000 кръстовища рекурсията в браузъра пада с препълнен стек. При 1000 кръстовища общият номер прави 4 808 операции, а новият обход за всяко кръстовище 2 405 440. При 2000 новият обход е вече 9 730 980, а общият при 100 000 прави 498 100.

Пробвай

Намери грешката

Колега реши, че в visit островът трябва да расте с всяка стъпка. Програмата печата:

static void Visit(Dictionary<string, List<string>> graph,
                  string stop, int island,
                  Dictionary<string, int> islandOf)
{
    islandOf[stop] = island;
    foreach (string next in graph[stop])
    {
        if (!islandOf.ContainsKey(next))
        {
            Visit(graph, next, island + 1, islandOf);
        }
    }
}
Изход
Острови: 5
Остров 1: Склад
Остров 2: Гара, Парк
Остров 3: Площад, Стадион
Остров 4: Пазар, Болница
Остров 5: Кино

Островите са пет, а Гара и Парк са „на един остров“, макар мостовете да са затворени. На кой ред е грешката?

Избери реда с грешката.

По-точно

Колко дълбоко може рекурсията

Стекът на нишка в .NET е около 1 MB. Препълването (StackOverflowException) не може да се хване: процесът спира. Затова при голям граф ползвай Stack<T>. Ако все пак трябва рекурсия, може да я пуснеш в Thread с по-голям стек.

Упражнение

Критичните улици

Реши задачата в редактора си.

Критични улици. Мостът Пазар – Парк е затворен за месец, а Площад – Кино още работи. Улица е критична, ако затварянето ѝ разделя града на повече острови. Затвори моста, изведи колко острова има, после за всяка отворена улица я махни, преброй островите с islands и я върни. Изведи критичните улици в реда на streets.

(string, string)[] closed =
[
    ("Пазар", "Парк"),
];
Изход
Острови: 1
Критични: Площад - Кино, Кино - Болница, Парк - Стадион, Болница - Стадион

Още задачи

  • Най-големият остров. Изведи острова с най-много спирки и колко бус-часа на седмица му трябват, ако всяка спирка иска 3 часа.
  • Кръгът в плана. Направи findCycle със свой стек: в стека слагай двойка (спирка, индекс на следващия съсед), а спирката почернява, когато индексът стигне края на списъка ѝ.
  • Острови на картата. Картата на склада е решетка от # (рафт) и . (свободно). Преброй свободните зони, като съседи на клетка са горе, долу, ляво и дясно.

Тест

Провери се

1. Какво прави DFS, когато около текущата спирка всичко вече е видяно?
2. Защо islands минава през всички спирки, а не пуска visit само от склада?
3. В насочения план findCycle вижда стрелка към черна спирка. Кръг ли е?
4. Градът има 100 000 кръстовища в една дълга верига. Какво става с рекурсивния visit?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·