Графы
- Граф — это набор узлов (также называемых вершинами), соединенных ребрами (связями).
- Графы моделируют сети: друзья, дороги между городами, ссылки между веб-страницами.
- Дерево — это на самом деле особый случай графа; общий граф может иметь циклы и несколько связей для каждого узла.
Представление графа: список смежности
- Один из распространенных способов — это список смежности: словарь, сопоставляющий каждый узел со списком соседей.
graph["A"]— это список узлов, непосредственно соединенных сA.- Это компактно, когда у каждого узла лишь несколько соединений.
# A graph as a dict: each node maps to its list of neighbours
graph = {
"A": ["B", "C"],
"B": ["A"],
"C": ["A"],
}
print(graph["A"]) # ['B', 'C'] -- A connects to B and C
print(graph["B"]) # ['A']
Добавление ребра
- В неориентированном графе ребро
A—Bидет в обе стороны. - Поэтому добавление его означает добавление
Bк спискуAиAк спискуB. - Если узел новый, сначала начните его с пустого списка.
def add_edge(graph, a, b):
if a not in graph:
graph[a] = []
if b not in graph:
graph[b] = []
graph[a].append(b)
graph[b].append(a)
graph = {}
add_edge(graph, "A", "B")
add_edge(graph, "A", "C")
print(graph) # {'A': ['B', 'C'], 'B': ['A'], 'C': ['A']}
Обход соседей
- Чтобы исследовать от узла, вы читаете его список соседей и посещаете каждый из них.
- Узел, которого нет в графе, не имеет ни одного соседа — возвращайте пустой список, а не ошибку.
- Этот поиск соседей является первым шагом больших задач, таких как поиск всего графа.
Направленные против неориентированных
- В неориентированном графе ребро работает в обе стороны (дружба).
- В направленном графе ребро указывает только в одну сторону (односторонняя дорога, ссылка «подписаться»).
- Для ориентированных рёбер вы добавляете их только в одном направлении.
Распространенные ошибки
- Граф — это узлы, соединённые рёбрами; ребро может быть однонаправленным или двусторонним.
- Дерево — это граф без циклов — не путайте два этих понятия.
Теперь попробуйте сами
- Реализуйте операции со списком смежности:
add_edge,neighboursиcount_edges. - Каждое задание проверяет вашу функцию на небольшом графе.
- Нажмите Проверить ответ, чтобы протестировать её.
Сложность 5/5 · 400 монет + небольшой бонус за первое завершение сегодня
Напишите add_edge(graph, a, b) для неориентированного графа, представленного словарем списков соседей. Добавьте ⟨b⟩ в ⟨graph[a]⟩ и ⟨a⟩ в ⟨graph[b]⟩. Если узла еще нет в графе, сначала создайте для него пустой список ⟨[]⟩. Измените словарь на месте.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 5/5 · 400 монет + небольшой бонус за первое завершение сегодня
Напишите neighbours(graph, node), который возвращает список узлов, непосредственно связанных с node. Если node отсутствует в графе, верните пустой список [] (не вызывайте ошибку).
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 5/5 · 400 монет + небольшой бонус за первое завершение сегодня
Напишите count_edges(graph) для неориентированного графа: подсчитайте количество рёбер. Сложите длины списков всех соседей и разделите на 2 (каждое ребро хранится в списках обоих узлов). Пример: треугольник A–B–C имеет 3 рёбер.
Нажмите Запустить, чтобы увидеть результат здесь.