Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.57/7: Рейтинг темы: голосов - 7, средняя оценка - 4.57
1 / 1 / 1
Регистрация: 10.08.2015
Сообщений: 40

Алгоритм развёртывания графа

18.11.2018, 05:42. Показов 1381. Ответов 10
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Добрый день. Столкнулся с такой проблемой. В базе данных хранится информация о компонентах изделия
КОД_ИЗДЕЛИЯКОД_КОМПОНЕНТЫКОЛИЧЕСТВО
AB11
AB21
AB31
B1NULLNULL
B2C11
B2C21
B3C31
C1NULLNULL
C2NULLNULL
C3NULLNULL

Нужно как-то свернуть этот структурный граф (дерево). Подскажите структуру алгоритма
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
18.11.2018, 05:42
Ответы с готовыми решениями:

Алгоритм построения планарного графа
День добрый. Я довольно долго искал по просторам интернета алгоритм построения планарного (или, кому как проще, плоского) графа. Не нашел....

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

Генетический алгоритм размещения вершин графа
Привет всем.Тут решение одной задачи. Кто может объясните откуда из p1 -1 2 3 4 5 взялось L1 = 3+ 4+ 3+ 1 = 11. На рисунке с низу сам граф....

10
392 / 294 / 121
Регистрация: 26.08.2016
Сообщений: 902
18.11.2018, 17:02
Что значит свернуть? Преобразовать в иерархическое дерево?
1
Модератор
Эксперт функциональных языков программирования
3134 / 2281 / 469
Регистрация: 26.03.2015
Сообщений: 8,878
18.11.2018, 20:05
T-SQL
1
select .... from ... group by ...
0
1 / 1 / 1
Регистрация: 10.08.2015
Сообщений: 40
19.11.2018, 15:57  [ТС]
Да, именно получить дерево, саму структуру

Добавлено через 2 минуты
Оно то понятно, но одним таким запросом можно получить "детей" только одной вершины
0
Модератор
Эксперт функциональных языков программирования
3134 / 2281 / 469
Регистрация: 26.03.2015
Сообщений: 8,878
19.11.2018, 16:28
Цитата Сообщение от mikki234 Посмотреть сообщение
Нужно как-то свернуть этот структурный граф (дерево).
Мой запрос и есть свёртка. В простейшем случае свёртка - это одно число.

Цитата Сообщение от mikki234 Посмотреть сообщение
Да, именно получить дерево, саму структуру
"Получить дерево" в каком виде?
Обычно при хранении дерева в БД в таблицу добавляют пути от корня или правые/левые индексы. Возможно, в Вашем случае второй способ лучше.
0
392 / 294 / 121
Регистрация: 26.08.2016
Сообщений: 902
20.11.2018, 11:45
Цитата Сообщение от Shamil1 Посмотреть сообщение
Обычно при хранении дерева в БД в таблицу добавляют пути от корня или правые/левые индексы.
Не обязательно, ссылка на родителя вполне достаточна, дерево можно получить одним обходом с использованием хэш-таблицы. Пример на javascript

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
const table = [
  {code: 'A', component: 'B1', amount: 1},
  {code: 'A', component: 'B2', amount: 1},
  {code: 'A', component: 'B3', amount: 1},
  {code: 'B1', component: null, amount: null},
  {code: 'B2', component: 'C1', amount: 1},
  {code: 'B2', component: 'C2', amount: 1},
  {code: 'B3', component: 'C3', amount: 1},
  {code: 'C1', component: null, amount: null},
  {code: 'C2', component: null, amount: null},
  {code: 'C3', component: null, amount: null},
];
 
v = 1;
 
const codesMap = {};
let parent, component
table.forEach(row => {
    if(!(parent = codesMap[row.code])) {
        parent = codesMap[row.code] = {code: row.code};
    }
 
    if(row.component) {
        if(!parent.components) parent.components = [];
        if(!(component = codesMap[row.component])) {
            component = codesMap[row.component] = {
                code: row.component, 
            };
        }
    component.isComponent = true;
        parent.components.push({
            component: component,
            amount: row.amount,
        })
    }
})
 
function showTree(thing, level, amount) {
 
    tree.innerHTML += '<div>' + '--'.repeat(level) + thing.code + (amount ? ' - ' + amount + 'шт.' : '') + '</div>';
    if(thing.components) {
        thing.components.forEach(c => showTree(c.component, level + 1, c.amount));
    }
 
}
 
for(let k in codesMap) {
    const thing = codesMap[k];
    if(thing.isComponent) continue;
 
    showTree(thing, 0); 
}
https://codepen.io/anon/pen/xQPWvg

