Пути в графе
Пусть А матрица смежности (aij=1, если имеется ребро между вершинами vi и vj). Рассмотрим матрицу А². Элементы этой матрицы равны числу различных путей длиной 2 из vi в vj через различные вершины vk. Аналогично матрица А³ задает число путей длиной 3 из vi в vj и т.д. Матрица Вⁿ = А+А²+А³+…+Аⁿ дает возможность определить число элементарных путей и элементарных циклов в графе, представленном матрицей смежности А.
Путевая матрица (матрица достижимости)
Если нас интересует, достижима ли вершина vj из вершины vi, и не интересует число путей из вершины vi в vj, то достаточно в матрице Вⁿ все ненулевые элементы поменять на 1. Тогда получим матрицу достижимости или путевую матрицу P. Матрицу P называют также транзитивным замыканием матрицы смежности. Рассмотренный способ определения путевой матрицы громоздок.
Кратчайшие пути из одной вершины
Кратчайшие пути из одной вершины
В заданном графе G=(V,E) для каждой вершины v поддерживается атрибут предшественник p[v], в роли которого выступает либо другая вершина, либо NULL. Далее для каждой вершины v поддерживается атрибут d[v], представляющий собой верхнюю границу веса, которым обладает кратчайший путь из истока s в вершину v. Назовем d[v] оценкой кратчайшего пути. Инициализация оценок кратчайших путей и предшественников производится в приведенной ниже процедуре, время работы которой равно Θ(V):
Кратчайшие пути из одной вершины
Initialize_Single_Source(G,s) { d[s] = 0; for (v=1; v < n; v++) do {d[v] = ∞; p[v] = NULL;} } Процесс ослабления ребра (u,v) заключается в проверке, нельзя ли улучшить найденный до сих пор кратчайший путь к вершине v, проведя его через вершину u, а также в обновлении атрибутов d[v] и p[v] при такой возможности улучшения. Ослабление может уменьшить оценку кратчайшего пути d[v] и обновить поле p[v] вершины v. Приведенный ниже код выполняет ослабление ребра (u,v):
Кратчайшие пути из одной вершины
Relax(u,v,w) { if (d[v] > d[u] + w(u,v)) { d[v] = d[u] + w(u,v);}}
Обходы графов. Поиск в ширину. Moore (1959 г.)
При поиске в ширину (breadth-first search, BFS) последовательно просматриваются, начиная с заданной вершины s (source), все вершины графа на расстоянии k=1, затем на расстоянии k+1 и т.д. В процессе обхода строится «дерево поиска в ширину» с корнем s, содержащее все достижимые вершины. Для каждой достижимой из s вершины v путь в дереве поиска в ширину соответствует кратчайшему пути от s до v в графе. Алгоритм работает как для ориентированных, так и для неориентированных графов.
Обходы графов. Поиск в ширину. Moore (1959 г.)
Для выполнения поиска в ширину удобно использовать очередь (queue). Очередь инициализируется стартовой вершиной поиска, помеченной как посещенной. На каждой итерации алгоритм находит все непосещенные вершины, смежные с вершиной в начале очереди, помечает их как посещенные и вносит в очередь, после этого вершина в начале очереди изымается из нее. Поиск в ширину полезно сопровождать построением леса поиска в ширину.
Обходы графов. Поиск в ширину. Moore (1959 г.)
Для отслеживания работы алгоритма поиск в ширину раскрашивает вершины графа в белый, серый и черный цвета. Изначально все вершины белые, и позже они могут стать серыми, а затем черными. Когда вершина открывается в процессе поиска, она окрашивается. Если вершина u черная смежная с ней вершина v либо серая, либо черная, т.е. все вершины, смежные с черной, уже открыты. Серые вершины могут иметь белых соседей, представляя собой границу между открытыми и неоткрытыми вершинами.
Обходы графов. Поиск в глубину
Обходы графов. Поиск в глубину
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.