Граф — это более общий случай дерева. Иногда деревья называют ациклическими графами.
Отличий у этих структур данных два:
● В графе возможны циклы, то есть «ребёнок» может быть «родителем» для того же элемента.
● Рёбра тоже могут нести смысловую нагрузку, то есть нужно сохранять их значения.
Графы бывают ориентированные и неориентированные. У первых рёбра между узлами имеют направление, так что порядок элементов важен. У вторых направлений нет, и элементы можно читать и обходить в любом порядке.
У ориентированных графов важен порядок элементов, у неориентированных ― элементы можно менять местами
Графы часто представляют в виде матрицы смежности.
Здесь каждая строка или столбец — узел. 1 в ячейке означает, что между узлами есть связь, 0 — что связи нет. Если у связей, то есть рёбер графа, есть вес, он как раз может быть помещён в ячейку
Как применяют графы:
● Для хранения информации, связанной друг с другом сложными соотношениями.
● Для анализа соотносящейся друг с другом информации.
● Для построения маршрута из точки А в точку Б.
Структуру данных для работы выбирают в зависимости от задачи. Если нужно что-то простое, подойдёт обычный массив. Когда требуется создать очередь или историю запросов, выбирают связный список или очередь. Если нужен поиск и сортировка, поможет двоичное дерево. Именно поэтому важно знать все типы данных в программировании, чтобы подбирать оптимальный в любой ситуации.