Графы

живой пример

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class GraphWalk {
    static final Map<String, List<String>> GRAPH = Map.of(
            "A", List.of("B", "C"), "B", List.of("D", "E"), "C", List.of("E", "F"),
            "D", List.of(), "E", List.of(), "F", List.of());

    static List<String> walk(String start, boolean depthFirst) {
        List<String> order = new ArrayList<>();
        Set<String> seen = new HashSet<>();
        Deque<String> pending = new ArrayDeque<>();
        pending.add(start);
        while (!pending.isEmpty()) {
            String node = depthFirst ? pending.pollLast() : pending.pollFirst();
            if (!seen.add(node)) continue;
            order.add(node);
            pending.addAll(GRAPH.get(node));
        }
        return order;
    }

    public static void main(String[] args) {
        System.out.println("в ширину:  " + walk("A", false));
        System.out.println("в глубину: " + walk("A", true));
    }
}

живой пример

package main

import "fmt"

var graph = map[string][]string{
	"A": {"B", "C"}, "B": {"D", "E"}, "C": {"E", "F"},
	"D": {}, "E": {}, "F": {},
}

func walk(start string, depthFirst bool) []string {
	var order []string
	seen := map[string]bool{}
	pending := []string{start}
	for len(pending) > 0 {
		var node string
		if depthFirst {
			node, pending = pending[len(pending)-1], pending[:len(pending)-1]
		} else {
			node, pending = pending[0], pending[1:]
		}
		if seen[node] {
			continue
		}
		seen[node] = true
		order = append(order, node)
		pending = append(pending, graph[node]...)
	}
	return order
}

func main() {
	fmt.Println("в ширину: ", walk("A", false))
	fmt.Println("в глубину:", walk("A", true))
}

живой пример

const GRAPH = new Map([
  ["A", ["B", "C"]], ["B", ["D", "E"]], ["C", ["E", "F"]],
  ["D", []], ["E", []], ["F", []],
]);

function walk(start, depthFirst) {
  const order = [];
  const seen = new Set();
  const pending = [start];
  while (pending.length > 0) {
    const node = depthFirst ? pending.pop() : pending.shift();
    if (seen.has(node)) continue;
    seen.add(node);
    order.push(node);
    pending.push(...GRAPH.get(node));
  }
  return order;
}

console.log("в ширину: ", walk("A", false));
console.log("в глубину:", walk("A", true));

живой пример

from collections import deque

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


def walk(start: str, depth_first: bool) -> list[str]:
    order: list[str] = []
    seen: set[str] = set()
    pending = deque([start])
    while pending:
        node = pending.pop() if depth_first else pending.popleft()
        if node in seen:
            continue
        seen.add(node)
        order.append(node)
        pending.extend(GRAPH[node])
    return order


print("в ширину: ", walk("A", False))
print("в глубину:", walk("A", True))

живой пример

import java.util.*;

public class BfsPath {
    static final Map<String, List<String>> GRAPH = Map.of(
            "A", List.of("B", "C"), "B", List.of("D"), "C", List.of("D", "E"),
            "D", List.of("F"), "E", List.of("F"), "F", List.of());

    static List<String> path(String from, String to) {
        Map<String, String> cameFrom = new HashMap<>();
        Deque<String> queue = new ArrayDeque<>(List.of(from));
        cameFrom.put(from, null);
        while (!queue.isEmpty()) {
            String node = queue.poll();
            if (node.equals(to)) break;
            for (String next : GRAPH.get(node)) {
                if (!cameFrom.containsKey(next)) {
                    cameFrom.put(next, node);
                    queue.add(next);
                }
            }
        }
        if (!cameFrom.containsKey(to)) return List.of();
        LinkedList<String> path = new LinkedList<>();
        for (String v = to; v != null; v = cameFrom.get(v)) path.addFirst(v);
        return path;
    }

    public static void main(String[] args) {
        System.out.println(path("A", "F"));
    }
}

живой пример

package main

import (
	"fmt"
	"slices"
)

var graph = map[string][]string{
	"A": {"B", "C"}, "B": {"D"}, "C": {"D", "E"},
	"D": {"F"}, "E": {"F"}, "F": {},
}

