← Назад к курсу
20 простых задач на графы с решениями на Python
1. Построение графа (списка смежности)
Задача: Создать неориентированный граф с использованием списка смежности.
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.adj_list = [[] for _ in range(num_vertices)]
def add_edge(self, u, v):
"""Добавление ребра между вершинами u и v"""
self.adj_list[u].append(v)
self.adj_list[v].append(u) # Для неориентированного графа
def print_graph(self):
"""Вывод графа"""
for i in range(self.num_vertices):
print(f"Вершина {i}: {self.adj_list[i]}")
# Пример использования
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.print_graph()
2. Обход в глубину (DFS)
Задача: Реализовать обход графа в глубину.
def dfs(graph, start, visited=None):
"""Обход графа в глубину с использованием рекурсии"""
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
# Рекурсивно посещаем всех соседей
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
return visited
# Пример использования
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 5],
3: [1],
4: [1],
5: [2]
}
print("DFS обход:")
dfs(graph, 0)
3. Обход в ширину (BFS)
Задача: Реализовать обход графа в ширину.
from collections import deque
def bfs(graph, start):
"""Обход графа в ширину с использованием очереди"""
visited = set()
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
print(vertex, end=' ')
# Добавляем всех непосещенных соседей в очередь
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# Пример использования
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 5],
3: [1],
4: [1],
5: [2]
}
print("\nBFS обход:")
bfs(graph, 0)
4. Проверка связности графа
Задача: Проверить, является ли граф связным.
def is_connected(graph):
"""Проверка связности графа с помощью DFS"""
if not graph:
return True
visited = set()
# Начинаем с первой вершины
start_vertex = next(iter(graph))
stack = [start_vertex]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
# Добавляем всех соседей
stack.extend(graph[vertex])
# Проверяем, все ли вершины посещены
return len(visited) == len(graph)
# Пример использования
connected_graph = {
0: [1, 2],
1: [0, 3],
2: [0],
3: [1]
}
disconnected_graph = {
0: [1],
1: [0],
2: [3],
3: [2]
}
print(f"Граф 1 связный: {is_connected(connected_graph)}")
print(f"Граф 2 связный: {is_connected(disconnected_graph)}")
5. Поиск кратчайшего пути в невзвешенном графе
Задача: Найти кратчайший путь между двумя вершинами.
from collections import deque
def shortest_path_bfs(graph, start, end):
"""Поиск кратчайшего пути с помощью BFS"""
if start == end:
return [start]
visited = set()
queue = deque([start])
visited.add(start)
parent = {start: None}
while queue:
vertex = queue.popleft()
# Если нашли целевую вершину
if vertex == end:
# Восстанавливаем путь
path = []
while vertex is not None:
path.append(vertex)
vertex = parent[vertex]
return path[::-1]
# Добавляем соседей
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
parent[neighbor] = vertex
queue.append(neighbor)
return None # Путь не найден
# Пример использования
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 5],
3: [1],
4: [1, 5],
5: [2, 4]
}
path = shortest_path_bfs(graph, 0, 5)
print(f"Кратчайший путь: {path}")
6. Поиск цикла в графе
Задача: Обнаружить наличие цикла в неориентированном графе.
def has_cycle_undirected(graph):
"""Поиск цикла в неориентированном графе с помощью DFS"""
visited = set()
def dfs(node, parent):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
if dfs(neighbor, node):
return True
elif neighbor != parent:
# Нашли ребро к уже посещенной вершине (не родителю)
return True
return False
# Проверяем все компоненты связности
for vertex in graph:
if vertex not in visited:
if dfs(vertex, -1):
return True
return False
# Пример использования
graph_with_cycle = {
0: [1, 2],
1: [0, 2],
2: [0, 1, 3],
3: [2]
}
graph_without_cycle = {
0: [1],
1: [0, 2],
2: [1, 3],
3: [2]
}
print(f"Граф 1 содержит цикл: {has_cycle_undirected(graph_with_cycle)}")
print(f"Граф 2 содержит цикл: {has_cycle_undirected(graph_without_cycle)}")
7. Подсчет компонент связности
Задача: Подсчитать количество компонент связности в графе.
def count_connected_components(graph):
"""Подсчет компонент связности с помощью DFS"""
visited = set()
count = 0
def dfs(node):
"""Вспомогательная функция DFS"""
stack = [node]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
# Добавляем всех соседей
stack.extend(graph[vertex])
# Обрабатываем все вершины
for vertex in graph:
if vertex not in visited:
dfs(vertex)
count += 1
return count
# Пример использования
graph = {
0: [1, 2],
1: [0, 2],
2: [0, 1],
3: [4],
4: [3],
5: []
}
print(f"Количество компонент связности: {count_connected_components(graph)}")
8. Топологическая сортировка (для DAG)
Задача: Выполнить топологическую сортировку ориентированного ациклического графа.
def topological_sort(graph):
"""Топологическая сортировка с использованием DFS"""
visited = set()
stack = []
def dfs(node):
"""Вспомогательная функция DFS"""
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
dfs(neighbor)
stack.append(node)
# Запускаем DFS для всех вершин
for vertex in graph:
if vertex not in visited:
dfs(vertex)
# Возвращаем обратный порядок
return stack[::-1]
# Пример использования
dag = {
0: [1, 2],
1: [3],
2: [3],
3: [4],
4: []
}
print("Топологическая сортировка:")
print(topological_sort(dag))
9. Поиск мостов в графе
Задача: Найти все мосты (ребра, удаление которых увеличивает количество компонент связности).
def find_bridges(graph):
"""Поиск мостов в графе с использованием алгоритма Тарьяна"""
time = 0
visited = set()
disc = {} # Время обнаружения
low = {} # Минимальное время достижимости
parent = {}
bridges = []
def dfs(u):
nonlocal time
visited.add(u)
disc[u] = low[u] = time
time += 1
for v in graph[u]:
if v not in visited:
parent[v] = u
dfs(v)
# Обновляем low значение для u
low[u] = min(low[u], low[v])
# Если low[v] > disc[u], то (u, v) - мост
if low[v] > disc[u]:
bridges.append((u, v))
elif v != parent.get(u): # Обратное ребро
low[u] = min(low[u], disc[v])
# Запускаем DFS для всех вершин
for vertex in graph:
if vertex not in visited:
dfs(vertex)
return bridges
# Пример использования
graph = {
0: [1, 2],
1: [0, 2],
2: [0, 1, 3],
3: [2, 4],
4: [3, 5],
5: [4]
}
bridges = find_bridges(graph)
print(f"Мосты в графе: {bridges}")
10. Алгоритм Дейкстры
Задача: Найти кратчайшие пути от начальной вершины до всех остальных во взвешенном графе.
import heapq
def dijkstra(graph, start):
"""Алгоритм Дейкстры для поиска кратчайших путей"""
distances = {vertex: float('inf') for vertex in graph}
distances[start] = 0
pq = [(0, start)] # Приоритетная очередь (расстояние, вершина)
visited = set()
while pq:
current_dist, current_vertex = heapq.heappop(pq)
if current_vertex in visited:
continue
visited.add(current_vertex)
# Обновляем расстояния до соседей
for neighbor, weight in graph[current_vertex]:
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
# Пример использования
weighted_graph = {
0: [(1, 4), (2, 1)],
1: [(3, 1)],
2: [(1, 2), (3, 5)],
3: [(4, 3)],
4: []
}
distances = dijkstra(weighted_graph, 0)
print("Кратчайшие расстояния от вершины 0:")
for vertex, distance in distances.items():
print(f"До вершины {vertex}: {distance}")
11. Поиск эйлерова пути
Задача: Проверить, существует ли эйлеров путь в графе.
def has_eulerian_path(graph):
"""Проверка существования эйлерова пути"""
# Считаем степени вершин
degrees = {vertex: 0 for vertex in graph}
for vertex in graph:
degrees[vertex] = len(graph[vertex])
# Подсчитываем вершины с нечетной степенью
odd_degree_count = 0
for degree in degrees.values():
if degree % 2 != 0:
odd_degree_count += 1
# Эйлеров путь существует если:
# 0 нечетных вершин (эйлеров цикл) или 2 нечетных вершины (эйлеров путь)
return odd_degree_count in [0, 2]
# Пример использования
graph_euler = {
0: [1, 2],
1: [0, 2],
2: [0, 1, 3, 4],
3: [2, 4],
4: [2, 3]
}
graph_non_euler = {
0: [1],
1: [0, 2, 3],
2: [1],
3: [1, 4],
4: [3]
}
print(f"Граф 1 имеет эйлеров путь: {has_eulerian_path(graph_euler)}")
print(f"Граф 2 имеет эйлеров путь: {has_eulerian_path(graph_non_euler)}")
12. Проверка двудольности графа
Задача: Проверить, является ли граф двудольным.
def is_bipartite(graph):
"""Проверка двудольности графа с помощью раскраски"""
color = {}
for vertex in graph:
if vertex not in color:
# Начинаем BFS с текущей вершины
queue = [vertex]
color[vertex] = 0 # Красим в цвет 0
while queue:
u = queue.pop(0)
for v in graph[u]:
if v not in color:
# Красим соседа в противоположный цвет
color[v] = 1 - color[u]
queue.append(v)
elif color[v] == color[u]:
# Нашли конфликт
return False
return True
# Пример использования
bipartite_graph = {
0: [1, 3],
1: [0, 2],
2: [1, 3],
3: [0, 2]
}
non_bipartite_graph = {
0: [1, 2, 3],
1: [0, 2],
2: [0, 1],
3: [0]
}
print(f"Граф 1 двудольный: {is_bipartite(bipartite_graph)}")
print(f"Граф 2 двудольный: {is_bipartite(non_bipartite_graph)}")
13. Поиск компонент сильной связности (алгоритм Косарайю)
Задача: Найти компоненты сильной связности в ориентированном графе.
def kosaraju(graph):
"""Алгоритм Косарайю для поиска компонент сильной связности"""
visited = set()
stack = []
# Первый проход DFS для заполнения стека
def dfs_first(u):
visited.add(u)
for v in graph.get(u, []):
if v not in visited:
dfs_first(v)
stack.append(u)
# Запускаем первый проход
for vertex in graph:
if vertex not in visited:
dfs_first(vertex)
# Транспонируем граф
transposed = {vertex: [] for vertex in graph}
for u in graph:
for v in graph[u]:
transposed[v].append(u)
# Второй проход DFS в транспонированном графе
visited.clear()
sccs = []
def dfs_second(u, component):
visited.add(u)
component.append(u)
for v in transposed[u]:
if v not in visited:
dfs_second(v, component)
# Обрабатываем вершины в порядке убывания времени выхода
while stack:
vertex = stack.pop()
if vertex not in visited:
component = []
dfs_second(vertex, component)
sccs.append(component)
return sccs
# Пример использования
directed_graph = {
0: [1],
1: [2],
2: [0, 3],
3: [4],
4: [5, 7],
5: [6],
6: [4, 7],
7: []
}
scc = kosaraju(directed_graph)
print("Компоненты сильной связности:")
for i, component in enumerate(scc):
print(f"Компонента {i}: {component}")
14. Минимальное остовное дерево (алгоритм Прима)
Задача: Найти минимальное остовное дерево во взвешенном неориентированном графе.
import heapq
def prim_mst(graph):
"""Алгоритм Прима для поиска минимального остовного дерева"""
if not graph:
return []
# Начинаем с произвольной вершины
start_vertex = next(iter(graph))
visited = set([start_vertex])
mst_edges = []
edges = []
# Добавляем все ребра из начальной вершины
for neighbor, weight in graph[start_vertex]:
heapq.heappush(edges, (weight, start_vertex, neighbor))
while edges and len(visited) < len(graph):
weight, u, v = heapq.heappop(edges)
if v not in visited:
visited.add(v)
mst_edges.append((u, v, weight))
# Добавляем ребра из новой вершины
for neighbor, w in graph[v]:
if neighbor not in visited:
heapq.heappush(edges, (w, v, neighbor))
return mst_edges
# Пример использования
weighted_undirected_graph = {
0: [(1, 2), (3, 6)],
1: [(0, 2), (2, 3), (3, 8), (4, 5)],
2: [(1, 3), (4, 7)],
3: [(0, 6), (1, 8), (4, 9)],
4: [(1, 5), (2, 7), (3, 9)]
}
mst = prim_mst(weighted_undirected_graph)
print("Ребра минимального остовного дерева:")
for u, v, w in mst:
print(f"{u} - {v}: {w}")
15. Поиск в глубину с временными метками
Задача: Реализовать DFS с вычислением времени входа и выхода.
def dfs_with_timestamps(graph):
"""DFS с вычислением времени входа и выхода"""
visited = set()
time = 0
entry_time = {}
exit_time = {}
def dfs(u):
nonlocal time
visited.add(u)
entry_time[u] = time
time += 1
for v in graph.get(u, []):
if v not in visited:
dfs(v)
exit_time[u] = time
time += 1
# Запускаем DFS для всех вершин
for vertex in graph:
if vertex not in visited:
dfs(vertex)
return entry_time, exit_time
# Пример использования
graph = {
0: [1, 2],
1: [3, 4],
2: [5],
3: [],
4: [],
5: []
}
entry, exit_ = dfs_with_timestamps(graph)
print("Время входа и выхода:")
for vertex in graph:
print(f"Вершина {vertex}: вход={entry[vertex]}, выход={exit_[vertex]}")
16. Поиск гамильтонова пути
Задача: Проверить существование гамильтонова пути (проходит через все вершины по одному разу).
def hamiltonian_path_exists(graph):
"""Проверка существования гамильтонова пути с помощью backtracking"""
n = len(graph)
if n == 0:
return False
def backtrack(path, visited):
# Если путь содержит все вершины
if len(path) == n:
return True
current = path[-1]
for neighbor in graph.get(current, []):
if neighbor not in visited:
visited.add(neighbor)
path.append(neighbor)
if backtrack(path, visited):
return True
# Backtrack
path.pop()
visited.remove(neighbor)
return False
# Пробуем начать с каждой вершины
for start_vertex in graph:
if backtrack([start_vertex], {start_vertex}):
return True
return False
# Пример использования
graph_with_hamiltonian = {
0: [1, 2, 3],
1: [0, 2],
2: [0, 1, 3, 4],
3: [0, 2, 4],
4: [2, 3]
}
graph_without_hamiltonian = {
0: [1],
1: [0, 2],
2: [1],
3: [4],
4: [3]
}
print(f"Граф 1 имеет гамильтонов путь: {hamiltonian_path_exists(graph_with_hamiltonian)}")
print(f"Граф 2 имеет гамильтонов путь: {hamiltonian_path_exists(graph_without_hamiltonian)}")
17. Центр дерева
Задача: Найти центр(ы) дерева (вершины с минимальной эксцентриситетом).
from collections import deque
def find_tree_center(tree):
"""Нахождение центра дерева с использованием обрезки листьев"""
if not tree:
return []
n = len(tree)
degree = {vertex: 0 for vertex in tree}
leaves = deque()
# Вычисляем степени вершин и находим листья
for vertex in tree:
degree[vertex] = len(tree[vertex])
if degree[vertex] <= 1:
leaves.append(vertex)
# Обрезаем листья пока не останется 1 или 2 вершины
remaining_nodes = n
while remaining_nodes > 2:
leaves_count = len(leaves)
remaining_nodes -= leaves_count
for _ in range(leaves_count):
leaf = leaves.popleft()
# Уменьшаем степень соседей
for neighbor in tree[leaf]:
degree[neighbor] -= 1
if degree[neighbor] == 1:
leaves.append(neighbor)
return list(leaves)
# Пример использования
tree = {
0: [1],
1: [0, 2, 4],
2: [1, 3],
3: [2],
4: [1, 5],
5: [4]
}
centers = find_tree_center(tree)
print(f"Центр(ы) дерева: {centers}")
18. Подсчет путей между вершинами
Задача: Подсчитать количество путей между двумя вершинами.
def count_paths(graph, start, end):
"""Подсчет количества путей между вершинами с помощью DFS"""
count = 0
def dfs(current, visited):
nonlocal count
if current == end:
count += 1
return
visited.add(current)
for neighbor in graph.get(current, []):
if neighbor not in visited:
dfs(neighbor, visited.copy())
dfs(start, set())
return count
# Пример использования
graph = {
0: [1, 2],
1: [2, 3],
2: [3],
3: []
}
paths_count = count_paths(graph, 0, 3)
print(f"Количество путей от 0 до 3: {paths_count}")
19. Проверка на дерево
Задача: Проверить, является ли граф деревом.
def is_tree(graph):
"""Проверка, является ли граф деревом"""
if not graph:
return True
visited = set()
# Проверяем наличие циклов
def has_cycle(node, parent):
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
if has_cycle(neighbor, node):
return True
elif neighbor != parent:
return True
return False
# Проверяем связность и отсутствие циклов
start = next(iter(graph))
if has_cycle(start, -1):
return False
# Проверяем, все ли вершины посещены
return len(visited) == len(graph)
# Пример использования
tree_graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0],
3: [1],
4: [1]
}
non_tree_graph = {
0: [1, 2],
1: [0, 2],
2: [0, 1]
}
print(f"Граф 1 является деревом: {is_tree(tree_graph)}")
print(f"Граф 2 является деревом: {is_tree(non_tree_graph)}")
20. Поиск диаметра дерева
Задача: Найти диаметр дерева (самый длинный путь между двумя вершинами).
from collections import deque
def tree_diameter(tree):
"""Нахождение диаметра дерева с помощью двух BFS"""
if not tree:
return 0
def bfs_farthest(start):
"""BFS для нахождения самой дальней вершины и расстояния"""
visited = set([start])
queue = deque([(start, 0)]) # (вершина, расстояние)
farthest_node = start
max_distance = 0
while queue:
node, distance = queue.popleft()
if distance > max_distance:
max_distance = distance
farthest_node = node
for neighbor in tree.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, distance + 1))
return farthest_node, max_distance
# Первый BFS для нахождения одной из конечных вершин диаметра
farthest1, _ = bfs_farthest(next(iter(tree)))
# Второй BFS для нахождения диаметра
_, diameter = bfs_farthest(farthest1)
return diameter
# Пример использования
tree = {
0: [1],
1: [0, 2, 3],
2: [1, 4, 5],
3: [1],
4: [2],
5: [2, 6],
6: [5]
}
diameter = tree_diameter(tree)
print(f"Диаметр дерева: {diameter}")
Ключевые концепции, используемые в задачах:
- Способы представления графов: списки смежности, матрицы смежности
- Алгоритмы обхода: DFS (глубина), BFS (ширина)
- Алгоритмы поиска путей: Дейкстра, BFS для невзвешенных графов
- Специальные типы графов: деревья, двудольные графы
- Структурный анализ: компоненты связности, мосты, циклы
- Оптимизационные задачи: минимальное остовное дерево
- Сортировка и упорядочение: топологическая сортировка
Эти задачи покрывают основные концепции теории графов и помогут освоить базовые алгоритмы для работы с графами в Python.