Граф - математический объект. Представляет из себя набор точек и связей между ними. Его изучением занимается теория графов.
Графы используются для демонстрации связей между объектами. Например, можно показать, какие люди знакомы между собой или карту дорог между основными точками маршрута.
Существует несколько видов графа:
- Неориентированный - в таком графе, если между двумя объектами есть связь, то она есть и из одного, и из другого. Таким графом можно описать родственников. Если один человек родственник для другого, то и другой родственник для первого.
- Ориентированный - в этом графе, между двумя объектами не обязательно существует связь в обе стороны. Яркий пример такого графа - дороги. Движение на них может быть как двухстороннее так и одностороннее.
Основные определения
Вершина - объекты, связи между которыми рассматриваться. На примере графа они изображены кругами с цифрами.
Ребро - связь между вершинами в неориентированном графе.
Дуга - связь между вершинами в ориентированном графе.
Смежные вершины - вершины, между которыми есть ребро или дуга.
Взвешенный граф - граф, в котором каждому ребру задано число, называемое весом ребра. Например, таким графом можно показать загруженность дорог.
Применение на практике
Поскольку граф это очень абстрактный математический объект, который к тому же можно описать конечным списком элементов, он широко применяется в компьютерных науках.
- Основное, конечно, это хранение связей между объектами. Такими, например, как друзья в социальных сетях или структура папок на диске.
- Благодаря своей гибкости размещения элементов, они применяются вместе с алгоритмами для хранения данных в определённом порядке, что позволяет ускорить выполнение программы.
- Также существует группа задач для графов, часто возникающих на практике. Например, как быстрее добраться из одной части города в другую, если существует множество вариантов как это можно сделать. Или как обойти все нужные места, чтобы не приходить в одно и то же более одного раза. Для таких задач уже разработано много алгоритмов, каждый из которых лучше справляется с определённым подвидом этих задач.