20 Вопрос. Обходы в графах.
Как и в случае обхода деревьев, для графов существуют два основных класса обходов: обходы в глубину и обходы в ширину.
Обходы в глубину пытаются каждый раз после прохождения некоторой вершины А выбрать в качестве следующей такую вершину В, в которую из вершины А ведет дуга. Таким образом, алгоритмы этого класса пытаются всегда двигаться вглубь графа, находя все новые не пройденные ранее вершины. Если таких непройденных вершин нет, то алгоритм возвращается к предыдущей, ранее пройденной вершине, и пытается найти очередную дугу, ведущую из нее в какую-либо другую еще не пройденную вершину. Если и таких вершин нет, то снова происходит откат назад, и так до тех пор, пока либо все вершины не будут пройдены, либо алгоритм вернется назад в вершину, выбранную в качестве исходной.
Обходы в ширину пытаются, начав с некоторой вершины, в качестве очередных рассматривать только вершины, непосредственно связанные с исходной. Только после того, как все такие вершины будут рассмотрены, алгоритм будет пытаться рассматривать следующий слой вершин, непосредственно связанных с только что пройденными. Таким образом, алгоритм обхода в ширину последовательно рассматривает все более удаленные от исходной вершины до тех пор, пока либо все вершины не будут пройдены, либо не останется больше вершин, достижимых из исходной.
21 Вопрос. Поиск кратчайших путей. Алгоритм Дейкстры.
Путем в графе называют чередующуюся последовательность вершин и дуг v1, e1, v2, e2,... vn-1 en-1, vn, в которой каждый элемент vi— вершина графа, а каждый элемент еi — дуга графа, ведущая из предыдущей вершины vi в следующую вершину vi+1|. Говорят, что такой путь соединяет вершину v1 с вершиной vn. Чаще всего рассматриваются простые пути, т. е. такие, в которых нет повторяющихся вершин, кроме, быть может, совпадения первой и последней вершины. В случае такого совпадения путь называется замкнутым или циклом.
Среди характеристик пути чаще всего рассматривается его длина— количество дуг в этом пути. Иногда с каждой дугой связывается некоторое число, которое можно интерпретировать как длину этой дуги. Граф в этом случае называется нагруженным, а длиной пути в нагруженном графе будет называться сумма длин входящих в этот путь дуг.
Алгоритм Дейкстры предназначен для нахождения кратчайшего пути между вершинами в неориентированном графе.
Идея алгоритма следующая: сначала выберем путь до начальной вершины равным нулю, заносим эту вершину во множество уже выбранных, расстояние от которых до оставшихся невы-бранных вершин определено. На каждом этапе находим следующую невыбранную вершину, расстояние до которой наименьшее, и соединенную ребром с какой-нибудь вершиной из множества выбранных (это расстояние будет равно расстоянию до уже выбранной вершины плюс длина ребра).
22 Вопрос. Определение путей и контуров Эйлера.
Путь Эйлера проходит по каждому ребру в графе только один раз. Контур Эйлера проходит каждое ребро в графе тоже один раз, а также начинается и заканчивается в одной и той же вершине (рис. 4). Многие уже знакомы с концепцией следующей простой головоломки — нарисовать какое-то очертание без отрыва ручки от бумаги.
Если серьезно, то поиск путей и контуров Эйлера имеет более практичное применение. Их можно использовать для проложения маршрута по каким-либо реальным сетям таким образом, что каждое ребро будет проходиться в точности один раз. Существуют некоторые свойства, которыми должен обладать граф, чтобы в нем имелся путь или контур Эйлера.
Рис. 4. Граф, который имеет путь Эйлера, и сам этот путь
Для существования контура Эйлера каждая вершина в графе должна иметь некоторую степень. Если любая вершина имеет нечетную степень, то сформировать контур Эйлера невозможно. В каждую вершину должны входить и из нее выходить только еще не пройденные ребра. Этого никогда не случится с вершиной, имеющей нечетную степень, потому что в нее можно войти, а выйти нельзя, поскольку все выходящие ребра уже пройдены.
Чтобы получить путь Эйлера, в графе должно быть точно две вершины с нечетной степенью. Путь должен начинаться и заканчиваться в вершине с нечетной степенью, потому что только эти вершины можно посетить дополнительное (для входа) количество раз.
Теперь очевидно, что для графа требуются ограничения. Граф не должен быть связанным. Однако этот граф должен содержать только один связанный подграф. Если граф содержит больше одного связанного подграфа, то он не может иметь путей или контуров Эйлера, так как некоторые ребра никогда не будут пройдены.
Любой граф, который удовлетворяет указанным условиям, должен иметь путь Эйлера или контур Эйлера. Такой граф называется эйлеровским.
Определение пути или контура Эйлера можно провести с использованием методики, похожей на глубинный поиск. Следующий алгоритм используется для поиска контура Эйлера, но его можно немного изменить, чтобы он позволял также находить путь Эйлера в любом графе, который удовлетворяет приведенным выше условиям.