Графы: BFS, DFS и топологическая сортировка

from collections import defaultdict

edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E")]

graph = defaultdict(list)                  # список смежности — основной вариант
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)                     # для неориентированного — в обе стороны
print(dict(graph))

names = ["A", "B", "C", "D", "E"]          # матрица смежности — для плотных графов
idx = {n: i for i, n in enumerate(names)}
matrix = [[0] * len(names) for _ in names]
for u, v in edges:
    matrix[idx[u]][idx[v]] = matrix[idx[v]][idx[u]] = 1
for name, row in zip(names, matrix):
    print(name, row)

graph = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C", "E"], "E": ["D"], "X": ["Y"], "Y": ["X"]}

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

print(dfs("A"))

def components(graph):
    seen, result = set(), []
    for node in graph:
        if node not in seen:
            comp = dfs(node)
            seen.update(comp)
            result.append(comp)
    return result

print("компоненты связности:", components(graph))

from collections import deque

graph = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C", "E"], "E": ["D"]}

def bfs_path(start, goal):
    queue = deque([start])
    parent = {start: None}                     # заодно и visited
    while queue:
        node = queue.popleft()
        if node == goal:
            path = []
            while node is not None:            # восстановить путь по родителям
                path.append(node)
                node = parent[node]
            return path[::-1]
        for nxt in graph[node]:
            if nxt not in parent:
                parent[nxt] = node
                queue.append(nxt)
    return None

print(bfs_path("A", "E"))

from collections import deque

def rotting_oranges(grid):
    """Сколько минут, пока сгниют все апельсины (2 — гнилой, 1 — свежий). BFS от нескольких источников."""
    rows, cols = len(grid), len(grid[0])
    queue = deque((r, c) for r in range(rows) for c in range(cols) if grid[r][c] == 2)
    fresh = sum(row.count(1) for row in grid)
    minutes = 0
    while queue and fresh:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
        minutes += 1
    return minutes if fresh == 0 else -1

print(rotting_oranges([[2, 1, 1], [1, 1, 0], [0, 1, 1]]))

from collections import deque, defaultdict

deps = {"app": ["db", "cache"], "db": ["config"], "cache": ["config"], "config": [], "tests": ["app"]}

def topo_sort(deps):
    graph = defaultdict(list)
    indegree = {node: 0 for node in deps}
    for node, needs in deps.items():
        for need in needs:
            graph[need].append(node)
            indegree[node] += 1
    queue = deque(n for n, d in indegree.items() if d == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    if len(order) != len(deps):
        raise ValueError("циклическая зависимость")
    return order

print(topo_sort(deps))
try:
    topo_sort({"a": ["b"], "b": ["a"]})
except ValueError as e:
    print("ValueError:", e)

from graphlib import TopologicalSorter            # в стандартной библиотеке с Python 3.9
print(list(TopologicalSorter(deps).static_order()))

import heapq

graph = {
    "Дом": [("Метро", 5), ("Автобус", 2)],
    "Автобус": [("Метро", 1), ("Работа", 9)],
    "Метро": [("Работа", 3)],
    "Работа": [],
}

def dijkstra(graph, source):
    dist = {source: 0}
    prev = {}
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                              # устаревшая запись в куче
        for v, w in graph[u]:
            if d + w < dist.get(v, float("inf")):
                dist[v] = d + w
                prev[v] = u
                heapq.heappush(heap, (d + w, v))
    return dist, prev

dist, prev = dijkstra(graph, "Дом")
path, node = [], "Работа"
while node:
    path.append(node)
    node = prev.get(node)
print(dist, " → ".join(reversed(path)))

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]     # сжатие пути
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                                   # уже вместе → ребро создаёт цикл
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra                               # меньшее дерево под большее
        self.size[ra] += self.size[rb]
        return True

uf = UnionFind(6)
for a, b in [(0, 1), (1, 2), (3, 4)]:
    uf.union(a, b)
print(uf.find(0) == uf.find(2), uf.find(0) == uf.find(3))
print("компонент:", len({uf.find(i) for i in range(6)}))
print("ребро 2–0 создаёт цикл:", not uf.union(2, 0))