МАТРИЦА СМЕЖНОСТИ PYTHON

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

matrix = [ [0, 1, 1, 0], [1, 0, 1, 1], [1, 1, 0, 0], [0, 1, 0, 0]]

Здесь каждая строка массива представляет вершину графа, а значение true(1) в ячейке i,j означает наличие ребра между вершинами i и j. Также можно использовать словарь, где ключами будут вершины, а значениями - списки смежных вершин:

graph = { 'A': ['B', 'C'], 'B': ['A', 'C', 'D'], 'C': ['A', 'B'], 'D': ['B']}

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

Для работы с матрицами смежности в Python можно использовать различные алгоритмы для обхода графа, поиска кратчайшего пути и т.д. Например, алгоритм BFS (Breadth-First Search) позволяет обойти граф в ширину и найти кратчайший путь от одной вершины до другой:

def bfs(graph, start, end):   # создаем очередь и помещаем в нее начальную вершину   queue = [(start, [start])]     while queue:       # извлекаем вершину из очереди       (vertex, path) = queue.pop(0)       # если мы нашли искомую вершину, возвращаем путь к ней       if vertex == end:           return path              # иначе добавляем в очередь все смежные вершины       for adjacent in graph.get(vertex, []):           if adjacent not in path:               queue.append((adjacent, path + [adjacent]))

Здесь граф представлен в виде словаря, функция bfs возвращает кратчайший путь между двумя заданными вершинами.