func path(from, to string) []string {
	cameFrom := map[string]string{from: ""}
	queue := []string{from}
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if node == to {
			break
		}
		for _, next := range graph[node] {
			if _, seen := cameFrom[next]; !seen {
				cameFrom[next] = node
				queue = append(queue, next)
			}
		}
	}
	if _, ok := cameFrom[to]; !ok {
		return nil
	}
	var path []string
	for v := to; v != ""; v = cameFrom[v] {
		path = append(path, v)
	}
	slices.Reverse(path)
	return path
}

func main() {
	fmt.Println(path("A", "F"))
}

живой пример

const GRAPH = new Map([
  ["A", ["B", "C"]], ["B", ["D"]], ["C", ["D", "E"]],
  ["D", ["F"]], ["E", ["F"]], ["F", []],
]);

function path(from, to) {
  const cameFrom = new Map([[from, null]]);
  const queue = [from];
  let head = 0;
  while (head < queue.length) {
    const node = queue[head++];
    if (node === to) break;
    for (const next of GRAPH.get(node)) {
      if (!cameFrom.has(next)) {
        cameFrom.set(next, node);
        queue.push(next);
      }
    }
  }
  if (!cameFrom.has(to)) return [];
  const path = [];
  for (let v = to; v !== null; v = cameFrom.get(v)) path.unshift(v);
  return path;
}

console.log(path("A", "F"));

живой пример

from collections import deque

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


def path(start: str, goal: str) -> list[str]:
    came_from = {start: None}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            break
        for nxt in GRAPH[node]:
            if nxt not in came_from:
                came_from[nxt] = node
                queue.append(nxt)
    if goal not in came_from:
        return []
    result = []
    v = goal
    while v is not None:
        result.append(v)
        v = came_from[v]
    return result[::-1]


print(path("A", "F"))

int components(List<List<Integer>> adj) {
    boolean[] seen = new boolean[adj.size()];
    int count = 0;
    for (int start = 0; start < adj.size(); start++) {
        if (seen[start]) continue;
        count++;
        Deque<Integer> pending = new ArrayDeque<>(List.of(start));
        while (!pending.isEmpty()) {
            int u = pending.pop();
            if (seen[u]) continue;
            seen[u] = true;
            for (int v : adj.get(u)) if (!seen[v]) pending.push(v);
        }
    }
    return count;
}

func components(adj [][]int) int {
	seen := make([]bool, len(adj))
	count := 0
	for start := range adj {
		if seen[start] {
			continue
		}
		count++
		pending := []int{start}
		for len(pending) > 0 {
			u := pending[len(pending)-1]
			pending = pending[:len(pending)-1]
			if seen[u] {
				continue
			}
			seen[u] = true
			for _, v := range adj[u] {
				if !seen[v] {
					pending = append(pending, v)
				}
			}
		}
	}
	return count
}

function components(adj) {
  const seen = new Array(adj.length).fill(false);
  let count = 0;
  for (let start = 0; start < adj.length; start++) {
    if (seen[start]) continue;
    count++;
    const pending = [start];
    while (pending.length > 0) {
      const u = pending.pop();
      if (seen[u]) continue;
      seen[u] = true;
      for (const v of adj[u]) if (!seen[v]) pending.push(v);
    }
  }
  return count;
}

def components(adj: list[list[int]]) -> int:
    seen = [False] * len(adj)
    count = 0
    for start in range(len(adj)):
        if seen[start]:
            continue
        count += 1
        pending = [start]
        while pending:
            u = pending.pop()
            if seen[u]:
                continue
            seen[u] = True
            pending.extend(v for v in adj[u] if not seen[v])
    return count

List<Integer> kahn(List<List<Integer>> adj) {
    int n = adj.size();
    int[] indeg = new int[n];
    for (List<Integer> edges : adj) for (int v : edges) indeg[v]++;
    Deque<Integer> ready = new ArrayDeque<>();
    for (int v = 0; v < n; v++) if (indeg[v] == 0) ready.add(v);
    List<Integer> order = new ArrayList<>();
    while (!ready.isEmpty()) {
        int u = ready.poll();
        order.add(u);
        for (int v : adj.get(u)) if (--indeg[v] == 0) ready.add(v);
    }
    if (order.size() < n) throw new IllegalStateException("в зависимостях цикл");
    return order;
}

