Модуль: Графы. Начало


Задача

3/13

Хранение взвешенных графов (Python)

Теория Нажмите, чтобы прочитать/скрыть

Взвешенный граф
 

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

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

  2. Список смежности. В этом способе каждая вершина представляется в виде списка, содержащего пары (или кортежи) вершин, с которыми она имеет ребра, и их соответствующие веса. Например, для вершины A список смежности может выглядеть как [(B, 5), (C, 3)], что означает наличие ребра с весом 5 к вершине B и ребра с весом 3 к вершине C.

  3. Список ребер: В этом способе граф представляется в виде списка всех его ребер, где каждое ребро содержит информацию о вершинах, которые оно соединяет, и его весе. Например, [(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' не имеет смежных ребер.

Попробуйте нарисовать на бумаге данный граф. 
 

Задача

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


time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Комментарий учителя

Вставьте недостающие фрагменты кода
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()

     

Результат проверки программы 

Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!