3.
Хранение взвешенных графов (Python)
Взвешенный граф
Во взвешенном графе, помимо самих ребер и их направления, каждое ребро обладает также весом или стоимостью. Существует несколько способов хранения списка вершин во взвешенном графе:
-
Матрица смежности. В этом способе граф представляется в виде двумерной матрицы, где строки и столбцы соответствуют вершинам графа, а элементы матрицы содержат информацию о весе ребер между вершинами. Если между вершинами нет ребра, то соответствующий элемент матрицы будет иметь значение "бесконечность" или другое специальное значение.
-
Список смежности. В этом способе каждая вершина представляется в виде списка, содержащего пары (или кортежи) вершин, с которыми она имеет ребра, и их соответствующие веса. Например, для вершины A список смежности может выглядеть как [(B, 5), (C, 3)]
, что означает наличие ребра с весом 5 к вершине B и ребра с весом 3 к вершине C.
-
Список ребер: В этом способе граф представляется в виде списка всех его ребер, где каждое ребро содержит информацию о вершинах, которые оно соединяет, и его весе. Например, [(A, B, 5), (A, C, 3)]
.
Выбор способа хранения зависит от конкретных требований и задачи, с которой вы работаете. Некоторые способы могут быть более эффективными для определенных операций, таких как поиск кратчайшего пути или обход графа.
Пример хранения взвешенного графа в виде списка смежности на языке Python с использованием словаря, где ключ - это номер вершины, а значение - список кортежей (первый элемент кортежа представляет собой смежную вершину, второй элемент - вес ребра)
graph = { 'A': [('B', 3), ('C', 2)], 'B': [('C', 1)], 'C': [('D', 5)], 'D': [] }
В данном примере:
- Вершина
'A'
имеет два смежных ребра: одно соединяет ее с вершиной 'B'
с весом 3, а другое - с вершиной 'C'
с весом 2.
- Вершина
'B'
имеет одно смежное ребро, которое соединяет ее с вершиной 'C'
с весом 1.
- Вершина
'C'
имеет одно смежное ребро, которое соединяет ее с вершиной 'D'
с весом 5.
- Вершина
'D'
не имеет смежных ребер.
Попробуйте нарисовать на бумаге данный граф.
По заданному изображению ориентированного графа сформируйте список смежных вершин для всех вершин. Вершины добавляйте в порядке возрастания.
Вставьте недостающие фрагменты кода
Python
V = 4
adj = {i:[] for i in range(1, V+1)}
adj[1].append((2, 5))
# остальные ребра добавьте сами в порядке возрастания вершин
|
|
for k, v in adj.items():
print(k, end=": ")
for j in v:
print(f'-> {j[0]}({j[1]})', end='')
print()
|