Неделя 7 — Графы и алгоритмы на графах

Примеры кода

1. Представление графа — список смежности:
```python
graph = {
"A": ["B", "C"],
"B": ["D"],
"C": ["E"],
"D": [],
"E": ["B"]
}
```

2. Поиск в глубину (DFS):
```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)
```

3. Поиск в ширину (BFS):
```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])
```

Практические упражнения

1. Реализуйте граф с использованием словаря списков смежности.
2. Напишите функцию для обхода графа в ширину (BFS).
3. Напишите функцию для обхода графа в глубину (DFS).
4. Реализуйте граф с циклом и проверьте, как работает DFS.

Задания на самостоятельную работу

1. Добавьте в граф веса рёбер и реализуйте вывод минимального веса между двумя вершинами (без поиска пути).
2. Напишите функцию, определяющую, связен ли граф.
3. Реализуйте граф с несколькими компонентами связности и напишите функцию, которая считает их количество.
4. Реализуйте функцию, которая ищет путь от одной вершины к другой.

Контрольные вопросы

1. Чем отличается BFS от DFS?
2. Что такое ориентированный граф?
3. Как можно представить граф в виде матрицы смежности?
4. Что такое компонент связности?
5. В каких задачах применяются графы?