func kahn(adj [][]int) ([]int, error) {
	n := len(adj)
	indeg := make([]int, n)
	for _, edges := range adj {
		for _, v := range edges {
			indeg[v]++
		}
	}
	var ready []int
	for v := 0; v < n; v++ {
		if indeg[v] == 0 {
			ready = append(ready, v)
		}
	}
	order := make([]int, 0, n)
	for len(ready) > 0 {
		u := ready[0]
		ready = ready[1:]
		order = append(order, u)
		for _, v := range adj[u] {
			indeg[v]--
			if indeg[v] == 0 {
				ready = append(ready, v)
			}
		}
	}
	if len(order) < n {
		return nil, errors.New("в зависимостях цикл")
	}
	return order, nil
}

function kahn(adj) {
  const n = adj.length;
  const indeg = new Array(n).fill(0);
  for (const edges of adj) for (const v of edges) indeg[v]++;
  const ready = [];
  for (let v = 0; v < n; v++) if (indeg[v] === 0) ready.push(v);
  const order = [];
  let head = 0;
  while (head < ready.length) {
    const u = ready[head++];
    order.push(u);
    for (const v of adj[u]) if (--indeg[v] === 0) ready.push(v);
  }
  if (order.length < n) throw new Error("в зависимостях цикл");
  return order;
}

В стандартной библиотеке Python алгоритм Кана уже есть: graphlib.TopologicalSorter с версии 3.9 принимает словарь зависимостей и бросает CycleError, если порядок не собрать. Руками он выглядит так:

from collections import deque


def kahn(adj: list[list[int]]) -> list[int]:
    n = len(adj)
    indeg = [0] * n
    for edges in adj:
        for v in edges:
            indeg[v] += 1
    ready = deque(v for v in range(n) if indeg[v] == 0)
    order: list[int] = []
    while ready:
        u = ready.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                ready.append(v)
    if len(order) < n:
        raise ValueError("в зависимостях цикл")
    return order

boolean hasCycle(int u, List<List<Integer>> adj, int[] color) {
    color[u] = 1;                       // серая
    for (int v : adj.get(u)) {
        if (color[v] == 1) return true; // ребро назад в незавершённую вершину
        if (color[v] == 0 && hasCycle(v, adj, color)) return true;
    }
    color[u] = 2;                       // чёрная
    return false;
}

func hasCycle(u int, adj [][]int, color []int) bool {
	color[u] = 1 // серая
	for _, v := range adj[u] {
		if color[v] == 1 { // ребро назад в незавершённую вершину
			return true
		}
		if color[v] == 0 && hasCycle(v, adj, color) {
			return true
		}
	}
	color[u] = 2 // чёрная
	return false
}

function hasCycle(u, adj, color) {
  color[u] = 1;                        // серая
  for (const v of adj[u]) {
    if (color[v] === 1) return true;   // ребро назад в незавершённую вершину
    if (color[v] === 0 && hasCycle(v, adj, color)) return true;
  }
  color[u] = 2;                        // чёрная
  return false;
}

def has_cycle(u: int, adj: list[list[int]], color: list[int]) -> bool:
    color[u] = 1                          # серая
    for v in adj[u]:
        if color[v] == 1:                 # ребро назад в незавершённую вершину
            return True
        if color[v] == 0 and has_cycle(v, adj, color):
            return True
    color[u] = 2                          # чёрная
    return False

У остальных структур курса в стандартной библиотеке есть готовый класс. Граф — исключение: класса Graph в Java нет, собирать придётся самому. Не с нуля, а из готовых коллекций — и от того, какие взять, зависит реальная сложность обхода.

Список смежности — это Map из вершины в список её соседей; список для новой вершины заводит computeIfAbsent. HashMap находит список соседей за O(1) в среднем, ArrayList внутри — плотный массив, по которому цикл идёт без промахов кэша. Если вершины пронумерованы подряд (0…N−1), Map вообще не нужен: берут массив списков, и поиск соседей превращается в обращение по индексу.

Матрица смежности — это boolean[][]; каждая ячейка занимает байт, поэтому на ста тысячах вершин матрица попросит около десяти гигабайт. Отсюда и правило: матрица — только для маленьких плотных графов.

