 |
Представление графа в памяти компьютера
|
|
|
|
Введение
Теория графов – важнейший математический инструмент, широко используемый в информатике, химии, генетике, исследовании операций, лингвистике, проектировании, так как посредством графов можно описывать разнообразные реальные явления – организацию транспортных систем, сети передачи данных, человеческих взаимоотношений, структуру гена или молекулы. Возможность формального моделирования такого множества разных реальных структур позволяет программисту решать широкий круг прикладных задач.
Разработка хорошего алгоритма «с нуля» – очень трудная задача. Часто достаточно правильно построить модель задачи и применить уже известный алгоритм, решающий задачу быстро и верно.
В рамках этого пособия разбираются основные алгоритмы на графах, решающие практические задачи. Для записи алгоритма используется как естественный язык, так и язык программирования C#.
Начальные понятия
Даже в период становления теории графов в ней возникало немало таких задач, решение которых предполагало построение некоторых алгоритмов. Достаточно вспомнить, например, задачу о кёнигсбергских мостах, которую решил в 1736 г. Л.Эйлер. В городе Кёнигсберге (нынешний Калининград) было два острова, соединенных семью мостами с берегами реки Преголя и друг с другом так, как показано на рисунке 1. Задача состояла в следующем: найти маршрут прохождения всех четырех частей суши, который начинался бы с любой из них, кончался бы на этой же части и ровно один раз проходил по каждому мосту. Исключительный вклад Л. Эйлера в решение этой задачи заключается в доказательстве, что такой маршрут построить невозможно.
Рис. 1. Парк в г. Кенигсберге Рис. 2. Граф к задаче о мостах
|
|
|
Эйлер обозначил каждую часть суши точкой (вершиной), а каждый мост линией (ребром), соединяющей соответствующие точки (см. рис. 2.). Полученная конструкция, состоящая из точек и соединяющих их ребер, со временем получила название граф.
Утверждение о том, что решения задачи о кенигсбергских мостах не существует, эквивалентно утверждению о невозможности обойти граф, представленный на рис. 2, проходя по каждому ребру в точности один раз. Отталкиваясь от этого частного случая, Эйлер обобщил постановку задачи и нашел критерий существования обхода у связного графа. На его основе позже был разработан алгоритм обхода связного графа.
Развитие теории графов в конце XIX и в начале XX в. было связано с распространением представлений о молекулярном строении вещества и становлением теории электрических цепей. Сейчас язык и методы теории графов используется не только в математике и традиционных приложениях в химии и электротехнике, но и в информатике, социологии, лингвистике, экономике, генетике. Очевидно, что алгоритмы для работы с графами очень важны.
Внедрение вычислительной техники поставило и перед всей математикой, и перед теорией графов проблему нахождения не произвольных алгоритмов, позволяющих решать те или иные классы задач, а таких алгоритмов, которые допускали бы практическую реализацию на компьютере. Так возникла проблема практической разрешимости задач: найти эффективный или хотя бы достаточно простой в практически важных случаях алгоритм решения задачи. В этом курсе лекций будут рассмотрены наиболее яркие и ценные алгоритмы на графах.
Основные определения
Приведем несколько основных определений и понятий.
Пусть V — непустое множество, [ V ] r — множество всех его r -элементных подмножеств.
Графом называется пара множеств G=(V, E), где E Í[V]2, то есть E — произвольное подмножество множества [V]2.
|
|
|
Элементы множества V называются вершинами графа G, а элементы множества E — его ребрами.
Рис. 3. Граф на множестве вершин V = {1,2,3,4,5,6,7}
со множеством ребер E = {{1, 2},{1, 6},{2,6},{3,5},{6,7}}
Множество вершин графа G обозначается через V (G), а множество его ребер — через E (G). Число вершин графа G будем обозначать через n (G), число ребер — через m (G). Очевидно, что максимальное число ребер в графе на n вершинах равно n (n -1)/2.
Говорят, что две вершины u и v графа смежны, если множество { u, v } является ребром, и не смежны в противном случае. Если e = { u, v } — ребро, то вершины u и v называют его концами. В этой ситуации говорят также, что ребро e соединяет вершины u и v, и что вершина u (или v) и ребро e инцидентны. Два ребра называются смежными, если они имеют общую вершину.
Подграфом графа G=(V, E) называется граф G 1 =(V1,E1): V1 Í V, E1 Í E, у которого все вершины и ребра принадлежат G.
Исключительную роль во многих прикладных задачах играет остовный подграф графа.
Остовный подграф — это подграф графа G, содержащий все его вершины.
Подграф G0 на подмножестве вершин V0Í V называется порожденным, если множество его ребер совпадает с множеством всех ребер графа G, оба конца которых принадлежат V0.
Графы удобно изображать в виде рисунков, состоящих из точек и линий, соединяющих некоторые из этих точек. При этом точки соответствуют вершинам графа, а линии, соединяющие пары точек — ребрам. Hа рисунке 4 изображен граф G и два его подграфа G 1 и G 2. G 1 — порожденный подграф G, а G 2 — нет. G 2 — остовный подграф G, а G 1 нет. Вершины 1 и 2 графа G смежные, а 1 и 3 нет. Также смежными являются ребра {1, 4} и {4, 5}. Вершина 1 инцидентна ребрам {1, 4} и {1, 2}.
Рис. 4.
При решении некоторых практических задач приведенное выше определение графа оказывается недостаточным, и приходится рассматривать более общие объекты. Многие задачи анализа программ, возникающие при оптимизации, трансляции, проверке правильности, тестировании и т.д., значительно упрощаются, если их рассматривать на теоретико-графовых моделях. В основе моделей лежит управляющий граф программы. Каждый оператор языка программирования изображается отдельной вершиной. Две вершины смежны, если между соответствующими операторами есть передача управления. Точнее, оператор, после которого производится передача управления, представляется началом дуги; оператор, на который передается управление, — концом дуги, каждая передача управления — дугой. Такие графы называются ориентированными.
|
|
|
Ориентированный граф состоит из конечного непустого множества V вершин и заданного набора X2 упорядоченных пар различных вершин. Элементы из X называются ориентированными ребрами или дугами.
Изучаются также мультиграфы.
Мультиграфом называется граф, в котором пары вершин могут соединяться более чем одним ребром; эти ребра называются кратными.
Если в мультиграфе ребра имеют ориентацию, то подобный граф называется ориентированным мультиграфом.
Дальнейшее обобщение состоит в том, что, кроме кратных ребер, допускаются еще и петли, то есть ребра, соединяющие вершину саму с собой. Такой граф называется псевдографом.
На рисунке 5 представлены описанные виды графов: G 1 — мультиграф, G 2 — псевдограф, G 3 — орграф. Следует отметить, что в литературе не существует единства терминологии, и поэтому надо быть внимательным к определениям при чтении различных источников.
Рис. 5. Мультиграф, псевдограф и орграф
Далее, как правило, под термином «граф» мы будем понимать именно обыкновенный граф, то есть конечный неориентированный граф без петель и кратных ребер.
Приведем примеры некоторых графов специального вида. Важную роль в теории графов имеет понятие полного графа, или клики.
Граф G называется полным (кликой), если любые две его вершины смежны.
Полный граф на n вершинах обозначается Kn. Для числа ребер полного графа выполняется равенство m(Kn) = 
.
Противоположным к понятию полного графа является понятие пустого графа.
Граф называется пустым, если в нем нет ребер. Пустой граф на n вершинах обозначается On.
На рисунке 6 приведены изображения полного и пустого графа на четырех вершинах.
Рис. 6.
На рисунке 7 показаны простые циклы Cn, (n = 3, 4) и простые пути Pn (n = 2, 3, 4). Очевидно, что K 2 = P 2, а K 3 = C 3.
Рис. 7. Простые циклы и простые пути
|
|
|
В теории графов наиболее изученными являются двудольные графы, к которым сводятся многие практические задачи, например, задача о назначениях.
Граф называется двудольным, если существует такое разбиение множества его вершин на две части (доли), что концы каждого ребра принадлежат разным частям.
Если при этом любые две вершины, входящие в разные доли, смежны, то граф называется полным двудольным. Полный двудольный граф, доли которого состоят из p и из q вершин, обозначается символом K p,q. На рисунке 8 изображен граф K 3,3 .
Рис. 8. Полный двудольный граф K 3,3
Представление графа в памяти компьютера
Выбор соответствующей структуры данных для представления графа имеет принципиальное значение при разработке эффективных алгоритмов. При решении задач используются следующие два стандартных способа представления графа G = (V, E): как набора списков смежных вершин или как матрицы смежности. Оба способа представления применимы как для ориентированных, так и для неориентированных графов. Обычно более предпочтительно представление с помощью списков смежности, поскольку оно обеспечивает компактное представление разреженных графов, т.е. таких, для которых число ребер гораздо меньше квадрата числа вершин.
Представление при помощи матрицы смежности предпочтительнее в случае плотных графов, т.е. когда число ребер близко к n(G)2, или когда нам надо иметь возможность быстро определить, имеется ли ребро, соединяющие две данные вершины. Например, алгоритм поиска кратчайшего пути для всех пар вершин использует представление графов именно в виде матриц смежности.
Представление графа G = (V, Е) в виде списка смежности использует массив Sp_reber из n(G) списков, по одному для каждой вершины из V. Для каждой вершины u Î V список Sp_reber [ u ] содержит все вершины v, такие что { u, v } Î Е, т.е. Sp_reber [ u ] состоит из всех вершин, смежных с u в графе G (список может содержать и не сами вершины, а указатели на них). Вершины в каждом списке обычно хранятся в произвольном порядке.
Рис. 9. Два представления неориентированного графа
На рис. 9 показано представление графа в виде списка смежности и в виде матрицы смежности. Аналогично, на рис. 10 показаны список и матрица смежности ориентированного графа.
Рис. 10. Два представления ориентированного графа
Если G — ориентированный граф, то сумма длин всех списков смежности равна m (G), поскольку ребру { u,v } однозначно соответствует элемент v в списке Sp_reber [ u ]. Если G —неориентированный граф, то сумма длин всех списков смежности равна 2 m (G), поскольку ребро { u, v }, будучи неориентированным, появляется в списке Sp_reber [ v ] как u, и в списке Sp_reber [ u ] — как v. Как для ориентированных, так и для неориентированных графов представление в виде списков требует объем памяти, равный O (n + m).
|
|
|
Представление графа G = (V, Е) с помощью матрицы смежности предполагает, что вершины перенумерованы в некотором порядке числами 1, 2,..., n. В таком случае представление графа G с использованием матрицы смежности представляет собой матрицу А размером n ´ n, такую что
На рис. 9 в) и 10 в) показаны представления с использованием матрицы смежности неориентированного и ориентированного графов, показанных на рис. 9 а) и 10 а) соответственно. Матрица смежности графа требует объем памяти, равный в n2, независимо от количества ребер графа. Ниже приведен листинг, иллюстрирующий реализацию графа в виде матирицы смежности.
public class graph
{
public int[,] matr_smeznosti;
public int kol_vershn; // количество вершин графа
// конструктор, считывающий граф из файла
public graph(string fileName)
{
int n, j;
string line;
char[] delimiterChars = new char[] { ',', ' ', ';', '.' };
using (StreamReader file = new StreamReader(fileName))
{
n = int.Parse(file.ReadLine()); // ввод размерности
this.kol_vershn = n;
this.matr_smeznosti = new int[n, n];
// ввод матрицы
for (int i = 0; (i < n) && ((line = file.ReadLine())!= null); i++)
{
string[] numbers = line.Split(delimiterChars, StringSplitOptions.RemoveEmptyEntries);
j = 0;
foreach (string numString in numbers)
{
int x;
bool canConvert = int.TryParse(numString, out x);
if (canConvert == true)
{
this.matr_smeznosti[i, j] = x;
j++;
}
}
}
}
} }
Листинг 1. Реализация графа в виде матрицы смежности
Списки и матрица смежности легко адаптируются для представления взвешенных графов, т.е. графов, с каждым ребром которых связан определенный вес, обычно определяемый весовой функцией w: Е " R. В этом случае, в каждый элемент списка добавляется весовое поле, а для матрицы смежности
Потенциальный недостаток представления при помощи cписков смежности заключается в том, что при этом нет более быстрого способа определить, имеется ли данное ребро (u, v) в графе, чем поиск v в списке Sp_reber [ u ]. Этот недостаток можно устранить ценой использования асимптотически большего количества памяти и представления графа с помощью матрицы смежности. Следует отметить, что простота последней делает ее предпочтительной при работе с небольшими графами.
Далее при представлении графов будем использовать оба способа в зависимости от решаемой задачи. Ниже приведен листинг, иллюстрирующий реализацию графа в виде списка смежности.
internal class rebro // внутренний класс ребро
{
public int v_na { get; set; } // смежная вершина
public int ves { get; set; } // вес ребра(если есть)
}
public class graph_edgeList
{
internal int kol_v_n { get; set; } // количество вершин графа
internal List<rebro>[] sp_reber;//массив списков смежных в-н
// конструктор, считывающий граф из файла
public graph_edgeList(string filename)
{
char[] separator = new char[] { '.', ' ', ',', ';' };
using (StreamReader f = new StreamReader(filename))
{
int n = int.Parse(f.ReadLine()); // количество вершин
sp_reber = new List<rebro>[n];
string line = f.ReadLine();
for (int i = 0; (i < sp_reber.Length) && (line!= null); i++)
{
List<rebro> rlist = new List<rebro>();
string[] values = line.Split(separator, StringSplitOptions.RemoveEmptyEntries);
if (values.Length > 0)
{
for (int j = 0; j < values.Length; j++)
{
int v = int.Parse(values[j]);
rebro r = new rebro { v_na = v};
rlist.Add(r);
}
}
line = f.ReadLine();
sp_reber[i] = rlist;
}
kol_v_n = n;
}
} }
Листинг 2. Реализация графа в виде списка смежности
Анализ алгоритмов
Неформальное определение алгоритма может быть следующим: алгоритм — это любая корректно определенная вычислительная процедура, на вход которой подается некоторая величина или набор величин, и результатом выполнения которой является выходная величина или набор значений. Таким образом, алгоритм представляет собой последовательность вычислительных шагов, преобразующих входные величины в выходные.
Алгоритмы – важнейшая часть информатики, при их изучении можно обойтись без компьютера или знания языка программирования. Но требуется как-то сравнивать алгоритмы, какой из них лучше, эффективнее. При оценке алгоритмов считается, что они выполняются на некоторой гипотетической машине, где для исполнения любой простой операции(+, *, –, =, if, call) требуется ровно один временной шаг, циклы и подпрограммы не считаются простыми операциями. Время выполнения цикла равно количеству его итераций, подпрограммы – количеству простых операций внутри. Исходные данные для решения любой задачи размещаются в памяти машины, будем называть их входом задачи. Размером (или длиною) входа считается число ячеек памяти компьютера, занятых входом. Считается, что память гипотетической машины неограничена, а время доступа занимает один временной шаг.
С помощью этой модели можно подсчитать для любого алгоритма число шагов, которые он затратит на решение экземпляра задачи. Заметим, что число шагов зависит от длины входных данных n. При анализе алгоритма любой задачи нас в первую очередь будет интересовать зависимость времени его работы от размера входа. Однако, это время зависит не только от размера входа, но и от других параметров задачи.
Например, на входе задачи n натуральных чисел a 1, a 2,..., an и требуется найти среди них число, кратное трем. Очевидный алгоритм решения состоит в следующем: будем проверять поочередно делимость элементов исходного списка данных на три, пока не встретится число ai, кратное трем. В зависимости от расположения такого элемента ai в списке исходных данных потребуется от 1 до n проверок на делимость. Наихудшим будет случай, когда подходящего числа в списке нет или оно расположено последним. При определении понятия трудоемкость алгоритма будем ориентироваться на такого рода наихудший случай.
Трудоемкость (временная сложность) алгоритма решения задачи – это функция f, которая ставит в соответствие каждому натуральному числу n максимальное число шагов (время работы) алгоритма f (n) на входных данных длины n.
Напрямую работать с функцией трудоемкости достаточно трудно, так как часто она требует слишком много информации для точного определения. Например, для некоторого алгоритма функция имеет вид: f ’(n) = 548 n 2 + 3792 n + 62log2 n + 2801. Точный анализ такой функции достаточно труден. Поэтому на практике пользуются асимптотическими обозначениями.
Говорят, что неотрицательная функция f (n) не превосходит по порядку функцию g (n), если существует такая константа c >0, что f (n) ≤ cg (n) для всех n ≥ n 0 при этом пишут f (n) = O (g (n)).
Алгоритм с трудоемкостью O (n), где n – длина входа, называют линейным. Линейный алгоритм ограниченное константой число раз просматривает входную информацию и по сути является неулучшаемым (по порядку) в смысле трудоемкости.
Алгоритм с трудоемкостью O (nc), где c – константа, называется полиномиальным. Согласно общепринятой точки зрения алгоритм является эффективным, если он имеет полиномиальную сложность.
Прежде всего в этом пособии будут рассматриваться полиномиальные алгоритмы.
Упражнения
1. Ориентированный граф хранится в виде списков смежности. Сколько операций нужно, чтобы вычислить исходящие степени всех вершин графа? А входящие степени?
2. Укажите представление с использованием списков смежности и матрицы смежности для графа K 3,3.
3. Транспонированием орграфа назовем операцию, при которой направление каждого ребра меняется на противоположное. Опишите эффективный алгоритм транспонирования орграфа, как для представления с использованием списков смежности, так и для матриц смежности. Проанализируйте время работы ваших алгоритмов.
4. Мультиграф G = (V, Е) хранится в виде списков смежных вершин. Опишите алгоритм со временем работы О (V + Е) для преобразования его в обычный граф G’ = (V’, Е’), при этом кратные ребра заменены обычными и удалены ребра-циклы.
5. Составьте таблицу в которой вычисляется время работы алгоритмов с трудоемкостью log(n), n, n log(n), n 2, n! на входных данных длиной n = 100, 1000, 104, 106, 108, 1010.
6. Предположим, что время исполнения алгоритма в наихудшем случае определяется как O (n 2), возможно ли, что для некоторых входных данных это время будет O (n)?
Алгоритмы обхода графа
Все основные служебные операции при работе с графами (например, преобразование графа из одного представления в другое, распечатка или рисование графа) предполагают его систематический обход, то есть посещение каждой вершины и каждого ребра графа. Если представить лабиринт в виде графа, где ребра – проходы, а вершины – точки пересечения проходов, то любой правильный алгоритм обхода графа должен найти выход из произвольного лабиринта. Наиболее известными из таких алгоритмов являются поиск в глубину (depth first search, DFS) и поиск в ширину (breadth-first search, BFS), причем они являются базисными для многих других алгоритмов решения прикладных задач, включающих обход графа, что и будет показано в дальнейшем.
Ключевая идея обхода графа – пометить каждую вершину при первом ее посещении и хранить информацию о тех вершинах, не все ребра из которых просмотрены. В мифах Древней Греции Тесей использовал клубок ниток, который ему дала Ариадна, для обхода лабиринта, мальчик-с-пальчик помечал пройденный путь камешками или крошками, для обхода графа будут применяться перечислимые типы. В процессе обхода графа каждая его вершина будет находиться в одном из трех состояний:
- неоткрытая – первоначальное состояние вершины;
- открытая – вершина обнаружена, но инцидентные ей ребра не просмотрены;
- обработанная (помеченная) – все ребра, инцидентные этой вершине посещены.
Понятно, что каждая вершина графа последовательно принимает все эти состояния. Первоначально открытой является только одна вершина – начало обхода графа.
Замечание: предложенные методы обходят все вершины, содержащиеся в одной компонете связности с начальной вершиной. Поэтому можно использовать любой из алгоритмов обхода для определения связности графа.
Поиск в ширину
Пусть задан граф G = (V, E) и выделена начальная вершина v. Алгоритм поиска в ширину систематически обходит все ребра графа G для «открытия» всех вершин, достижимых из v. В процессе обхода строится дерево поиска в ширину с корнем в начальной вершине, содержащее все достижимые вершины. Заметим, что расстояние (количество ребер) от корневой вершины до любой вершины этого дерева является кратчайшим.
Поиск в ширину имеет такое название, так как в процессе обхода графа помечаются все вершины на расстоянии k, прежде чем начнется обработка любой вершины на расстоянии k +1.
Алгоритм работает как для ориентированных, так и для неориентированных графов.
Идея алгоритма: все вершины, смежные с начальной, открываются, то есть помещаются в список, и получают единичную пометку. После этого начальная вершина обработана полностью и имеет пометку 2.
Следующей текущей вершиной становится первая вершина списка. Все ранее непомеченные вершины, смежные с текущей, заносятся в конец списка (становятся открытыми). Текущая вершина удаляется из списка и помечается числом 2. Процесс продолжается, пока список вершин не пуст. Такая организация списка данных называется очередью.
Рассмотрим пример. Исходный граф на левом рисунке. На правом рисунке рядом с вершинами в скобках указана очередность просмотра вершин графа. Ребра, образующие дерево поиска в ширину, выделены жирным.
Рис. 11. Просмотр вершин графа в процессе поиска в ширину.
При реализации поиска в ширину используется массив пометок Mark, массив предков Parent и очередь Q. Первоначально каждой вершине в массиве Mark соответствует значение 0, то есть вершина неоткрытая. Вершина открывается при первом посещение и ее пометка изменяется на 1. Когда все ребра, исходящие из вершины исследованы, то она считается обработанной и имеет пометку 2.
При просмотре списка вершин, смежных с текущей, открываются новые вершины. При этом их предком считается текущая вершина. Эта информация сохраняется в массиве Parent и позволяет восстановить дерево поиска в ширину. Для графа, изображенного на рисунке 11, массив предков будет иметь вид:
| Вершина | ||||||||
| Предок |
Граф задается матрицей смежности. Код алгоритма приведен на листинге 3.
public class BreadthFirstSearchAlgm
{ // Алгоритм обхода графа «Поиск в ширину»
public void BFS(graph g)
{
int[] Mark = new int[g.kol_vershn]; // массив пометок
int[] Parent = new int[g.kol_vershn]; // массив предков
for (int i = 0; i < g.kol_vershn; i++)
{
Mark[i] = 0;
Parent[i] = 0;
}
Console.WriteLine("Вершины в порядке обхода");
Queue<int> Q = new Queue<int>(); // создание очереди
int v = 0; // задание начальной вершины
Mark[v] = 1; // пометим нач. вершину
Q.Enqueue(v); // поместим нач. вершину в очередь
Console.Write("{0} ", v);
while (Q.Count!= 0) //Пока очередь не исчерпана
{ //взять из очереди очередную вершину
v = Q.Dequeue();
for (int i = 0; i < g.kol_vershn; i++)
{
if ((g.matr_smeznosti[v, i]!= 0) && (Mark[i] == 0))
{ // все непомеченные вершины,
Mark[i] = 1; // смежные с текущей, помечаются
Q.Enqueue(i); // и помещаются в конец очереди
Parent[i] =v; // v – предок открытой вершины
Console.Write("{0} ", i);
}
}
Mark[v] = 2; // вершина обработана
}
Console.WriteLine();
} }
Листинг 3. Обход графа в ширину
Трудоемкость данного алгоритма O (n 2), где n – количество вершин графа. Действительно, каждая вершина открывается и помещается в очередь только один раз, поэтому цикл по вершинам очереди выполняется не больше n раз. В цикл while вложен цикл по всем вершинам графа, который так же выполняется n раз. Если использовать представление графа в виде списков смежности, то трудоемкость была бы O (n+m), где m – количество ребер.
|
|
|
