На седьмой неделе курса мы знакомимся с одной из самых универсальных структур данных — графами. Графы применяются при моделировании дорог, социальных сетей, компьютерных сетей, логистики и других задач. Мы изучим способы представления графов и базовые алгоритмы обработки графов: поиск в ширину и в глубину.
Граф состоит из узлов (вершин) и соединяющих их рёбер. Граф может быть:
- ориентированным или неориентированным;
- взвешенным или невзвешенным;
- циклическим или ациклическим.
1. Список смежности:
```python```
graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['E'],
'D': [],
'E': ['B']
}
2. Матрица смежности:
```python```
matrix = [
[0, 1, 1],
[0, 0, 1],
[1, 0, 0]
]
Алгоритм обхода графа, уходящий как можно глубже:
```python```
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
if node not in visited:
print(node)
visited.add(node)
for neighbor in graph[node]:
dfs(graph, neighbor, visited)
Обход графа слоями — полезен для поиска кратчайшего пути:
```python```
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
print(node)
visited.add(node)
queue.extend(graph[node])
- DFS и BFS — поиск и перебор;
- Поиск кратчайшего пути — алгоритм Дейкстры;
- Алгоритм Беллмана-Форда;
- Поиск компонент связности;
- Топологическая сортировка (для DAG).
- Социальные сети (друзья, подписки);
- Маршруты и навигация;
- Зависимости задач в системах сборки;
- Компьютерные игры (AI, карты);
- Анализ текста и рекомендаций.
1. Постройте граф на основе словаря и обойдите его с помощью DFS.
2. Реализуйте BFS для поиска кратчайшего пути от узла A до B.
3. Модифицируйте граф для учёта весов рёбер.