Оба обхода держатся на ArrayDeque: в ширину это очередь (addLast в конец, pollFirst с начала), в глубину — тот же класс как стек (push и pop). Внутри кольцевой массив, обе операции амортизированно O(1). LinkedList формально умеет то же самое, но платит отдельным объектом-узлом за каждый элемент. Stack не берут вообще: внутри у него синхронизированный Vector из первых версий Java.

Посещённые вершины держат в HashSet (O(1) в среднем), а при пронумерованных вершинах — в boolean[]: быстрее и без объектов-обёрток.

Грабля тут одна, зато обидная. Если вершина — ваш собственный класс без equals и hashCode, HashMap сравнивает вершины по ссылке. Две «одинаковые» вершины станут разными ключами, граф тихо распадётся на куски, а обход найдёт меньше, чем должен, — без исключения, просто неверный ответ. Вторая мелочь оттуда же: соседи хранят порядок добавления, а сами вершины при переборе Map выдаются в порядке корзин — когда важна воспроизводимость обхода, ключи держат в LinkedHashMap.

У остальных структур курса в стандартной библиотеке есть готовый тип. Граф — исключение: типа Graph в Go нет, собирать придётся самому. Не с нуля, а из среза и map — и от того, как их взять, зависит реальная сложность обхода.

Список смежности — это map[string][]string из вершины в срез её соседей; append к отсутствующему ключу работает сразу, потому что нулевой срез это nil, к которому можно добавлять. map находит соседей за O(1) в среднем, срез внутри — плотный массив, по которому цикл идёт без промахов кеша. Если вершины пронумерованы подряд (0…N−1), map вообще не нужен: берут [][]int, и поиск соседей превращается в обращение по индексу, как во фрагментах выше.

Матрица смежности — это [][]bool или один плоский []bool длиной N·N; каждая ячейка занимает байт, поэтому на ста тысячах вершин матрица попросит около десяти гигабайт. Отсюда и правило: матрица — только для маленьких плотных графов.

Оба обхода держатся на срезе: в глубину — как стек (append и s[:len(s)-1]), в ширину — как очередь с индексом головы или q[1:]. Обе операции амортизированно O(1). container/list формально умеет то же самое, но платит отдельным объектом-узлом и упаковкой в any за каждый элемент. Рекурсивный обход в глубину в Go безопаснее, чем в других языках, потому что стек горутины растёт, но на графе из пользовательских данных его всё равно переписывают циклом.

Посещённые вершины держат в map[string]bool или map[string]struct{} (O(1) в среднем), а при пронумерованных вершинах — в []bool: быстрее и без хеширования.

Грабля тут одна, зато обидная. Если вершина — ваша структура, ключом в map она годится, только пока все её поля сравнимы, и сравнивается по значению: две структуры с одинаковыми полями — один ключ. А вот map[*Vertex] сравнивает по адресу: две «одинаковые» вершины, созданные в разных местах, станут разными ключами, граф тихо распадётся на куски, а обход найдёт меньше, чем должен, — без ошибки, просто неверный ответ. Вторая мелочь оттуда же: соседи в срезе хранят порядок добавления, а сами вершины при переборе map выдаются в случайном порядке, каждый запуск в новом — когда важна воспроизводимость обхода, стартовые вершины сортируют, slices.Sorted(maps.Keys(graph)).

У остальных структур курса в стандартной библиотеке есть готовый класс. Граф — исключение: класса Graph в JavaScript нет, собирать придётся самому. Не с нуля, а из Map, Set и массивов — и от того, какие взять, зависит реальная сложность обхода.

Список смежности — это Map из вершины в массив её соседей; массив для новой вершины заводят при первом ребре. Map находит соседей за O(1) в среднем, массив внутри — плотный, пока в нём только числа или строки. Если вершины пронумерованы подряд (0…N−1), Map вообще не нужна: берут массив массивов, и поиск соседей превращается в обращение по индексу, как во фрагментах выше.

Матрица смежности — это массив массивов или один плоский Uint8Array длиной N·N; каждая ячейка занимает байт, поэтому на ста тысячах вершин матрица попросит около десяти гигабайт, больше, чем куча Node позволит. Отсюда и правило: матрица — только для маленьких плотных графов.

