Структура данных — это специальное решение для организации данных, которое предоставляет место для размещения элементов и возможность для их сохранения и извлечения
Структура данных — это специальное решение для организации данных, которое предоставляет место для размещения элементов и возможность для их сохранения и извлечения
Это свойство позволяет использовать простую очередь вместо очереди с приоритетами. Неплохо, учитывая, что время добавления и удаления элемента для первой в худшем случае равно O(1) (тогда как для куч, например, эти операции выполняются за O(log(n))), что обеспечивает линейное время работы BFS. В худшем случае оно будет линейно зависеть от наибольшего числа вершин и ребер, то есть O(|V| + |E|). Для связных графов эту оценку можно упростить до O(|E|).
В листинге 14.2 показан псевдокод, реализующий алгоритм поиска в ширину (Breadth First Search, BFS), целью которого, как следует из названия, является максимально возможное расширение поиска, сохранение периметра уже посещенных вершин и расширение этого периметра до соседних вершин.
Свойство частичной упорядоченности DAG обеспечивает возможность топологической сортировки — упорядочения вершин таким образом, что для любого ребра в графе его начальная точка находится перед конечной.
Граф называется связным, если для любой пары его вершин (u, v) существует последовательность вершин u, (w1... wk), v, где k ≥ 0, такая, что любые две смежные вершины в последовательности соединены ребром.
Неориентированный граф легко представить в виде ориентированного графа, разложив каждое неориентированное ребро (u, v) на пару ориентированных ребер (u, v) и (v, u).
Обратное обычно неверно, и многие ориентированные графы нельзя преобразовать в неориентированные изоморфные аналоги 285 .
Имея это в виду, дадим определение, которое пригодится далее в этом разделе: граф G = (V, E) называется разреженным, если |E| = O(|V|); граф G называется плотным, если |E| = O(|V|2).
