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

Question

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

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

...... 5

.... 3 ... 2

.. 4 ... 1 ... 6

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

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

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

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

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

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

...... 5

..... / .. \

.... 3 ... 2

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

.. 4 ... 1 ... 6

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

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

Answer 1

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

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

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

      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 по крайней мере один узел должен иметь только исходящие ребра, а по крайней мере один должен иметь только входящие ребра.Если бы это было не так, было бы возможно непрерывно перемещаться по графу, даже не заходя в тупик (поскольку каждый узел будет иметь выход), и не посещая ни один узел дважды (поскольку граф является ациклическим).Если существует только конечное число узлов, это, очевидно, невозможно.

Answer 4

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

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