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

Читать целиком »

Практически каждому программисту приходится сталкиваться с древовидной структурой.

Дано: php + mysql.
Все элементы, которые входят в древовидную структуру хранятся в одной таблице базы данных.
Найти: способ хранения и представления древовидной структуры.

1. Простейший вариант состоит в том, что все “ветки” дерева имеют дополнительное поле “идентификатор родителя”, используя который и можно построить всё дерево. Если нет необходимости строить всё дерево, а достаточно просматривать потомков следующего уровня некоторого родителя - то такой способ организации дерева, на мой взгляд, идеален. Если же требуется строить дерево целиком, то придется использовать рекурсивную процедуру - или в php или в mysql (при условии, что максимальная “глубина  дерева” заранее определена, можно, конечно, обойтись одним составным, в котором одна таблица присоединяется сама к себе… Но это уже больше похоже на извращения..).
   Можно, конечно, обойтись одним запросом (что-то вроде “select * from tree”, а данные разбирть уже в php примерно так:
  while($row = mysql_fetch_assoc($res)){
  $tree[$row['pid']][$row['id']] = $row;
  }
Плюсы: простота организации данных.
   Минусы: при большом количестве “веток” количество запросов возрастает…
2. Nested sets или вложенные множества. Способ организации дерева, при котором дерево обходится, к примеру слева направо, и все вершины нумеруются дважды.
   
   Плюсы: одним запросом можно выбрать всех потомков, отстоящих по дереву на заданное количество уровней, всех родителей.. да вообще много чего можно. Где-то встречал уже готовый класс для работы с ”Nested sets” -  деревьями.