По направлению рёбер
По весу рёбер
По наличию циклов
(0) --10-- (1)
| \ / |
5 6 4 | <-- Ребро(0,1) вес 10, Ребро(0,4) вес 5, ...
| \ / | (Цифры в скобках - вершины)
(4) --8-- (2)
\ /
7 3
\ /
(3)num_vertices = 5
# Инициализация матрицы нулями
adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]
edges = [(0, 1), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (3, 4)]
for u, v in edges:
adj_matrix[u][v] = 1
adj_matrix[v][u] = 1 # Симметрично для неориентированного
print("Матрица смежности:")
for row in adj_matrix:
print(row)
# Пример вывода:
# [0, 1, 0, 0, 1]
# [1, 0, 1, 1, 1]
# [0, 1, 0, 1, 0]
# [0, 1, 1, 0, 1]
# [1, 1, 0, 1, 0]
# Проверка ребра (1, 4): O(1)
print(f"\nРебро (1, 4) существует? {'Да' if adj_matrix[1][4] == 1 else 'Нет'}")from collections import defaultdict
# Используем defaultdict(list)
adj_list = defaultdict(list)
edges = [(0, 1), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (3, 4)]
# Заполняем список смежности
for u, v in edges:
adj_list[u].append(v)
adj_list[v].append(u) # Для неориентированного графа
print("Список смежности:")
# Выводим содержимое словаря
for vertex in sorted(adj_list.keys()): # Сортируем ключи для предсказуемого вывода
print(f"Вершина {vertex}: {sorted(adj_list[vertex])}") # Сортируем соседей для наглядности
# Пример вывода:
# Вершина 0: [1, 4]
# Вершина 1: [0, 2, 3, 4]
# Вершина 2: [1, 3]
# Вершина 3: [1, 2, 4]
# Вершина 4: [0, 1, 3]
# Получение соседей вершины 1: O(1) в среднем для словаря
print(f"\nСоседи вершины 1: {adj_list[1]}")
# Проверка ребра (1, 4): O(k), где k - степень вершины 1
print(f"Ребро (1, 4) существует? {'Да' if 4 in adj_list[1] else 'Нет'}")Матрица смежности
Список смежности
Вывод
В большинстве случаев для Python выбирайте список смежности. Матрицу смежности стоит рассматривать только при специфических требованиях к плотным графам или O(1) проверке рёбер.
from collections import defaultdict, deque
class Graph:
def __init__(self):
self.graph = defaultdict(list) # Список смежности
def add_edge(self, u, v, is_directed=False):
"""Добавляет ребро между u и v."""
self.graph[u].append(v)
if not is_directed:
self.graph[v].append(u) # Для неориентированного
def bfs(self, start_node):
"""Выполняет BFS графа, начиная с start_node."""
if start_node not in self.graph:
print(f"Стартовая вершина {start_node} отсутствует.")
return []
visited = {start_node} # Используем set для O(1) проверки
queue = deque([start_node])
result_order = [] # Список для хранения порядка обхода
while queue:
current_node = queue.popleft()
result_order.append(current_node) # Обрабатываем
for neighbor in self.graph[current_node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
print(f"BFS от {start_node}: {result_order}")
return result_order
# --- Создаем граф (ориентированный) ---
# 0 -> 1, 0 -> 2
# 1 -> 2
# 2 -> 0, 2 -> 3
# 3 -> 3
g_bfs = Graph()
g_bfs.add_edge(0, 1, is_directed=True)
g_bfs.add_edge(0, 2, is_directed=True)
g_bfs.add_edge(1, 2, is_directed=True)
g_bfs.add_edge(2, 0, is_directed=True) # Цикл!
g_bfs.add_edge(2, 3, is_directed=True)
g_bfs.add_edge(3, 3, is_directed=True) # Петля!
-
g_bfs.bfs(2)
# Ожидаемый вывод: BFS от 2: [2, 0, 3, 1]from collections import defaultdict
class Graph: # Используем тот же класс, что и для BFS
def __init__(self):
self.graph = defaultdict(list)
self.dfs_result_order = [] # Для хранения результата обхода
def add_edge(self, u, v, is_directed=False):
self.graph[u].append(v)
if not is_directed:
self.graph[v].append(u)
# Вспомогательная рекурсивная функция
def _dfs_recursive(self, vertex, visited):
visited.add(vertex) # 1. Пометить
self.dfs_result_order.append(vertex) # 2. Обработать
# 3. Для каждого соседа
for neighbor in self.graph[vertex]:
# 4. Если не посещен
if neighbor not in visited:
# 5. Рекурсивный вызов
self._dfs_recursive(neighbor, visited)
def dfs(self, start_node):
"""Выполняет DFS графа, начиная с start_node."""
if start_node not in self.graph:
print(f"Стартовая вершина {start_node} отсутствует.")
return []
visited = set()
self.dfs_result_order = [] # Очищаем результат перед новым обходом
self._dfs_recursive(start_node, visited) # Запускаем рекурсию
print(f"DFS от {start_node}: {self.dfs_result_order}")
return self.dfs_result_order
g_dfs = Graph()
g_dfs.add_edge(0, 1, is_directed=True); g_dfs.add_edge(0, 2, is_directed=True)
g_dfs.add_edge(1, 2, is_directed=True)
g_dfs.add_edge(2, 0, is_directed=True) # Цикл 0-2-0
g_dfs.add_edge(2, 3, is_directed=True)
g_dfs.add_edge(3, 3, is_directed=True) # Петля
g_dfs.dfs(2)
# DFS от 2: [2, 0, 1, 3]
# (Порядок может отличаться от BFS, т.к. DFS уходит вглубь: 2 -> 0 -> 1, затем возвращается и идет 2 -> 3)Понимание внутреннего устройства, асимптотической сложности (Big O) и алгоритмов работы с ними — это не академическая прихоть, а фундамент для написания по-настоящему эффективного, масштабируемого и элегантного кода на Python.
Знание алгоритмов и структур данных позволяет вам не просто решать задачи, а решать их правильно.