Форум на Исходниках.RU

Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3875020 Wed, 31 Aug 2022 06:01:37 +0000 Список смежности для графа, для графа с петлями и мультиграфа https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3875020 я об этом и писал раньше, что ты по делу заметил эту хрень с петлей

в общем всем спс. за науку ;)

зы: со списком смежности надо разбираться конкретно с каждой задачей, адаптируя под данные - к такому выводу пришел...может это ошибочно, но пока такой вывод]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874998 Tue, 30 Aug 2022 17:47:07 +0000 Список смежности для графа, для графа с петлями и мультиграфа https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874998 AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874973 Tue, 30 Aug 2022 12:47:36 +0000 Список смежности для графа, для графа с петлями и мультиграфа https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874973 Цитата Akina @ 30.08.22, 04:36

Не списка, а списка для узла, т.е. длина списка смежных вершин в одной строке списка смежности.

А, ну тогда да, все верно.]]> Majestio Алгоритмы https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874939 Tue, 30 Aug 2022 04:36:50 +0000 Список смежности для графа, для графа с петлями и мультиграфа https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874939 Цитата Majestio @ 29.08.22, 18:57

И тут неверно. Длина списка равна просто количеству вершин

Не списка, а списка для узла, т.е. длина списка смежных вершин в одной строке списка смежности.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874938 Tue, 30 Aug 2022 04:08:48 +0000 Список смежности для графа, для графа с петлями и мультиграфа https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874938 Цитата FasterHarder @ 30.08.22, 03:55

еще пример ТОЛЬКО на петли:

a: a(*)

a: a

a: a(*), a(*)

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

Добавлено 30.08.22, 04:10

Цитата FasterHarder @ 30.08.22, 03:59

и все равно, вот этот момент надо окончательно прояснить:

См выше. Два первых. Все со списка восстанавливается на отлично.]]> Majestio Алгоритмы https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874937 Tue, 30 Aug 2022 03:59:53 +0000 Список смежности для графа, для графа с петлями и мультиграфа https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874937 test_8.png (, : 486) ]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874936 Tue, 30 Aug 2022 03:55:26 +0000 Список смежности для графа, для графа с петлями и мультиграфа https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874936 Цитата AVA12 @ 29.08.22, 16:59

А в чем смысл "ориентации" петель? Чем работа с "направленной" петлей отличается от работы с "ненаправленной"?

это ведь похоже на схему дорог, связывающих города, а направление петли показывает тип движение: одностороннее или двустороннее
тут вроде все ок

Цитата Majestio @ 29.08.22, 18:48

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

я бы готов был согласиться с этим утверждением, если бы не одно НО(!): даже из названия "смежности" следует описание смежностей вершин ( соседство их ), а к весам это не имеет отношения, поэтому, если граф взвешенный, то необходимо добавлять весовую матрицу. С др. стороны эта информация может быть инкапсулирована каким-то образом в класс "Ребро" и пр., но это ладно...
Изолированные вершины, безусловно, также участвуют в списке смежности, но у них NULL-список соседей

Цитата Akina @ 29.08.22, 18:51

Для данного "сложного" графа (хотя что тут сложного? ну если не считать направления у некоторых рёбер, которое я проигнорирую) список смежности такой:

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

если буду считывать его, то понимаю, что, первая пара соседей: a - a
test_3.png (, : 425)

затем снова пара: a - a
и здесь начинаются проблемы!
можно так построить:
test_4.png (, : 537)

в результате можно заменить на неориентированную петлю ( вроде ), т е:
test_5.png (, : 537)

а можно построить так:
test_6.png (, : 486)

но, теперь я понимаю, что AVA12 абсолютно верно указал на бесполезность ориентации петли ( если она без веса, разумеется ). По-большему счету ведь по хрен, есть ориентация у петли или нет: добраться все равно можно.

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

еще пример ТОЛЬКО на петли:
test_7.png (, : 479)
-------------------------------------------------
вывод: если петля имеет направление ( петля-дуга ), то 1 раз перечисляется, как сосед. Если не имеет - 2 раза.
А если 3 раза, например, то тогда будет одна петля-ребро и одна петля-дуга))
То есть, при считывании списка смежности, надо считать количество соседей, имеющих такую же метку, как и текущая вершина.

зы: какие же эти петли неудобные штуки!]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874926 Mon, 29 Aug 2022 18:57:02 +0000 Список смежности для графа, для графа с петлями и мультиграфа https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874926 Цитата Akina @ 29.08.22, 18:51

которое я проигнорирую

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

Цитата Akina @ 29.08.22, 18:51

Длина списка для узла равна количеству уникальных рёбер с вершиной

И тут неверно. Длина списка равна просто количеству вершин. Ибо существуют еще такой тип, как "разорванные графы". Все вершины должны быть перечислены, даже просто отдельно стоящая несоединенная вершина.]]> Majestio Алгоритмы https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874925 Mon, 29 Aug 2022 18:51:40 +0000 Список смежности для графа, для графа с петлями и мультиграфа https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874925

a: bcccd

b: abcd

c: aaab

d: abd

Длина списка для узла равна количеству уникальных рёбер с вершиной (для направленных графов - начальной) в этом узле. И соответственно элементы списка - это вторые узлы-вершины.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874924 Mon, 29 Aug 2022 18:48:01 +0000 Список смежности для графа, для графа с петлями и мультиграфа https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874924 Цитата FasterHarder @ 29.08.22, 08:48

подскажите, плиз, где ошибся в списке смежности для этого графа + как должно быть правильно, буду признателен.

Думаю, как-то так. Где в (*) указывает направленное ребро.

a: b, c, c, d

b: a, b, c, d

c: a(*), a, a, b

d: a, b, d(*)

Дело в том, что если почитать про Теорию Графов, можно просто утонуть в "непричесанности" терминологии. Каждая прикладная область применения Теории Графов имеет свою специфику и свою терминологию.

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

N1: N2(наличие направления, вес), ...Nx(наличие направления, вес) ...

Частично-взвешенных графов не бывает, не используют такое. Но это ЕМПИП.]]> Majestio Алгоритмы https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874908 Mon, 29 Aug 2022 16:59:06 +0000 Список смежности для графа, для графа с петлями и мультиграфа https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874908 AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874804 Mon, 29 Aug 2022 08:48:09 +0000 Список смежности для графа, для графа с петлями и мультиграфа https://forum.sources.ru/index.php?showtopic=429467&view=findpost&p=3874804
хочется понять основательно представление графа в виде списка смежности. ЛЮБОГО графа...
в целом, как устроен список смежности - понятно, в инете полно инфы по этому поводу, но все примеры какие-то тривиальные

вот пример для неориентированного помеченного невзвешенного графа, состоящего из 4-рех вершин:
test_1.png (, : 526)

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

вот пример списка смежности для "сложного" ( относительно ) графа.
test_2.png (, : 527)

подскажите, плиз, где ошибся в списке смежности для этого графа + как должно быть правильно, буду признателен.

спс за внимание]]> FasterHarder Алгоритмы