Граф, как математический объект

Граф невероятно простой концептуально объект, но который открывает нам множество возможностей. Знали ли вы, что такие задачи, как поиск пути, вывод древовидных комментариев и динамические структуры данных – это поле теории графов?

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

С точки зрения математики, графы изучаются как более абстрактные объекты с какими-то отличительными свойствами. Например, есть ли направление у связи? Есть ли циклы на графе? Какие алгоритмы мы можем применять к тем или иным графам?

Но больше толку для вас, конечно же, будет представлять чисто практический опыт применения этих знаний. И чаще всего граф будет спрятан под абстракцией, и вам нужно будет грамотно представить его с инкапсуляцией, и это, зачастую, бывает очень не просто.

Что можно представлять графом?

Граф G – это два множества. Первое множество состоит из вершин (ноды, node, индексы, vertices, вертиксы). А второе множество из пар (рёбра, edges), которые определяют отношения.

Например: G = (V, E), где

V – Множество вершин;

E – Множество рёбер (пар).

Что можно описать таким графом? Например, у нас есть в игре танки. Танки разбиты на ветки, и, допустим, если мы хотим получить танк КВ-2, нам изначально нужно получить танк КВ-1.

Тогда мы могли бы сказать, что множество V содержит танки:

V = (КВ-1, КВ2, ИС-1, ИС-2, ИС-3)

А множество E содержит отношения танков, например, представлено как множество (родитель, [потомки]):

E = ((КВ-1, КВ-2), (ИС-1, ИС-2), (ИС-2, ИС-3))

Такой граф бы очертил две ветки танков, чтобы получить ИС-3 мне сначала нужно было бы открыть ИС-2,а чтобы открыть его, нужно открыть ИС-1.

Вершины бы содержали, вероятно, не только сами танки, но и дополнительные состояния: открыт\закрыт, куплен\не куплен, исследован\не исследован.

Т.е. танк открыт (доступен для исследования; на исследование тратится валюта). Следующий танк считается открытым, если исследован один из предыдущих.

Рёбра тоже могут содержать данные, например, если бы ИС-3 был доступен из другой ветки (например, исследование одного танка открывает нам два других танка), то исследование из одной ветки стоило бы одно количество валюты, а из другой другое.

У нас получился ориентированный граф, в таком графе очень важно откуда и куда лежат связи. Так связь (ИС-2, ИС-3) лежит от первого ко второму. Т.е. первый танк открывает для исследования второй, и если у нас открыт второй (в результате какой-то акции пользователь получил этот танк), то это не означает доступность первого. Допустим игрок купил за реальные деньги ИС-3, при этом, чтобы получить ИС-2, ему сначала нужно открыть ИС-1.

Инкапсуляция графа

Графы являются структурами данных – они помогают организовать связи между различными данными системы. С точки зрения объектно-ориентированного программирования – это ужас и большой вызов. Объекты должны обладать инкапсуляций – защитой внутреннего состояния. Графы в этом плане дают большое поле для творчества.

Если представлять граф, как полноценный объект, то мы уже не можем работать с ним как хотим. К структуре начинает примешиваться модель приложения и бизнес-правила. Например, если мы представим граф квестовой системы, где выполнение одного квеста может давать игроку ряд других квестов, то мы можем иметь следующие правила:

  • У нас не должно быть циклов, когда, например, квест A открывает доступ к квесту B, а тот, в свою очередь, опять к квесту A.
  • Открываемые квесты можно выполнить на ближайших локациях (явное выражение такого геймдизайн-правила в коде – это очень полезный трюк).

В таком случае мы уже не сможем описать граф влоб, и он будет красиво скрываться в объектной модели. Дальше мы рассмотрим как это сделать.

Если вы нашли ошибку, пожалуйста выделите её и нажмите Ctrl+Enter.


Leave a Reply

Your email address will not be published. Required fields are marked *