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

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

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

Проблем

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

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

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

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

Идеята

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

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

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

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

Виж го

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

static void visit(Map<String, List<String>> graph,
                  String stop, int island,
                  Map<String, Integer> islandOf) {
    islandOf.put(stop, island);
    for (String next : graph.get(stop)) {
        if (!islandOf.containsKey(next)) {
            visit(graph, next, island, islandOf);
        }
    }
}


static Map<String, Integer> islands(
        Map<String, List<String>> graph, String[] stops) {
    Map<String, Integer> islandOf = new HashMap<>();
    int count = 0;
    for (String stop : stops) {
        if (islandOf.containsKey(stop)) continue;
        count++;
        visit(graph, stop, count, islandOf);
    }
    return islandOf;
}

static void visit(Map<String, List<String>> graph,
                  String stop, int island,
                  Map<String, Integer> islandOf) {
    islandOf.put(stop, island);
    for (String next : graph.get(stop)) {
        if (!islandOf.containsKey(next)) {
            visit(graph, next, island, islandOf);
        }
    }
}


static Map<String, Integer> islands(
        Map<String, List<String>> graph, String[] stops) {
    Map<String, Integer> islandOf = new HashMap<>();
    int count = 0;
    for (String stop : 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[][] closed = {
    {"Пазар", "Парк"}, {"Площад", "Кино"},
};
for (String[] street : closed) {
    graph.get(street[0]).remove(street[1]);
    graph.get(street[1]).remove(street[0]);
}
Map<String, Integer> islandOf = islands(graph, stops);
int count = Collections.max(islandOf.values());
System.out.println("Острови: " + count);
for (int i = 1; i <= count; i++) {
    List<String> members = new ArrayList<>();
    for (String stop : stops) {
        if (islandOf.get(stop) == i) members.add(stop);
    }
    System.out.println("Остров " + i + ": " + String.join(", ", members));
}
Изход
Острови: 2
Остров 1: Склад, Гара, Пазар, Площад
Остров 2: Парк, Кино, Болница, Стадион

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

Пробвай

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

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

String[][] closed = {
    {"Площад", "Кино"}, {"Кино", "Болница"},
};
for (String[] street : closed) {
    graph.get(street[0]).remove(street[1]);
    graph.get(street[1]).remove(street[0]);
}
Map<String, Integer> islandOf = islands(graph, stops);
int count = Collections.max(islandOf.values());
System.out.println("Острови: " + count);
Отговор

Идеята

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

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

static List<String> walk(Map<String, List<String>> graph,
                         String start) {
    List<String> order = new ArrayList<>();
    Set<String> seen = new HashSet<>();
    Deque<String> stack = new ArrayDeque<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        String stop = stack.pop();
        if (!seen.add(stop)) continue;
        order.add(stop);
        List<String> next = graph.get(stop);
        for (int i = next.size() - 1; i >= 0; i--) {
            if (!seen.contains(next.get(i))) stack.push(next.get(i));
        }
    }
    return order;
}

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

  • Спирка може да влезе в стека два пъти: от двама съседи, преди да е посетена. Затова проверката „видяна ли е“ е и при взимането: втория път се прескача.
  • Съседите влизат наобратно. Последният сложен излиза пръв, затова първият съсед трябва да е най-отгоре. Така редът е същият като при рекурсията:
Map<String, Integer> islandOf = new LinkedHashMap<>();
visit(graph, "Склад", 1, islandOf);
System.out.println("Рекурсия: " + String.join(", ", islandOf.keySet()));
System.out.println("Свой стек: " + String.join(", ", walk(graph, "Склад")));
Изход
Рекурсия: Склад, Гара, Площад, Пазар, Парк, Стадион, Болница, Кино
Свой стек: Склад, Гара, Площад, Пазар, Парк, Стадион, Болница, Кино
HashMap не пази реда на добавяне, затова тук островът е в LinkedHashMap: keySet() дава спирките в реда на посещение.
По-точно, за любопитните

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

Идеята

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

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

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

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

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

static List<String> findCycle(
        Map<String, List<String>> plan, String stop,
        Map<String, String> color, List<String> path) {
    color.put(stop, "grey");
    path.add(stop);
    for (String next : plan.get(stop)) {
        String c = color.getOrDefault(next, "white");
        if (c.equals("grey")) {
            var cycle = new ArrayList<String>(path);
            cycle.subList(0, path.indexOf(next)).clear();
            cycle.add(next);
            return cycle;
        }
        if (c.equals("white")) {
            var found = findCycle(plan, next, color, path);
            if (found != null) return found;
        }
    }
    color.put(stop, "black");
    path.remove(path.size() - 1);
    return null;
}

static List<String> findCycle(
        Map<String, List<String>> plan, String stop,
        Map<String, String> color, List<String> path) {
    color.put(stop, "grey");
    path.add(stop);
    for (String next : plan.get(stop)) {
        String c = color.getOrDefault(next, "white");
        if (c.equals("grey")) {
            var cycle = new ArrayList<String>(path);
            cycle.subList(0, path.indexOf(next)).clear();
            cycle.add(next);
            return cycle;
        }
        if (c.equals("white")) {
            var found = findCycle(plan, next, color, path);
            if (found != null) return found;
        }
    }
    color.put(stop, "black");
    path.remove(path.size() - 1);
    return null;
}
Стъпка по стъпка, с думи
  1. Всяка стрелка е правило: спирката, от която излиза, се доставя първа. Всички спирки са бели, никой не е виждан. Обходът тръгва от Склад.
  2. Сиво значи „на текущия път“: Склад → Гара → Площад. Тези извиквания още са отворени.
  3. От Площад не излизат правила: почернява, всичко след нея е проверено и тя излиза от пътя. И Гара е готова.
  4. И Пазар сочи към Площад, но Площад е черна: от нея няма път обратно до Пазар. Две правила към една спирка не са кръг.
  5. Отвъд реката пътят расте: Парк → Кино → Болница → Стадион, всички сиви.
  6. Стадион → Парк: Парк е сив, още е на пътя. Стрелката води обратно в самия път, а това е кръг.
  7. Кръгът е пътят от Парк до края: Парк → Кино → Болница → Стадион → Парк. Никой ред на тези четири спирки не спазва всички правила, затова правилото Стадион → Парк трябва да отпадне.

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

static List<String> anyCycle(Map<String, List<String>> plan,
                             String[] stops) {
    Map<String, String> color = new HashMap<>();
    for (String stop : stops) {
        if (color.containsKey(stop)) continue;
        var found = findCycle(plan, stop, color, new ArrayList<>());
        if (found != null) return found;
    }
    return null;
}
String[][] rules = {
    {"Склад", "Гара"}, {"Гара", "Площад"},
    {"Склад", "Пазар"}, {"Пазар", "Площад"},
    {"Пазар", "Парк"}, {"Парк", "Кино"},
    {"Кино", "Болница"}, {"Болница", "Стадион"},
    {"Стадион", "Парк"},
};
List<String> cycle = anyCycle(plan, stops);
System.out.println(cycle == null ? "Няма кръг" : "Кръг: " + String.join(" → ", cycle));
Изход
Кръг: Парк → Кино → Болница → Стадион → Парк

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

static List<String> findCycle(
        Map<String, List<String>> plan, String stop,
        Map<String, String> color, List<String> path) {
    color.put(stop, "grey");
    path.add(stop);
    for (String next : plan.get(stop)) {
        String c = color.getOrDefault(next, "white");
        if (c.equals("grey")) {
            var cycle = new ArrayList<String>(path);
            cycle.subList(0, path.indexOf(next)).clear();
            cycle.add(next);
            return cycle;
        }
        if (c.equals("white")) {
            var found = findCycle(plan, next, color, path);
            if (found != null) return found;
        }
    }
    color.put(stop, );
    path.remove(path.size() - 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 Map<String, Integer> islands(
        Map<String, List<String>> graph, String[] stops) {
    Map<String, Integer> islandOf = new HashMap<>();
    int count = 0;
    for (String stop : 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(Map<String, List<String>> graph,
                  String stop, int island,
                  Map<String, Integer> islandOf) {
    islandOf.put(stop, island);
    for (String next : graph.get(stop)) {
        if (!islandOf.containsKey(next)) {
            visit(graph, next, island + 1, islandOf);
        }
    }
}
Изход
Острови: 5
Остров 1: Склад
Остров 2: Гара, Парк
Остров 3: Площад, Стадион
Остров 4: Пазар, Болница
Остров 5: Кино

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

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

По-точно

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

Стекът на нишка в Java е около 1 MB по подразбиране (настройва се с -Xss), което стига за няколко хиляди до десетки хиляди извиквания на visit. Препълването хвърля StackOverflowError. Може да го хванеш, но обходът вече е прекъснат. За големи графи ползвай ArrayDeque като стек: push и pop.

Упражнение

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

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

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

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

Още задачи

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

Тест

Провери се

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

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