Что такое графы

Граф — это более общий случай дерева. Иногда деревья называют ациклическими графами.

Отличий у этих структур данных два:

● В графе возможны циклы, то есть «ребёнок» может быть «родителем» для того же элемента.

● Рёбра тоже могут нести смысловую нагрузку, то есть нужно сохранять их значения.

Графы бывают ориентированные и неориентированные. У первых рёбра между узлами имеют направление, так что порядок элементов важен. У вторых направлений нет, и элементы можно читать и обходить в любом порядке.

У ориентированных графов важен порядок элементов, у неориентированных ― элементы можно менять местами

Графы часто представляют в виде матрицы смежности.

Здесь каждая строка или столбец — узел. 1 в ячейке означает, что между узлами есть связь, 0 — что связи нет. Если у связей, то есть рёбер графа, есть вес, он как раз может быть помещён в ячейку

Как применяют графы:

● Для хранения информации, связанной друг с другом сложными соотношениями.

● Для анализа соотносящейся друг с другом информации.

● Для построения маршрута из точки А в точку Б.

Структуру данных для работы выбирают в зависимости от задачи. Если нужно что-то простое, подойдёт обычный массив. Когда требуется создать очередь или историю запросов, выбирают связный список или очередь. Если нужен поиск и сортировка, поможет двоичное дерево. Именно поэтому важно знать все типы данных в программировании, чтобы подбирать оптимальный в любой ситуации.