Алгоритм топологической сортировки
Алгоритм генерирует последовательность согласованных меток для вершин бесконтурного орграфа G=(V,Е). В самом начале работы алгоритма антецеденты каждой вершины vзаписываются в множество A(v).
begin
forvV do
вычислитьA(v);
label:=0;
whileостаются неотмеченные вершины, для которыхA(v)= do
begin
label:= label+1;
u:= вершинасA(u)= ;
присвоить метку вершине u;
forкаждой неотмеченной вершины vVdo;
A(v):=A(v)\{u};
end
end Алгоритм присваивает метки вершинам. Каждая вершина получает очередную метку в том случае, если у нее нет неотмеченных антецедентов.
№35
Ориентированные графы успешно применяются для схематичного изображения транспортных линий, соединяющих города всего мира, или коммуникационных сетей между компьютерами
Пусть G=(V,Е) – орграф с пвершинами, а М – его матрица смежности. Напомним, что буквой И на пересечении i-той строки и j-гостолбца мы обозначаем наличие дуги от вершины с номером iк вершине с номером j. Дуга, по определению, является путем длины 1. Булево произведение матрицы М с самой собой обозначается через М2. В этой матрице буква И символизирует наличие пути длины 2. По матрице М3=М×М×М можно определить все пути длины 3, и вообще, матрица Мkхранит сведения о путях длины k. Наконец, в матрице достижимости М*=Мили М2или … или Мn, где n– максимальная длина пути, записаны пути любой длины между вершинами.
Пример 8.2. Вычислите матрицу достижимости орграфа, представленного на рис. 8.3.
Рисунок.22.
Решение. Прежде всего, запишем матрицу смежности орграфа:
M=
.
Квадрат матрицы M равен
M2
=
=
.
Заметим, что букваИ в матрице М2 соответствует путям длины 2 в орграфе G, а именно: abc, abdиbdc.
Дальнейшие вычисления приводят к третьей и четвертой степеням матрицы М:
M3=
;
M4
=
;
M*
=
.
Отметим, например, что букваИ в верхнем правом углу матрицы М* появляется из матрицы М2и соответствует пути abd.
M3= ; M4 = ; M* = .
Для больших орграфов вычисление матрицы М* с помощью возведения М всё в большую степень утомительно и неэффективно. Более удобный путь определения М*дает так называемый алгоритм Уоршелла.
алгоритм Уоршелла.
Этот алгоритм вычисляет матрицу достижимости W=М* ориентированного графа G=(V,Е) с матрицей смежности М.
begin
W:=M;
fork = 1to n do
fori = 1to n do
forj = 1to n do
W(i,j) = W(i,j)или(W(i,k)иW(k,j));
end
№36
Рассмотрим задачу поиска кратчайшего пути, связывающего пару вершин в нагруженном орграфе. Слово «кратчайший» здесь вполне уместно, поскольку довольно часто веса в орграфе – это расстояния между пунктами. Типичная ситуация, которая моделируется нагруженным орграфом – это транспортная или коммуникационная сеть.
Рассмотрим нагруженный граф, изображенныйна рис. 8.4. Он может представлять, например, длины дорог в километрах между шестью деревнями. Поскольку количество вершин в этом графе невелико, то перебрать все возможные пути между любой парой заданных вершин нам вполне по силам. При этом, естественно, мы найдем наиболее короткий путь, соединяющий соответствующие деревни.
Рисунок.23. Нагруженный граф