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

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

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

Проблем

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

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

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

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

Идеята

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

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

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

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

Виж го

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

def visit(graph, stop, island, island_of):
    island_of[stop] = island
    for nxt in graph[stop]:
        if nxt not in island_of:
            visit(graph, nxt, island, island_of)




def islands(graph, stops):
    island_of = {}
    count = 0
    for stop in stops:
        if stop in island_of:
            continue
        count += 1
        visit(graph, stop, count, island_of)
    return island_of

def visit(graph, stop, island, island_of):
    island_of[stop] = island
    for nxt in graph[stop]:
        if nxt not in island_of:
            visit(graph, nxt, island, island_of)




def islands(graph, stops):
    island_of = {}
    count = 0
    for stop in stops:
        if stop in island_of:
            continue
        count += 1
        visit(graph, stop, count, island_of)
    return island_of
Стъпка по стъпка, с думи
  1. Двата моста са затворени. islands минава спирките по ред: Склад още няма остров, затова count = 1 и visit тръгва от него.
  2. visit(Склад) му дава остров 1 и веднага слиза в първия съсед без остров: Гара. Склад чака сив в стека на извикванията.
  3. Все по-надълбоко: Гара → Площад → Пазар. Четири извиквания са отворени едновременно и всяко чака по-горното.
  4. Около Пазар всичко вече има остров. visit се връща и Пазар почернява. Назад по стека: и при Площад и Гара няма нищо ново.
  5. Склад пак е отгоре. Последният му съсед Пазар вече е видян и първият обход свършва: остров 1 е Склад, Гара, Пазар, Площад. Затворените мостове са го спрели на реката.
  6. Цикълът в islands продължава: Гара, Пазар и Площад вече имат остров и се прескачат. Парк няма: count = 2.
  7. Същият обход на другия бряг: Парк → Стадион → Болница → Кино, после назад до Парк.
  8. Два острова: по 4 спирки на всеки бряг. Всяка спирка получи номер веднъж, всяка улица беше погледната от двата края: O(V + E).

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

closed = [
    ("Пазар", "Парк"), ("Площад", "Кино"),
]
for a, b in closed:
    graph[a].remove(b)
    graph[b].remove(a)
island_of = islands(graph, stops)
count = max(island_of.values())
print(f"Острови: {count}")
for i in range(1, count + 1):
    members = [s for s in stops if island_of[s] == i]
    print(f"Остров {i}: " + ", ".join(members))
Изход
Острови: 2
Остров 1: Склад, Гара, Пазар, Площад
Остров 2: Парк, Кино, Болница, Стадион

Номерът на острова пази речник, а броят им е най-големият номер в него.

Пробвай

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

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

closed = [
    ("Площад", "Кино"), ("Кино", "Болница"),
]
for a, b in closed:
    graph[a].remove(b)
    graph[b].remove(a)
island_of = islands(graph, stops)
count = max(island_of.values())
print(f"Острови: {count}")
Отговор

Идеята

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

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

def walk(graph, start):
    order = []
    seen = set()
    stack = [start]
    while stack:
        stop = stack.pop()
        if stop in seen:
            continue
        seen.add(stop)
        order.append(stop)
        for nxt in reversed(graph[stop]):
            if nxt not in seen:
                stack.append(nxt)
    return order

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

  • Спирка може да влезе в стека два пъти: от двама съседи, преди да е посетена. Затова проверката „видяна ли е“ е и при взимането: втория път се прескача.
  • Съседите влизат наобратно. Последният сложен излиза пръв, затова първият съсед трябва да е най-отгоре. Така редът е същият като при рекурсията:
island_of = {}
visit(graph, "Склад", 1, island_of)
print("Рекурсия: " + ", ".join(island_of))
print("Свой стек: " + ", ".join(walk(graph, "Склад")))
Изход
Рекурсия: Склад, Гара, Площад, Пазар, Парк, Стадион, Болница, Кино
Свой стек: Склад, Гара, Площад, Пазар, Парк, Стадион, Болница, Кино
По-точно, за любопитните

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

Идеята

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

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

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

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

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

