Graph
·
Граф - структура данных, в которой есть вершины и рёбра, которые их соединяют. Граф подразделяют с помощью разных видов ребёр:
- наличие направления - направленные / ненаправленный
- отдельно стоят графы с циклами и без циклов (DAGs)
- наличие весов на рёбрах
Типовые действия над графом:
- Найти несвязные подграфы. Решается с помощью disjoint set.
- Обойти весь граф в глубину (сначала один путь до конца) или в ширину (нарезая как бы по уровням).
- Найти кратчайшее расстояние между двумя вершинами. Здесь помогает алгоритм Дийкстры, алгоритм Bellman Ford и A*.
- Отсортировать граф топологически. Звучит сложно, но факту это составить дерево зависимостей или убедиться что это нельзя сделать из-за цикла.
Где потренироваться
Обратные ссылки
Структуры данных
В рамках computer science рассматриваются два основных вопроса - собственно структуры данных и алгоритмы поверх...
The Definition of “graph” and Terminologies
graph is a non-linear data structure consisting of vertices and edges. There are a lot...
Tree structure
Дерево - это частный вид графа, а именно связный и ацикличный. Благодаря этим свойствам, его...