Graphs · Графы
Graphs
- A graph is a set of nodes (also called vertices) joined by edges (connections).
- Graphs model networks: friends, roads between cities, links between web pages.
- A tree is really a special graph; a general graph can have cycles and many links per node.
Графы
- Граф — это набор узлов (также называемых вершинами), соединенных ребрами (связями).
- Графы моделируют сети: друзья, дороги между городами, ссылки между веб-страницами.
- Дерево — это на самом деле особый случай графа; общий граф может иметь циклы и несколько связей для каждого узла.
Representing a graph: adjacency list
- One common way is an adjacency list: a dictionary mapping each node to its list of neighbours.
graph["A"]is the list of nodes directly connected toA.- This is compact when each node has only a few connections.
Представление графа: список смежности
- Один из распространенных способов — это список смежности: словарь, сопоставляющий каждый узел со списком соседей.
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']
Adding an edge
- In an undirected graph, an edge
A—Bgoes both ways. - So adding it means appending
BtoA's list andAtoB's list. - If a node is new, start it with an empty list first.
Добавление ребра
- В неориентированном графе ребро
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']}
Walking the neighbours
- To explore from a node, you read its neighbour list and visit each one.
- A node that is not in the graph has no neighbours — return an empty list, not an error.
- This neighbour lookup is the first step of bigger jobs like searching the whole graph.
Обход соседей
- Чтобы исследовать от узла, вы читаете его список соседей и посещаете каждый из них.
- Узел, которого нет в графе, не имеет ни одного соседа — возвращайте пустой список, а не ошибку.
- Этот поиск соседей является первым шагом больших задач, таких как поиск всего графа.
Directed vs undirected
- In an undirected graph an edge works both ways (a friendship).
- In a directed graph an edge points one way only (a one-way street, a "follows" link).
- For directed edges you would append in one direction only.
Направленные против неориентированных
- В неориентированном графе ребро работает в обе стороны (дружба).
- В направленном графе ребро указывает только в одну сторону (односторонняя дорога, ссылка «подписаться»).
- Для ориентированных рёбер вы добавляете их только в одном направлении.
Common mistakes
- A graph is nodes joined by edges; an edge can be one-way or two-way.
- A tree is a graph with no cycles — do not confuse the two.
Распространенные ошибки
- Граф — это узлы, соединённые рёбрами; ребро может быть однонаправленным или двусторонним.
- Дерево — это граф без циклов — не путайте два этих понятия.
Now you try
- Build the adjacency-list operations:
add_edge,neighbours, andcount_edges. - Each task checks your function on a small graph.
- Press Check answer to test it.
Теперь попробуйте сами
- Реализуйте операции со списком смежности:
add_edge,neighboursиcount_edges. - Каждое задание проверяет вашу функцию на небольшом графе.
- Нажмите Проверить ответ, чтобы протестировать её.
Write add_edge(graph, a, b) for an undirected graph stored as a dict of neighbour lists. Append b to graph[a] and a to graph[b]. If a node is not in the graph yet, give it an empty list [] first. Change the dict in place. · Напишите add_edge(graph, a, b) для неориентированного графа, представленного словарем списков соседей. Добавьте ⟨b⟩ в ⟨graph[a]⟩ и ⟨a⟩ в ⟨graph[b]⟩. Если узла еще нет в графе, сначала создайте для него пустой список ⟨[]⟩. Измените словарь на месте.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
Write neighbours(graph, node) that returns the list of nodes directly connected to node. If node is not in the graph, return an empty list [] (do not raise an error). · Напишите neighbours(graph, node), который возвращает список узлов, непосредственно связанных с node. Если node отсутствует в графе, верните пустой список [] (не вызывайте ошибку).
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
Write count_edges(graph) for an undirected graph: count how many edges it has. Add up the lengths of every neighbour list, then divide by 2 (each edge is stored in both nodes' lists). Example: a triangle A–B–C has 3 edges. · Напишите count_edges(graph) для неориентированного графа: подсчитайте количество рёбер. Сложите длины списков всех соседей и разделите на 2 (каждое ребро хранится в списках обоих узлов). Пример: треугольник A–B–C имеет 3 рёбер.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.