При программировании вершины графа обычно сопоставляют числам от 1 до N, где - количество вершин графа, и рассматривают . Ребра нумерую числами от 1 до M, где . Для хранения графа в программе можно применить различные методы. Самым простым является хранение матрицы смежности, т.е. двумерного массива, скажем A, где для невзвешенного графа (или 1), если и (или 0) в противном случае. Для взвешенного графа A[i][j] равно весу соответствующего ребра, а отсутствие ребра в ряде задач удобно обозначать бесконечностью. Для неориентированных графов матрица смежности всегда симметрична относительно главной диагонали (i = j). C помощью матрицы смежности легко проверить, существует ли в графе ребро, соединяющее вершину i с вершиной j. Основной же ее недостаток заключается в том, что матрица смежности требует, чтобы объем памяти памяти был достаточен для хранения N2 значений, даже если ребер в графе существенно меньше, чем N2. Это не позволяет построить алгоритм со временем порядка O(N) для графов, имеющих O(N) ребер.
Этого недостатка лишены такие способы хранения графа, как одномерный массив длины N списков или множеств вершин. В таком массиве каждый элемент соответствует одной из вершин и содержит список или множество вершин, смежных ей.
Для реализации некоторых алгоритмов более удобным является описание графа путем перечисления его ребер. В этом случае хранить его можно в одномерном массиве длиной M, каждый элемент которого содержит запись о номерах начальной и конечной вершин ребра, а также его весе в случае взвешенного графа.
Наконец, при решении задач на графах, в том числе и с помощью компьютера, часто используется его графическое представление. Вершины графа изображают на плоскости в виде точек или маленьких кружков, а ребра -- в виде линий (не обязательно прямых), соединяющих соответствующие пары вершин, для неориентированного графа и стрелок - для ориентированного (если ребро направлено из u в v, то из точки, изображающей вершину u, проводят стрелку в вершину v).
Графы широко используются в различных областях науки (в том числе в истории!!!) и техники для моделирования отношений между объектами. Объекты соответствуют вершинам графа, а ребра -- отношениям между объектами). Подробнее об этой структуре данных можно прочитать в [5 - 7].
const nn=200;{число линий}
type myset = set of 0..nn;var i,m,n,k:byte; ss:array[1..nn] of myset; s,s1:myset;begin
…{считываем входные данные}
s:=[m]; k:=0; while not (n in s) and(k<nn-1) do begin k:=k+1;
s1:=s; s:=[]; for i:=1 to nn do if i in s1 then
{добавляем к s вершины,
достижимые из i} s:=s+ss[i] end; if n in s then writeln(k) else
writeln('it is impossible')
end.
Заметим, что предложенный при решении задачи 12 алгоритм можно модифицировать так, чтобы он находил длину кратчайшего пути от исходной вершины до всех других вершин графа, причем асимптотическое время его работы не изменится. Несмотря на хорошие временные характеристики, область применения алгоритма ограничена размером типа “множество” в Паскале. Избежать этого ограничения можно, используя такой способ представления графа как массив списков вершин, смежных с данной. О способах реализации динамических структур данных, и в частности списков, см., например, [8].
Пусть теперь требуется определить наличие пути сразу для всех пар вершин графа. Такая задача для невзвешенного графа называется транзитивным замыканием. Рассмотрим ее решение на примере следующей проблемы.
Краткость говорит здесь сама за себя. В результате выполнения трех вложенных циклов (то есть мы имеем алгоритм, работающий за N3 операций), порядок которых очень важен, в матрице a мы фактически получим ответ на вопрос задачи. Распечатать его можно так:
for i:=1 to nn do
for j:=1 to nn do
if a[i,j] xor c[i,j] then writeln(i,' ',j);
Если же требуется найти длины кратчайших путей для всех пар вершин, то, если каждому ребру графа приписать вес, равный единице, решение задачи будет полностью совпадать с решением той же задачи для взвешенного графа (см. далее). Поэтому отдельно мы рассматривать его не будем.
procedure way(i,j:integer);
{печатает путь между вершинами i и j}
begin
if w[i,j]=0 then write(' ',j)
{печатаем только вершину j,
чтобы избежать повторов}
else
way(i,w[i,j]); way(w[i,j],j)
end
end;
…{заполняем матрицу смежности}
for k:=1 to nn do
if a[i,k]+a[k,j]<a[i,j] then
a[i,j]:=a[i,k]+a[k,j];
w[i,j]:=k
write(i);
if i<>j then way(i,j);
writeln
Алгоритм Флойда хорош всем, кроме одного: он требует хранить матрицу смежности, а это не всегда возможно. Кроме того, для определения длины кратчайшего пути между двумя конкретными вершинами, его упростить невозможно (то есть все равно придется считать пути между всеми парами вершин). Если вес любого ребра в графе вычисляется по некоторой формуле (например, как расстояние между двумя точками на плоскости, если таковыми являются вершины нашего графа), то матрицу смежности можно не создавать вообще, а в процессе выполнения программы обращаться к функции вычисления веса ребра, соединяющего вершины i и j: a(i, j).
В этом случае для определение кратчайшего пути между вершинами s и t используют алгоритм Дейкстры [5 - 7]. Все вершины в процессе работы этого алгоритма разбиты на два множества: те, до которых кратчайший путь из вершины s уже известен (в программе они помечены значениями true одномерного булевского массива b) и все остальные. Cначала в первом множестве находится только вершина s. На каждом шаге к нему добавляется одна из вершин, текущее известное расстояние до которой минимально среди всех вершин из второго множества, обозначим ее p. Первоначально текущие расстояния (в программе они хранятся в одномерном массиве l) от s до остальных вершин равны , а расстояние до s равно 0, p также равна s. На очередном же шаге мы пытаемся улучшить длину пути до каждой из вершин второго множества, сравнивая выражения l[p]+a(p,i) и l[i]. Нужно показать, почему минимальное из значений l, рассматриваемых на текущем шаге, является длиной кратчайшего пути до соответствующей вершины, а, следовательно, этот путь содержит только вершины из первого множества. Если это не так, то есть кратчайший путь до этой вершины содержит и вершины из второго множества, то минимальной оказалась бы длина пути от s до одной из этих вершин. Значит кратчайший путь до вершины p проходит только через вершины первого множества и больше его пересчитывать не нужно.
Приведем схему программы, реализующей этот алгоритм (функцию a(i, j) и значение “бесконечности” определять не будем):
l[i]= ;
b[i]:=false
p:=s; l[s]:=0;
b[s]:=true;
f:=true;{cтоит ли искать дальше}
while (p<>t) and f do
f:=false;
if not b[i] then
if l[p]+a(p,i)<l[i] then l[i]:=l[p]+a(p,i);
min:=t;{важно, что b[t]=false}
for i:=1 to n do
if (not b[i])and(l[i]<l[min]) then min:=i;
if l[min]< then
p:=min; b[p]:=true; f:=true
Несложно подсчитать, что трудоемкость алгоритма составляет O(N2), что окупает некоторые сложности в его реализации. Как и в случае применения “волнового” алгоритма в невзвешенном графе, асимптотическая оценка не изменится если нам потребуется подсчитать длину пути от s до каждой из вершин графа. Поэтому, как и в алгоритме Флойда, длины кратчайших путей между всеми парами вершин могут быть рассчитаны за O(N3) операций.
Андреева Е., Фалина И. Системы счисления и компьютерная арифметика. М.: Лаборатория базовых знаний, 2000.
Станкевич А.С. Решение задач I Всероссийской командной олимпиады по программированию. “Информатика”, №12, 2001.
Окулов С.М. 100 задач по информатике. Киров: изд-во ВГПУ, 2000.
Андреева Е.В. Решение задач XIII Всероссийской олимпиады по информатике. “Информатика”, №19, 2001.
Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: “Вильямс”, 2000.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2000.
Липский В. Комбинаторика для программистов. М.: “Мир”, 1988.
Вирт Н. Алгоритмы и структуры данных. Санкт-Петербург: “Невский диалект”, 2001.
Страницы: 1, 2, 3