Как называется структура данных, похожая на кегли для боулинга?

Question

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

По сути, я просто ищу имя структуры данных, элементы которой выглядят следующим образом (не обращайте внимания на точки):

......5

....3...2

..4...1...6

9...2...3...1

Сначала я подумал, что это может быть определенный вид «дерева», но, как говорит Википедия:

Дерево — это [...] ациклический связный граф, в котором каждый узел имеет ноль или более дочерних узлов и не более одного родительского узла

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

Итак, вот мой вопрос:

Как называется структура данных, которая может представлять данные со следующими связями между элементами?(/ и \ — ссылки, опять же, точки игнорируйте):

......5

...../..\

....3...2

.../..\./..\

..4...1...6

../.\./..\./..\

9...2...3...1

Answer 1

Я думаю, что это не совсем не так, чтобы называть это деревом, хотяДипраф«(направленный график) был бы более правильным сроком.

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

Название в порядке, я лол, когда я открыл вопрос. Я собираюсь начать звонить им "боулинг-булавки" сейчас :)

      5

    3   2

  4   1   6

9   2   3   1

Answer 2

Я считаю, что самая популярная вещь, которая была изложена вот так, это Треугольник Паскаля.Это структура, используемая для расчета биномиальные коэффициенты;каждый узел представляет собой сумму своих родителей:

http://info.ee.surrey.ac.uk/Personal/L.Wood/publications/MSc-thesis/fig36.gif.

Обычно, когда дело доходит до реализации таких алгоритмов (такой класс обычно называют «динамическое программирование»), эта «структура» обычно представляется в виде простого двумерного массива.Видеть здесь, например:

n\k  0  1  2  3  4
------------------
0    1  0  0  0  0 
1    1  1  0  0  0 
2    1  2  1  0  0 
3    1  3  3  1  0 
4    1  4  6  4  1 
5    1  5 10 10  5 
6    1  6 15 20 15

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

Но отныне, как NullUserException предлагает Я называю это "кеглями для боулинга" :-)

Answer 3

«DAG» или направленный ациклический граф, представляет собой график с направленным преимуществом, в котором могут быть несколько путей к узлу, а некоторые узлы могут иметь как входящие, так и исходящие края, но нет способа оставить любой узел и возвращаться в Это (нет циклов). Обратите внимание, что в конечном отличии, по меньшей мере, один узел, не должен иметь ничего, кроме исходящих краев, а по крайней мере, нужно иметь ничего, кроме входящих краев. Были ли то, что не так, можно было бы непрерывно перемещаться через график, не достигая мертвого конца (поскольку каждый узел будет иметь выход), и не посещающий любой узел дважды (поскольку график AcyClic). Если есть только конечное число узлов, это явно невозможно.

Answer 4

Поскольку в структуре данных может быть более одного родителя в структуре данных, я ищу, это, вероятно, не дерево.

Что вы ищете, вероятно, график. Отказ А. дерево это особый случай графика, где каждый узел имеет ровно один родитель. (кроме корня, который имеет ни одного)