Оба обхода держатся на массиве, но с разной ценой: в глубину — как стек, push и pop, амортизированно O(1); в ширину — как очередь, и здесь shift стоит O(N), потому что сдвигает весь массив. На графе из десятка вершин, как в примере, это незаметно, на графе из миллиона обход становится квадратичным. Честная очередь — индекс головы по тому же массиву, как во фрагменте с путём выше, или пакет denque. Рекурсивный обход в глубину упирается в стек V8 на десятке тысяч вершин, поэтому на больших графах его переписывают циклом.

Посещённые вершины держат в Set (O(1) в среднем), а при пронумерованных вершинах — в массиве или Uint8Array: быстрее и без хеширования.

Грабля тут одна, зато обидная. Map и Set сравнивают объекты по ссылке: если вершина — ваш объект, две «одинаковые» вершины, созданные в разных местах, станут разными ключами, граф тихо распадётся на куски, а обход найдёт меньше, чем должен, — без исключения, просто неверный ответ. Ключом делают примитив: идентификатор или строку. Вторая мелочь: обычный объект {} вместо Map тянет прототип, и вершина с именем constructor «найдётся» в графе, куда её не клали; словарь вершин делают через Map или Object.create(null). Зато порядок обхода воспроизводим сам собой: и Map, и Set перебираются в порядке вставки.

У остальных структур курса в стандартной библиотеке есть готовый тип. Граф — исключение: класса Graph в Python нет, собирать придётся самому. Не с нуля, а из dict, list и set — и от того, какие взять, зависит реальная сложность обхода.

Список смежности — это dict из вершины в список её соседей; список для новой вершины сам заводит defaultdict(list). dict находит соседей за O(1) в среднем, список внутри — плотный массив ссылок. Если вершины пронумерованы подряд (0…N−1), dict вообще не нужен: берут список списков, и поиск соседей превращается в обращение по индексу, как во фрагментах выше.

Матрица смежности — это список списков или, чтобы не платить по 8 байт за ссылку на True, bytearray длиной N·N; каждая ячейка занимает байт, поэтому на ста тысячах вершин матрица попросит около десяти гигабайт. Отсюда и правило: матрица — только для маленьких плотных графов.

Оба обхода держатся на разных структурах: в глубину — обычный list как стек, append и pop(); в ширину — collections.deque с popleft, потому что list.pop(0) сдвигает весь список за O(N). Обе операции у своих структур амортизированно O(1). Рекурсивный обход в глубину в Python упирается в предел на тысяче вложенных вызовов, RecursionError, поэтому на графе больше нескольких сотен вершин его пишут циклом со своим стеком.

Посещённые вершины держат в set (O(1) в среднем), а при пронумерованных вершинах — в списке bool: быстрее и без хеширования.

Грабля тут одна, зато обидная. Если вершина — ваш собственный класс без __eq__ и __hash__, dict и set сравнивают вершины по адресу. Две «одинаковые» вершины станут разными ключами, граф тихо распадётся на куски, а обход найдёт меньше, чем должен, — без исключения, просто неверный ответ. Лечится @dataclass(frozen=True), который делает оба метода по полям. Зато порядок обхода воспроизводим почти сам собой: dict перебирается в порядке вставки; только set порядка не хранит, и для воспроизводимости стартовые вершины берут из dict, а не из set.

И одна готовая вещь всё-таки есть: топологическую сортировку по Кану стандартная библиотека умеет сама, graphlib.TopologicalSorter с версии 3.9, а для настоящей работы с графами берут networkx, где написаны и обходы, и кратчайшие пути, и компоненты.

• В Java класса Graph нет: список смежности собирают на HashMap, обход — на ArrayDeque, посещённые — в HashSet. Вершина-ключ без equals и hashCode тихо рвёт граф на куски.

• В Go типа Graph нет: список смежности это map[string][]string или [][]int, обходы на срезе, посещённые в map или []bool; ключ-указатель сравнивается по адресу и рвёт граф, а обход map идёт в случайном порядке.

• В JavaScript класса Graph нет: список смежности на Map, стек на массиве, очередь с индексом головы (shift это O(N)), посещённые в Set; объект-вершина сравнивается по ссылке, ключом делают идентификатор.

• В Python класса Graph нет: defaultdict(list), стек на list, очередь на deque, посещённые в set; вершина без __eq__ и __hash__ рвёт граф, рекурсивный обход упирается в предел тысячи вызовов; Кан готов в graphlib.