🔑 Как создать матрицу смежности в Python: полное руководство для начинающих

Для создания матрицы смежности в Python вы можете использовать двумерный список. Каждый элемент списка будет представлять вершину графа, а значение элемента будет указывать на наличие или отсутствие ребра между вершинами.

# Создание матрицы смежности размером 5x5
matrix = [[0, 1, 1, 0, 0],
          [1, 0, 0, 1, 0],
          [1, 0, 0, 1, 1],
          [0, 1, 1, 0, 1],
          [0, 0, 1, 1, 0]]

В приведенном примере, матрица представляет граф из 5 вершин и значения 1 указывают на наличие ребер между соответствующими вершинами. Если ребра нет, то значение равно 0.

Как создать матрицу смежности в Python?

Матрица смежности - это графическое представление связей между вершинами в графе. В Python существует несколько способов создания матрицы смежности. В этой статье мы рассмотрим несколько примеров.

1. Создание пустой матрицы смежности

Если вам необходимо создать матрицу смежности для графа с заранее известным количеством вершин, вы можете использовать вложенные списки. Вначале мы создаем пустую матрицу, заполняя ее нулями или другими значениями, которые соответствуют отсутствию ребер между вершинами.

# Создаем пустую матрицу смежности
n = 4
matrix = [[0] * n for _ in range(n)]
print(matrix)
    

В этом примере мы создаем матрицу смежности размером 4x4 и заполняем ее нулями. Вы можете изменить значение переменной "n" для создания матрицы с другим размером.

2. Создание матрицы смежности из списка ребер

Если у вас уже есть список ребер, вы можете использовать его для создания матрицы смежности. В этом случае, мы сначала создаем пустую матрицу такого же размера, а затем заполняем ее значениями из списка ребер.

# Создаем пустую матрицу смежности
n = 4
matrix = [[0] * n for _ in range(n)]

# Задаем список ребер
edges = [(0, 1), (1, 2), (2, 3), (3, 0)]

# Заполняем матрицу значениями из списка ребер
for edge in edges:
    matrix[edge[0]][edge[1]] = 1
    matrix[edge[1]][edge[0]] = 1

print(matrix)
    

В этом примере мы создаем матрицу смежности размером 4x4 и заполняем ее значениями из списка ребер. Каждое ребро представлено кортежем, содержащим номера связанных вершин. Здесь мы присваиваем значения 1 для связанных вершин и 0 для отсутствия связи.

3. Создание матрицы смежности из взвешенного списка ребер

Если ваш граф имеет взвешенные ребра, вы можете использовать словарь или вложенные словари для создания матрицы смежности. Значения в словарях будут соответствовать весам ребер.

# Создаем пустую матрицу смежности
n = 4
matrix = [[0] * n for _ in range(n)]

# Задаем словарь с весами ребер
weighted_edges = {(0, 1): 2, (1, 2): 3, (2, 3): 1, (3, 0): 4}

# Заполняем матрицу значениями из словаря весов
for edge, weight in weighted_edges.items():
    matrix[edge[0]][edge[1]] = weight
    matrix[edge[1]][edge[0]] = weight

print(matrix)
    

В этом примере мы создаем матрицу смежности размером 4x4 и заполняем ее значениями из словаря весов. Каждое ребро представлено кортежем, содержащим номера связанных вершин, а значения соответствуют весам ребер.

Вывод

Матрица смежности является полезным инструментом для представления связей между вершинами в графе. В Python вы можете легко создать матрицу смежности с использованием вложенных списков или словарей. Представленные примеры помогут вам начать работу с матрицами смежности и использовать их для анализа графов и других связанных задач.