Граф (представления)

Граф — это множество вершин V и рёбер E. Два основных представления:

• Список смежности — для каждой вершины хранится список соседей. Память O(V + E), эффективен для разреженных графов.
• Матрица смежности — таблица V×V, где ячейка [i][j] показывает наличие ребра. Память O(V^2), проверка ребра за O(1), но расточительна для разреженных графов.

Большинство алгоритмов обхода предпочитают список смежности.

# Список смежности через словарь
graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D"],
    "D": [],
}
for v, neighbours in graph.items():
    print(v, "->", neighbours)