10 Графовых алгоритмов

Источник: Nuances of Programming

Графы превратились в невероятно сильное средство моделирования и получения данных из соцсетей, веб-страниц и ссылок, а также определения местоположения и маршрутов в GPS. Любой набор объектов, которые связаны друг с другом, можно сейчас представить с помощью графа.

В статье опишем 10 основных графовых алгоритмов, которые становятся очень полезными для анализа, а также области их применения.

Начнём с того, что приведём определение графа.

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

Граф состоит из конечного множества вершин (узлов) и набора рёбер, соединяющих эти вершины. Две вершины считаются смежными, если они соединены друг с другом одним и тем же ребром.