Архив категории ‘Алгоритмы поиска на графах’

Алгоритм Ярника — Прима — Дейкстры

    На этом шаге мы рассмотрим алгоритм Ярника - Прима - Дейкстры.     Перейдем к рассмотрению алгоритма Ярника - Прима - Дейкстры, основанного на применении стратегии 2. Впервые он появился в работе Ярника, опубликованной в 1930 году, затем был переоткрыт Примом в 1957 году и независимо Дейкстрой в 1959 году. Заметим, что Дейкстра предложил очень […]

Задача о минимальном остове

    На этом шаге мы рассмотрим задачу о минимальном остове.     Пусть G = (V, Е) - связный обыкновенный граф. Напомним, что его остовом называется остовный подграф, являющийся деревом. Остов (n, m)-графа легко найти поиском в глубину или поиском в ширину. Поскольку оба поиска имеют сложность O(m + n) и в связном графе m > […]

Алгоритм отыскания эйлеровой цепи в эйлеровом графе

    На этом шаге мы рассмотрим алгоритм отыскания эйлеровой цепи в эйлеровом графе.     Напомним, что замкнутая цепь в графе G называется эйлеровой, если она содержит все ребра и все вершины графа. Связный неодноэлементный граф эйлеров тогда и только тогда, когда каждая его вершина имеет четную степень.     Этот шаг посвящен построению и анализу алгоритма, […]

Поиск в ширину

    На этом шаге мы рассмотрим поиск в ширину.     Рассмотрим еще один способ систематического обхода всех вершин обыкновенного графа G, называемый поиском в ширину. Для описания поиска в ширину введем в рассмотрение очередь Q, элементами которой являются вершины графа G. Поиск начинается с некоторой вершины v. Эта вершина помещается в очередь Q и с […]

Алгоритм отыскания компонент сильной связности в орграфе

    На этом шаге мы рассмотрим алгоритм отыскания компонент сильной связности в орграфе.     Пусть G = (V, Е) - связный орграф. Алгоритм 1 легко приспособить для организации поиска в глубину в орграфе G. Для этого нужно лишь список list(v) заменить списком list(v'), состоящим из концов всех дуг, выходящих из вершины v. Все понятия, связанные […]

Алгоритм отыскания блоков и точек сочленения

    На этом шаге мы рассмотрим алгоритм отыскания блоков и точек сочленения.     Пусть G = (V, Е) - обыкновенный связный граф. Определено отношение ≈ на множестве ребер Е графа G: e ≈ f ⇔ e=f или e, f лежат на некотором цикле.     Это отношение является эквивалентностью, причем каждый его класс совпадает с множеством […]

Поиск в глубину

    На этом шаге мы рассмотрим поиск в глубину.     Многие алгоритмы на графах основаны на систематическом переборе всех вершин графа, при котором каждая вершина просматривается в точности один раз. Здесь мы рассмотрим два стандартных и широко используемых метода такого перебора: поиск в глубину и поиск в ширину. Оба метода изучаются применительно к обыкновенным графам, […]