def find_cycle(plan, stop, color, path):
    color[stop] = "grey"
    path.append(stop)
    for nxt in plan[stop]:
        c = color.get(nxt, "white")
        if c == "grey":
            return path[path.index(nxt):] + [nxt]
        if c == "white":
            found = find_cycle(plan, nxt, color, path)
            if found is not None:
                return found
    color[stop] = "black"
    path.pop()
    return None

def find_cycle(plan, stop, color, path):
    color[stop] = "grey"
    path.append(stop)
    for nxt in plan[stop]:
        c = color.get(nxt, "white")
        if c == "grey":
            return path[path.index(nxt):] + [nxt]
        if c == "white":
            found = find_cycle(plan, nxt, color, path)
            if found is not None:
                return found
    color[stop] = "black"
    path.pop()
    return None
Стъпка по стъпка, с думи
  1. Всяка стрелка е правило: спирката, от която излиза, се доставя първа. Всички спирки са бели, никой не е виждан. Обходът тръгва от Склад.
  2. Сиво значи „на текущия път“: Склад → Гара → Площад. Тези извиквания още са отворени.
  3. От Площад не излизат правила: почернява, всичко след нея е проверено и тя излиза от пътя. И Гара е готова.
  4. И Пазар сочи към Площад, но Площад е черна: от нея няма път обратно до Пазар. Две правила към една спирка не са кръг.
  5. Отвъд реката пътят расте: Парк → Кино → Болница → Стадион, всички сиви.
  6. Стадион → Парк: Парк е сив, още е на пътя. Стрелката води обратно в самия път, а това е кръг.
  7. Кръгът е пътят от Парк до края: Парк → Кино → Болница → Стадион → Парк. Никой ред на тези четири спирки не спазва всички правила, затова правилото Стадион → Парк трябва да отпадне.

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

def any_cycle(plan, stops):
    color = {}
    for stop in stops:
        if stop in color:
            continue
        found = find_cycle(plan, stop, color, [])
        if found is not None:
            return found
    return None
rules = [
    ("Склад", "Гара"), ("Гара", "Площад"),
    ("Склад", "Пазар"), ("Пазар", "Площад"),
    ("Пазар", "Парк"), ("Парк", "Кино"),
    ("Кино", "Болница"), ("Болница", "Стадион"),
    ("Стадион", "Парк"),
]
cycle = any_cycle(plan, stops)
print("Няма кръг" if cycle is None else "Кръг: " + " → ".join(cycle))
Изход
Кръг: Парк → Кино → Болница → Стадион → Парк

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

def find_cycle(plan, stop, color, path):
    color[stop] = "grey"
    path.append(stop)
    for nxt in plan[stop]:
        c = color.get(nxt, "white")
        if c == "grey":
            return path[path.index(nxt):] + [nxt]
        if c == "white":
            found = find_cycle(plan, nxt, color, path)
            if found is not None:
                return found
    color[stop] = 
    path.pop()
    return None
По-точно, за любопитните

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

Идеята

Колко струва

Всяка спирка получава номер веднъж и се посещава веднъж. При посещението си поглежда своите улици, а двупосочна улица се вижда от двата края. Общо: 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 не пускаме, за да не замръзне страницата.
def islands(graph, stops):
    island_of = {}
    count = 0
    for stop in stops:
        if stop in island_of:
            continue
        count += 1
        visit(graph, stop, count, island_of)
    return island_of

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

Пробвай

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

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

def visit(graph, stop, island, island_of):
    island_of[stop] = island
    for nxt in graph[stop]:
        if nxt not in island_of:
            visit(graph, nxt, island + 1, island_of)
Изход
Острови: 5
Остров 1: Склад
Остров 2: Гара, Парк
Остров 3: Площад, Стадион
Остров 4: Пазар, Болница
Остров 5: Кино

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

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

По-точно

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

Python спира рекурсията на 1000 нива с RecursionError. sys.setrecursionlimit вдига границата, но под нея е стекът на C, и при твърде голяма граница процесът пада без съобщение. За графи с хиляди спирки ползвай списък като стек: append и pop от края са O(1).

Упражнение

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

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

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

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

Още задачи

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

Тест

Провери се

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

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