Добавлено через 2 часа 11 минут
Цитата Сообщение от mikki234 Посмотреть сообщение
одним таким запросом можно получить "детей" только одной вершины
Запросом кстати тоже можно, сделав несколько вложенных друг в друга левых соединений для поиска детей, и зааписывая их в childLevel1, childLevel2 и допустим до 4х. Если есть хоть один child последнего 4 уровня, то повторяем запрос для тех позиций, где он есть, записывая уже в childLevel5 и т.д., если таблица индексирована, работает довольно быстро. Но проще мне кажется первый вариант с пост-обработкой плоской таблицы.
0
Модератор
Эксперт функциональных языков программирования
3134 / 2281 / 469
Регистрация: 26.03.2015
Сообщений: 8,878
20.11.2018, 11:48
Цитата Сообщение от renat_dmitriev Посмотреть сообщение
дерево можно получить одним обходом с использованием хэш-таблицы
Это значит, либо выкачать все данные в память и там работать с ними, либо постоянно запрашивать новые данные. Оба подхода приводят к большой потере производительности на больших объёмах данных. А если добавить правые-левые индексы, то ответ на любой вопрос про дерево можно будет получить простым SQL-запросом.
0
392 / 294 / 121
Регистрация: 26.08.2016
Сообщений: 902
20.11.2018, 12:06
Цитата Сообщение от Shamil1 Посмотреть сообщение
Это значит, либо выкачать все данные в память и там работать с ними, либо постоянно запрашивать новые данные.
В любом случае у вас только две альтернативы - либо выкачать все данные в память, либо при каждом развороте ветки подкачивать детей. Здесь наверное не имеет смысла строить предположения, пока автор не скажет какие у него объемы и для чего это используется. И опять же что такое большие объемы данных? Думаю миллион строк этот алгоритм обработает быстро, но пользователю такой объем естественно не нужен, а если этот алгоритм используется для расчета неких значений, то либо он должен запускаться нечасто, либо структура данных должна быть оптимизирована.

Добавлено через 3 минуты
Цитата Сообщение от Shamil1 Посмотреть сообщение
А если добавить правые-левые индексы, то ответ на любой вопрос про дерево можно будет получить простым SQL-запросом.
Любой запрос возвращает плоскую таблицу, для приведения его к виду дерева в любом случае потребуется обход и соответственно расход памяти. То есть разница в производительности будет только на алгритмы хэш-таблицы, имеющие логарифмическую сложность.
0
Модератор
Эксперт функциональных языков программирования
3134 / 2281 / 469
Регистрация: 26.03.2015
Сообщений: 8,878
20.11.2018, 12:47
Цитата Сообщение от renat_dmitriev Посмотреть сообщение
пока автор не скажет какие у него объемы и для чего это используется
Я так понимаю, что есть рекурсивный список составных частей для изделий. Нужно выяснить, например, сколько винтов М6 ГОСТ 1491-80 требуется для сборки стиральной машины.

Цитата Сообщение от renat_dmitriev Посмотреть сообщение
либо выкачать все данные в память
В БД могут быть сотни миллионов строк, большая часть которых относится к другим изделиям (нас не интересует).

Цитата Сообщение от renat_dmitriev Посмотреть сообщение
либо при каждом развороте ветки подкачивать детей
Каждый запрос к БД - это накладные расходы. Для простых запросов эти накладные расходы многократно превосходят время исполнения самого запроса. Если изделие состоит из нескольких сотен деталей, то суммарный объём таких расходов может вырасти до неприличных размеров.

Цитата Сообщение от renat_dmitriev Посмотреть сообщение
Любой запрос возвращает плоскую таблицу, для приведения его к виду дерева в любом случае потребуется обход и соответственно расход памяти.
Часто требуется не само дерево, а его свёртка, которая является плоским списком. Например, список всех компонентов рекурсивно входящих в заданное изделие.
Даже если требуется целое поддерево, то его размеры могут быть на несколько порядков меньше размера всего хранящегося в таблице леса деревьев.
0
392 / 294 / 121
Регистрация: 26.08.2016
Сообщений: 902
20.11.2018, 13:00
Цитата Сообщение от Shamil1 Посмотреть сообщение
В БД могут быть сотни миллионов строк, большая часть которых относится к другим изделиям (нас не интересует).
При таких объемах я бы хранил в БД дополнительную таблицу, которая содержала бы окончательный состав комплектующих последнего уровня без промежуточных слоев для тех элементов, у которых глубина комплектации больше одного уровня. Думаю тут всегда надо анализировать и оптимизировать уже структуру хранения.
0
Модератор
Эксперт функциональных языков программирования
3134 / 2281 / 469
Регистрация: 26.03.2015
Сообщений: 8,878
20.11.2018, 13:25
Цитата Сообщение от renat_dmitriev Посмотреть сообщение
При таких объемах я бы хранил в БД дополнительную таблицу, которая содержала бы окончательный состав комплектующих последнего уровня без промежуточных слоев для тех элементов, у которых глубина комплектации больше одного уровня.
Вычисления данных для промежуточной таблицы могут быть сложными (требовать открывания курсора и т.п.). И такой подход лишён гибкости. А правые-левые индексы позволяют ответить на любой вопрос про поддерево.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
20.11.2018, 13:25
Помогаю со студенческими работами здесь

Алгоритм поиска циклов неориентированного графа
Помогите пожалуйста. Нужен алгоритм, который считал бы циклы неориентированного графа.

Гамма-алгоритм плоской укладки графа
Всем привет! Необходимо запрогать алгоритм плоской укладки графа. В связи с этим вопрос какую лучше выбрать структуру для...

Алгоритм раскраски графа
Раскраска графа, нужен алгоритм! Помогите! Желательно на C++!

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

Нахождение фактора графа и остова графа для некоторого произвольного графа (5-6 вершин)
Форумчане прошу помощь в выполнение задания по деск. мат. Задание: Нахождение фактора графа и остова графа для некоторого произвольного...


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Новые блоги и статьи
Подключение Box2D v3 к SDL3 для Android: физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image
8Observer8 27.01.2026
Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
Влияние грибов на сукцессию
anaschu 26.01.2026
Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android
8Observer8 26.01.2026
Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д.
8Observer8 25.01.2026
Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf
8Observer8 25.01.2026
Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru