Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
SungMaster
1 / 1 / 0
Регистрация: 25.10.2010
Сообщений: 29
1

Экономное представление путей в графе

16.12.2015, 13:22. Просмотров 284. Ответов 7
Метки нет (Все метки)

Есть приведенное бинарное дерево (изоморфные подграфы сливаются, в узла может стать несколько родителей). Нужно каким-то образом представлять пути от листьев к корню. Верхняя часть пути у многих маршрутов похожа (т.к. дерево). Нужно с минимальными расходами памяти разметить все маршруты (в нашем случае маршрут выступает неким ключом, по которому нужно собрать значение из узлов по пути). Вариат разметки от корня к листьям тоже допускается.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.12.2015, 13:22
Ответы с готовыми решениями:

поиск путей на графе
поиск путей на графе дан ориентированый граф из 2-50 вершин, где каждому существующему ребру...

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

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

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

Каким образом лучше выполнять поиск всех возможных путей в ориентированном графе?
Имеется ориентированный граф. Каждое ребро графа имеет вес (условно обозначу #). Задача - найти...

7
Shamil1
Модератор
2299 / 1594 / 356
Регистрация: 26.03.2015
Сообщений: 5,787
16.12.2015, 14:05 2
Не совсем понял, что требуется, но...
Простой маршрут (дерево) можно хранить в виде связанного (неизменяемого) списка узлов.
В "многородительских" узлах приведённого дерева обрываем простой маршрут.
Сложный маршрут (дерево простых маршрутов) храним в виде связанного списка простых маршрутов.
0
SungMaster
1 / 1 / 0
Регистрация: 25.10.2010
Сообщений: 29
16.12.2015, 14:21  [ТС] 3
Во вложении пример возможного графа (описывает все возможные комбинации с 'a' и 'b' длиною 3). Со списками нужно поосторожней, т.к. они вместе могут занять места больше, чем сам граф, а тогда пропадает смысл приводить его (т.е. тогда проще и дешевле оставлять его в виде дерева)
0
Изображения
 
Shamil1
Модератор
2299 / 1594 / 356
Регистрация: 26.03.2015
Сообщений: 5,787
16.12.2015, 16:22 4
Цитата Сообщение от SungMaster Посмотреть сообщение
Во вложении пример возможного графа (описывает все возможные комбинации с 'a' и 'b' длиною 3).
Не понимаю. Один узел может участвовать в пути несколько раз?

Цитата Сообщение от SungMaster Посмотреть сообщение
Со списками нужно поосторожней, т.к. они вместе могут занять места больше, чем сам граф
Не понимаю. Все возможные пути на (односвязном) графе всегда займут больше места, чем сам граф.
0
16.12.2015, 16:22
SungMaster
1 / 1 / 0
Регистрация: 25.10.2010
Сообщений: 29
16.12.2015, 16:38  [ТС] 5
Цитата Сообщение от Shamil1 Посмотреть сообщение
Один узел может участвовать в пути несколько раз?
Нет, узлы распределы по уровнях, с уровня можно взять только один узел
Цитата Сообщение от Shamil1 Посмотреть сообщение
Все возможные пути на (односвязном) графе всегда займут больше места, чем сам граф.
В любом случае нужно минимизировать расход памяти
0
Shamil1
Модератор
2299 / 1594 / 356
Регистрация: 26.03.2015
Сообщений: 5,787
16.12.2015, 17:00 6
Цитата Сообщение от SungMaster Посмотреть сообщение
описывает все возможные комбинации с 'a' и 'b' длиною 3
Я вижу на рисунке:
6 кружочков... вероятно, узлов графа. Непонятно, зачем рядом с ними числа.
7 линий... вероятно рёбер графа. Непонятно, почему некоторые из них пунктирные.

Я не могу прочитать Ваши мысли и догадаться, каким образом этот граф описывает "все возможные комбинации с 'a' и 'b' длиною 3". Я вижу пути длиной от 1 до 6. И не вижу путь, проходящий через bbb.
0
SungMaster
1 / 1 / 0
Регистрация: 25.10.2010
Сообщений: 29
16.12.2015, 17:14  [ТС] 7
Цитата Сообщение от Shamil1 Посмотреть сообщение
Я не могу прочитать Ваши мысли и догадаться, каким образом этот граф описывает "все возможные комбинации с 'a' и 'b' длиною 3". Я вижу пути длиной от 1 до 6. И не вижу путь, проходящий через bbb.
Нумерация узлов только для наличия. Корень в узле 1. Предположим, что анализируется строка длиной 3. Заходим в корень, проверяем, совпала ли буква, на которой стоит курсор чтения строки, с той, что записана в узле. Если да - сдвигаем курсор, переходим по ребру, обозначеному сплошной линией. Если нет - переходим по ребру, обозначеному пунктирной линией, не сдвигая курсор чтения строки. И так пока будет куда идти.
Граф указывает, какие слова в нашем словаре есть. А нужно еще и каким-то образом получать из него отдельные слова.
0
Igor3D
1229 / 596 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
17.12.2015, 07:35 8
Каждый узел хранит контейнер/массив исходящих ребер, а если требуется - то и входящих. Вопрос с экономией памяти чисто технический, обычно решается собственной кучей (в том или ином виде) т.к. стандартные контейнеры могут оказаться слишком расходными.

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

0
17.12.2015, 07:35
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.12.2015, 07:35

Нахождение путей в графе
Доброго времени суток! Подскажите: Есть граф как на рисунке. Необходимо найти все возможные пути....

Найти количество путей в графе
Сколько маршрутов длины не больше 3 существует между вершинами 1 и 4 графа G = ( {1,2,3,4,5},...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru