Графы превратились в невероятно сильное средство моделирования и получения данных из соцсетей, веб-страниц и ссылок, а также определения местоположения и маршрутов в GPS. Любой набор объектов, которые связаны друг с другом, можно сейчас представить с помощью графа.
В статье опишем 10 основных графовых алгоритмов, которые становятся очень полезными для анализа, а также области их применения.
Начнём с того, что приведём определение графа.
Что такое граф?
Граф состоит из конечного множества вершин (узлов) и набора рёбер, соединяющих эти вершины. Две вершины считаются смежными, если они соединены друг с другом одним и тем же ребром.
Ниже приведён ряд базовых понятий, относящихся к графам.
Порядок: число вершин в графе.
Размер: число рёбер в графе.
Степень вершины: число рёбер, инцидентных вершине.
Изолированная вершина: вершина, которая не связана ни с одной другой вершиной графа.
Петля: ребро, вершины которого совпадают.
Ориентированный граф: граф, в котором все рёбра имеют направление, определяющее начальную и конечную вершину.
Неориентированный граф: граф с рёбрами, которые не имеют направления.
Взвешенный граф: рёбра такого графа имеют определённый вес.
Невзвешенный граф: рёбра такого графа не имеют никаких весов.
Комментариев нет:
Отправить комментарий