В настоящее время я разрабатываю онтологию, веб-иерархию категорий всего (подумайте о людях, местах, вещах). Готовый продукт должен быть чем-то, что позволит мне перейти от Технологии->Компьютеры->Ноутбуки->Порты USB, а также от Фильмов->Особое мнение->Компьютеры->и т.д. Мне нужна эффективная структура данных для их группировки. Мне нужен древовидный граф, но особое дерево, позволяющее дочерним узлам иметь несколько родительских узлов. Размышляя над этим, я понял, что Википедия — несовершенная модель для этого. Фактически, у них есть иерархия, начинающаяся здесь. Я нуждаюсь. Я вижу, что они использовали ориентированный граф, но мне интересно, каковы различия/недостатки между этим ориентированным графом, ориентированным ациклическим графом и полидеревом. Я пытался исследовать это, но я не совсем понимаю различия. Любая помощь будет принята с благодарностью. Спасибо!
Структуры данных: дерево, подобное Википедии
comment
Кстати: категории Википедии допускают циклы, хотя они и не нужны сообществу. Немецкая система является лучшим примером мультидерева, корнем которого является !Hauptkategorie.
- person Bergi schedule 07.06.2012
comment
Возможно, вы имеете в виду онтологию? В противном случае это звучит как обычный ориентированный граф.
- person Konrad Rudolph schedule 07.06.2012
comment
Да, я имею в виду онтологию. Спасибо за правильный жаргон :)
- person Ruben Martinez Jr. schedule 07.06.2012
Ответы (1)
Я думаю, что статьи в Википедии дают хороший обзор:
- ориентированный граф – это набор узлов, соединенных ребрами, с которыми связано направление.
- направленный ациклический граф (DAG) — это ориентированный граф без направленные циклы.
- полидерево (также называемое ориентированным деревом) – это ориентированный граф, в котором ровно один неориентированный путь между любыми двумя вершины. Другими словами, полидерево – это ориентированный граф, базовым неориентированным графом которого является дерево. , или, что то же самое, связный ориентированный ациклический граф, для которого также нет неориентированных циклов .
Итак, я думаю, вы ищете связный ориентированный ациклический граф. Хотя система категорий Википедии допускает циклы, они нежелательны.
person
Bergi
schedule
07.06.2012
Спасибо вам за помощь! Однако я не совсем понял, что Википедия имела в виду под словом «направленный». Не могли бы вы объяснить, что значит для ребра иметь направление? Это просто жаргон для родителей и детей? *извините, если это глупый вопрос
- person Ruben Martinez Jr.; 07.06.2012
Нет, это просто общий термин. Да, граф соединений родитель-потомок будет направленным, но не каждое направленное ребро означает родитель->потомок (как в дереве).
- person Bergi; 07.06.2012
направленный означает, что вы можете двигаться только в направлении ребра от узла «от» к узлу «к» (но не назад). В неориентированном графе вы можете путешествовать туда и обратно от узла к узлу по ребру.
- person Justin; 07.06.2012
Спасибо @Justin, так что, если я хочу подняться, скажем, из баскетбола в спорт, мне понадобится неориентированный граф?
- person Ruben Martinez Jr.; 07.06.2012
Нет, в неориентированном графе вы бы не знали, вверх он или вниз, просто вы можете путешествовать. Но ваш ориентированный граф может предоставить метод getIncomingEdges(node), который возвращает, например, Sports и Balls.
- person Bergi; 07.06.2012
@RMartin Если вы хотите двигаться вверх от баскетбола к спорту, вы можете использовать дополнительное направленное ребро (по сути, направленное ребро от баскетбола к спорту и одно от спорта к баскетболу). Но если вы всегда хотите иметь возможность путешествовать в обоих направлениях, то вам подойдет неориентированный граф.
- person Justin; 07.06.2012
@Justin: Нет, в неориентированном графе вы не можете не путешествовать в любом направлении :-)
- person Bergi; 07.06.2012
@ Берги Я не уверен, что сказал это. Я имею в виду следующее: если вы находитесь в узле Basketball, вы можете перемещаться из Basketball в любой узел, который имеет граничное соединение с Basketball.
- person Justin; 07.06.2012
Спасибо за объяснение @Justin и @Bergi! Таким образом, с помощью неориентированного графа я могу перейти от Баскетбола к Спорту или вниз, скажем, к Баскетболистам. Всегда. Но с ориентированным графом, если я специально не добавлю второе ориентированное ребро, я не могу двигаться в обоих направлениях. Это правильно? Является ли ориентированный граф менее/более затратным, чем неориентированный граф, с точки зрения эффективности?
- person Ruben Martinez Jr.; 07.06.2012
@RMartin Ты понял. Непрямой граф реализовать несколько проще, чем ориентированный. Я думаю, что если у вас много двунаправленных ребер между узлами, то ориентированный граф занимает больше места, но не имеет большого значения. С точки зрения процессора неориентированный граф может быть немного быстрее, поскольку логика проще, но это не имеет большого значения.
- person Justin; 07.06.2012
Нет, вы можете перемещаться по всем типам графиков. направленный означает, что на ребрах есть только информация о направлении, в которой говорится, какой узел вверх, а какой вниз (или родитель/потомок или что-то еще). Это означает, что ему нужно больше места для хранения. Эффективность зависит от реализации задач, которые вы хотите выполнить.
- person Bergi; 07.06.2012
@Bergi Итак, кажется, что любой граф позволяет мне путешествовать вверх или вниз, но ориентированный граф фактически хранит информацию о том, какой узел находится вверху, а какой внизу. Что-то вроде связанного списка? И если бы он был направлен вверх и вниз, это было бы похоже на двусвязный список? Неориентированный граф проще, легче. Но ориентированный граф работает быстрее, когда нам нужно часто перемещаться вверх и вниз по ветвям. Я размышляю здесь, это правильно?
- person Ruben Martinez Jr.; 07.06.2012
Я думаю, что вы определили здесь не полидерево (также называемое направленным деревом), а полифорест (также называемое направленным деревом). лес). Полидерево — это ориентированный граф с ровно одним неориентированным путем между любыми двумя вершинами. Другими словами, полидерево — это связный ориентированный ациклический граф, для которого также нет неориентированных циклов. Для справки см. мой ответ.
- person Maggyero; 16.05.2019
