Графы

Здравствуйте! Во время изучения пайтона я столкнулся с такой структурой как граф. Теория графов мне более-менее понятна.
Но вот реализация....
Абсолютно не могу понять как применять графы в задачах и вообще как создать граф в пайтоне. Помогите пожалуйста разобраться с этим
Можете привести пример как создать граф(без использования библиотек, т.к. для спортивного программирования используются только стандартные библиотеки, P.S. я знаю что с++ для таких задач лучше, но вот душа у меня лежит к пайтону) и пожалуйста с комментариями.
Я понимаю что могу просто заучить один из способов создания графа, но считаю это бесполезной практикой т к. понимаю что больше понимать я не стану(тавтология ).
Если знаете сайты и такие материалы похожие где всё могут объяснить кидайте ссылку.
Если знаете чаты в соц.сетях то тоже кидайте ссылку
P.S. мне 1 лет поэтому давайте обойдёмся без математики из университета.
Буду очень признателен за помощь, вы моя последняя надежда.

0

Простой и удобный способ задать граф в питоне: словарь, где ключи это вершины графа, а значения - список соседних вершин данного ключа.

2

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

2

Если наш граф это дерево, то у нас получится словарь с достаточно большой вложенностью т.к. каждая вершина там является тоже "родителем" для двух других.
Или я Опять что-то намудрил блин я что такой глупый?(

0

marat1928, Открой книгу "Грокаем алгоритмы", прочитай главы 6-7. Там как раз реализация на python. Для начального понимания, этого достаточно.

1

Спасибо, буду читать

0

Вот еще нашел книгу: Алгоритмы на графах. Использование языка Python О.И. Мельников, А.А. Морозов. 2022 г.
Сказать ничего не могу, не читал.

1

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

В стране, где Денис владеет магазинами, имеется n городов, соединённых m двунаправленными дорогами. Дорога с номером i соединяет города с номерами ui и vi и имеет длину li. Также в каждом городе либо есть магазин Дениса, либо нет. Расстоянием между двумя городами называется минимальная длина маршрута, требуемого для того, чтобы добраться из одного города в другой. Если между городами не существует маршрута, то расстояние между ними отсутствует.

Теперь Денис захотел для каждого города вывести расстояние до ближайшего города с магазином, либо «-1», если его нет.

Входные данные
Первая строка содержит два целых числа n и m (1≤n≤105,0≤m≤min(2∗105,n∗(n−1)2)) - количество городов и дорог соответственно.

Во второй строке находится n целых чисел ai (ai∈{0,1}). Если ai равно единице, то в городе i есть магазин, иначе ai равно нулю.

Далее в m строках содержатся три целых числа ui, vi и li (1≤ui,vi≤n,1≤li≤109,ui≠vi) - описание дорог.

Выходные данные
Выведите в строке n целых чисел t1,t2,...,tn, где ti — расстояние до ближайшего магазина.

Примеры
входные данные
4 2
1 0 0 1
1 2 4
2 3 7
выходные данные
0 4 11 0
входные данные
4 2
1 0 0 0
1 2 4
2 3 7
выходные данные
0 4 11 -1
Объясните как для такой задачи оформить граф

0

Чужие решения ничему вас не научат.

0

Я просто не могу понять как создавать граф когда вот так значения вводятся с клавиатуры.

Добавлено через 44 секунды
Мне решение задачи и не надо сам хочу ее решить,я просто хочу разобраться как вводить вот так граф

0

marat1928, ну ты начни. выложи код свой.

0

Сообщение от marat1928 Я просто не могу понять как создавать граф когда вот так значения вводятся с клавиатуры

marat1928, вам дается напрямую матрица смежности.

0

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

0

Можно и через словарь. Ключи - вершины, а значения - словарь с ключами - соседями, а значениями - весом ребер.
Вот пример ориентированного взвешенного графа:

0

Спасибо.
Осталось попробовать самому сделать такую штуку при введении с клавиатуры значения.

0

Вершины здесь обозначены литерами для наглядности, по факту лучше конечно обозначать числами

Добавлено через 28 секунд

Сообщение от marat1928 Осталось попробовать самому сделать такую штуку при введении с клавиатуры значения.

Это несложно

1

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

0

marat1928, алгоритм Дийкстры не работает с циклами отрицательной длины. Это совсем другое.

1

Аааа понял, буду пробовать, спасибо!

Добавлено через 50 секунд
Если я потом скину решение или его части, сможешь указать на ошибки или то, как сделать было лучше?

0

Сообщение от marat1928 Если я потом скину решение или его части, сможешь указать на ошибки или то, как сделать было лучше?

без проблем

0