§26 Алгоритмы на графах

Графы. Общие сведения

Из теории графов

Граф — это абстрактный объект, представляющий собой множество вершин (узлов) и набор рёбер – связей (соединений) между парами вершин. Тема графов очень обширна. Только терминологии графов посвящена цела страничка в Википедии [1]. Графы являются предметом изучения в дискретной математике (где дается более точное определение понятия графа). Графы применяются для описания сложно структурированной информации и, поэтому имеют огромное прикладное значение. Появлению графов в математике способствовали труды Эйлера.
Где мы встречаемся с графами? Наверное проще сказать где мы с ними не встречаемся. Вот лишь небольшой перечень, который сразу приходит на ум:

  • Модель локальной или глобальной сети
  • Блок-схема алгоритма
  • Принципиальная электрическая схема
  • Генеалогическое древо
  • Схема метрополитена
  • Модель связей в базе данных
  • Диаграммы Фейнмана
  • Ментальные карты

и очень многие другие вещи. Поднять всю теорию графов на этом уроке не представляется возможным, поэтому мы отправляем вас к списку (популярной) литературы на этой странице. Здесь же мы рассмотрим лишь те базовые понятия, которые нам пригодятся при составлении программ для работы с этой фундаментальной структурой.
Граф G — это упорядоченная пара G:=(V,E), где V — это непустое множество вершин (или узлов), а E — множество пар вершин, называемых рёбрами. Вершины и рёбра графа называются также элементами графа, число вершин в графе |V|порядком, число рёбер |E|размером графа.

Рис. 1. Неориентированный граф

Рис. 2. Дерево – это связный ацикличный граф

Глоссарий

Здесь мы сделали небольшую выборку терминов из теории графов (раздел дискретной математики), сама же дисциплина не обладает устоявшейся терминологией [2].

Базовая терминология
Рус En Описание
Вершина vortex Элемент графа
Узел node Тоже, что и вершина
Ребро edge Связь двух соседних вершин
Дуга arc Тоже, но в орграфе
Связь link Элемент графа (ребро или дуга)
Смежность adjacent О двух вершинах между которыми есть связь
Инцидентность incident on О ребре по отношению к вершине
Степень degree Число ребер инцидентных вершине
Основные понятия
  • Маршрут в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершиной ребром
  • Цепью называется маршрут без повторяющихся рёбер. Простой цепью называется маршрут без повторяющихся вершин (откуда следует, что в простой цепи нет повторяющихся рёбер)
  • Ориентированным маршрутом (или путём) в орграфе называют конечную последовательность вершин и дуг, в которой каждый элемент инцидентен предыдущему и последующему
  • Циклом называют цепь, в которой первая и последняя вершины совпадают (На рис. 1 ACD и ACDE – циклы)
  • Длину пути (или цикла) называют число составляющих его рёбер
  • Путь (или цикл) называют простым, если рёбра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются
Разновидности графов
  • Ориентированный граф – (кратко орграф) — граф, рёбрам которого присвоено направление (рис. 4)
  • Неориентированный граф – граф в котором пара вершин не является упорядоченной (рис. 3)
  • Связный граф — граф в котором между любой парой вершин существует как минимум один путь
  • Дерево — это связный ациклический граф, т.е. отсутствуют циклы и между парами вершин имеется только по одному пути (рис. 2). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода называются листьями.
  • Взвешенный граф – граф в котором каждому ребру поставлено в соответствие некоторое число, называемое весом ребра

Методы представления графа

Для представления графа используется несколько способов. Для обхода графа нужно использовать такой из них, который позволит решить вашу задачу наиболее эффективно. В большинстве своем, выбор будет между матрицей смежности и списком смежности (ниже в таблице приводится сравнение эффективности обоих подходов). При этом, вы можете моделировать как свои собственные структуры данных, опираясь на встроенный Си-массив, так и использовать уже имеющееся в STD большое разнообразие контейнеров.

Матрица смежности

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента a[i][j] равно единице, если i-я и j-я вершины графа являются смежными, иначе значение равно нулю. Такая матрица называется бинарной. Для простого графа элементы главной диагонали равны 0.
Матрица смежности подходит как для описания орграфа, так и для описания неориентированного графа. Для неориентированного графа значения элементов симметричны относительно главной диагонали. Симметрия матрицы смежности является её плюсом в плане экономии памяти, т. к. достаточно сохранить только половину матрицы (элемент a[i][j] == a[j][i]).
Использование матрицы смежности предпочтительно только в случае неразреженных графов, с большим числом рёбер, так как она требует хранения по одному биту данных для каждого элемента. Если граф разрежён, то большая часть памяти будет тратиться впустую на хранение нулей, зато в случае неразреженных графов матрица смежности достаточно компактно представляет граф в памяти, используя примерно n2 бит памяти, что может быть на порядок лучше списков смежности (см ниже).
В алгоритмах, работающих со взвешенными графами, элементы матрицы смежности вместо чисел 0 и 1, указывающих на присутствие или отсутствие ребра, часто содержат веса самих рёбер. При этом на место отсутствующих рёбер ставят некоторое специальное граничное значение (англ. sentinel), зависящее от решаемой задачи, обычно 0 или inf.

Матрицы смежности для орграфа и неориентированного графа

Рис. 3. Неориентированный граф

Рис. 4. Орграф

Для реализации матрицы смежности используется массив массивов: вектор векторов (vector<bool>), или вектор битсетов (если размер графа известен и изменяться не будет), или словарь, в котором ключ – номер вершины, а значение битсет (или vector<bool>, если на этапе компиляции размер битсета неизвестен). Если граф не предполагается расширять, то вектор целесообразно заменить на array.

Матрица инцидентности

Матрица инцидентности — форма представления графа, в которой указываются связи между инцидентными элементами графа (ребро – вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Отсюда, матрица не является квадратной. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).
В случае ориентированного графа каждая дуга в соответствующем столбце имеет значение «−1» в строке исходящей вершины x и «1» в строке входящей вершины y; если связи между вершиной и ребром нет, то в соответствующая ячейка имеет значение «0».

Матрицы инцидентности для орграфа и неориентированного графа

Рис. 5. Неор. граф

Рис. 6. Орграф

Применяется данный метод (из-за перерасхода памяти) крайне редко, в основном, для поиска циклов. Размер памяти пропорционален O(|V||E|).

Список смежности

Список смежности — способ представления графа в виде коллекции списков вершин («список списков») – каждой вершине графа соответствует список смежных вершин. Например, граф на рис. 1 мы можем описать следующим списком смежности:

a: {b, c, d, e}
b: {a}
c: {a, d}
d: {a, c, e}
e: {a, f}
f: {e}

Это наиболее удобный способ как для представления разреженных графов, так и реализации базовых алгоритмов обхода графа в ширину или глубину, где нужно быстро получать «соседей» текущей просматриваемой вершины.

Сравнение с матрицей смежности
Операция Список смежности Матрица смежности
Проверка на наличие ребра (x,y) O(|V|+|E|) O(1)
Определение степени вершины O(1) O(|V|)
Использование памяти для разреженных графов O(|V|+|E|) O(|V|2)
Обход графа O(|V|+|E|) O(|V|2)

Реализация списков смежности может быть выполнена, аналогично матрице смежности за той лишь разницей, что список может иметь переменную дину. Например, с помощью вектора векторов или может быть использован словарь (map) в котором ключ – номер вершины, а значение – список смежных вершин, реализованный подходящим последовательным контейнером. Если граф является взвешенным, то информацию о весе ребра можно передавать как пару (std::pair) {номер_вершины, вес_ребра,_инцидентного_этой_вершине}. В качестве списка может выступать любой последовательный контейнер или словарь (для взвешенных графов).

Список ребер

Список ребер – это массив, в котором каждому ребру графа (элемент массива) соответствует список, в которой хранятся две вершины (std::pair), инцидентные ребру. Это наиболее компактный способ представления графов, поэтому часто применяется для внешнего хранения или обмена данными. Если необходимо хранить и вес, то элемент списка представляет собой кортеж (std::tuple) трех элементов (x, y, weight). Размер занимаемой памяти: O(|E|).

Поиск кратчайшего пути в графе

Ниже мы рассмотрим лишь самые известные алгоритмы в их нерекурсивном варианте. Рекурсию не рекомендуется применять в случае если граф очень большой. Для простоты чтения программного кода методы оптимизации контейнеров не используются.

Алгоритм Флойда-Уоршелла

Алгоритм Флойда-Уоршелла разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом. Он служит для нахождения кратчайших путей между всеми парами вершин графа.
Основная идея алгоритма. Пусть есть три вершины i, j, k и заданы расстояния между ними. Если выполняется неравенство

A[i,k] + A[k,j] < A[i,j],

то целесообразно заменить путь i => j путем i => k => j. Такая замена выполняется систематически в процессе выполнения данного алгоритма и называется релаксацией. Такой же подход используется в алгоритме Дейкстры (см. ниже).
В программе используется вспомогательный массив, для определения кратчайших путей. Значения исходной матрицы заменяются значениями этих кратчайших путей. Иными словами, матрица смежности будет заменена матрицей кратчайших путей.

Рис. 7. Взвешенный ориентированный граф для иллюстрации в программе 26.1 алгоритма Флойда-Уоршелла

Программа 26.1

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

void FloydWarshall(vector<vector<int>>&);

int main() {
	// Матрица смежности
	vector<vector<int>> G {
		{0, 4, 0, 2, 2, 0, 0, 0, 0},
		{0, 0, 7, 0, 0, 3, 0, 0, 0},
		{0, 0, 0, 0, 0, 2, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 1, 1, 0},
		{0, 2, 0, 3, 0, 2, 0, 6, 1},
		{0, 0, 0, 0, 0, 0, 0, 0, 2},
		{0, 0, 0, 0, 0, 0, 0, 5, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 5},
		{0, 0, 0, 0, 0, 0, 0, 0, 0}
	};

	FloydWarshall(G);
	for (auto &i: G) {
		for (auto &j: i)
			cout << j << setw(3);
		cout << "\n";
	}
	return 0;
}

void FloydWarshall(vector<vector<int>> &myG){

	int inf = 1000000000;
	size_t k, i, j, w = myG.size();
	vector<vector<int>> minP = myG;

	// Устанавливаем в вершины где нет путей inf
	for (i = 0; i < w; i++)
		for (j = 0; j < w; j++)
			if (minP[i][j] == 0 && i != j)
				minP[i][j] = inf;
	// Собственно реализация алгоритма Флойда-Уоршелла
	for (k = 0; k < w; k++)
		for (i = 0; i < w; i++)
			for (j = 0; j < w; j++)
				if (minP[i][k] + minP[k][j] < minP[i][j])
					myG[i][j] = minP[i][k] + minP[k][j];
}

Вывод:

0  4 11  2  2  4  3  8  3  
0  0  7  0  0  3  0  0  5  
0  0  0  0  0  2  0  0  4  
0  0  0  0  0  0  1  1  6  
0  2  9  3  0  2  4  4  1  
0  0  0  0  0  0  0  0  2  
0  0  0  0  0  0  0  5 10  
0  0  0  0  0  0  0  0  5  
0  0  0  0  0  0  0  0  0 

Алгоритм Флойда — Уоршелла является эффективным для расчёта всех кратчайших путей в плотных графах, когда имеет место большое количество пар рёбер между парами вершин. В случае разреженных графов с рёбрами неотрицательного веса лучшим выбором считается использование алгоритма Дейкстры для каждого возможного узла. При таком выборе сложность составляет O(|V||E|log⁡|V|, что лучше, чем O(|V|3) алгоритма Флойда — Уоршелла тогда, когда |E| << |V|2 (условие плотности графа).

Алгоритм Дейкстры

Алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации.
Формальное определение алгоритма: дан взвешенный ориентированный граф G(V,E) без дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины a графа G до всех остальных вершин этого графа.
Идея алгоритма. Определяем массив D[], в котором для каждой вершины v будем хранить текущую длину D[v] кратчайшего пути из s в v. Изначально D[s]=0, а для всех остальных вершин эта длина равна бесконечности (некоторое значение, заведомо большее возможной длины пути):
Кроме того, для каждой вершины v будем хранить, помечена она ещё или нет, т.е. определим булевский массив U[]. Изначально все вершины не помечены, т.е. элементы массива имеют начальное значением false.
Сам алгоритм Дейкстры состоит из n итераций (по количеству вершин). На очередной итерации выбирается вершина v с наименьшей величиной D[v] среди ещё не помеченных.
Выбранная, таким образом, вершина v отмечается помеченной. Далее, на текущей итерации, из вершины v производятся релаксации: просматриваются все рёбра (v,to), исходящие из вершины v, и для каждой такой вершины to алгоритм пытается улучшить значение D[to]. Пусть длина текущего ребра равна len, тогда в виде кода релаксация выглядит как:

D[to] = min(D[to], D[v] + len)

В конце концов, после n итераций, все вершины графа станут помеченными, и алгоритм завершит свою работу.
Стоит заметить, что, если не все вершины графа достижимы из вершины s, то значения D[v] для них так и останутся бесконечными. Понятно, что несколько последних итераций алгоритма будут как раз выбирать эти вершины, но никакой полезной работы производить эти итерации не будут (поскольку бесконечное расстояние не сможет прорелаксировать другие). Поэтому алгоритм можно сразу останавливать, как только в качестве выбранной вершины берётся вершина с бесконечным расстоянием.

Рис. 8. Взвешенный граф для иллюстрации работы в программе 26.2 алгоритма Дейкстры

Программа 26.2

#include <iostream>
#include <vector>
using namespace std;

void Dijkstra(vector<vector<pair<int, int>>>&, int&);

int main() {
	//==========================================================//
	// Список смежности	(рис. 8)								//
	// представляет собой вектор векторов пар.					//
	// Первый элемент пары смежная вершина (в массиве 1-я - 0),	//
	// а второй элемент - вес инцидентного ребра				//
	//==========================================================//
	vector<vector<pair<int, int>>> G {
		{ {1, 1}, {3, 6} 				 				 },	// 1
		{ {0, 1}, {2, 4}, {3, 3}, {4, 9}, {5, 8}, {6, 7} },	// 2
		{ {0, 6}, {1, 4} 								 },	// 3
		{ {1, 3}, {4, 2} 								 },	// 4
		{ {3, 2}, {1, 9} 								 },	// 5
		{ {1, 8}, {6, 5}								 },	// 6
		{ {1, 7}, {5, 5}								 }	// 7
	};
	int vortex;
	cout << "Введите номер вершины: ";
	cin >> vortex;
	Dijkstra(G, vortex);

	return 0;
}

void Dijkstra(vector<vector<pair<int, int>>> &myG, int &s) {
	// Определяем значение infinity
	const int inf = 2000000000;
	size_t n = myG.size();
	//==========================================================//
	// Определяем три массива:									//
	// D - для хранения кратчайших путей в графе от исходной	//
	// P - для хранения промежуточных итогов длин путей			//
	// U - для хранения булевских флагов посещения вершин		//
	//==========================================================//
	vector<size_t> D(n, inf);
	vector<size_t> P(n);
	vector<bool> U(n, false);
	// Исходная вершина (в данном случае первая)
	// s = 0;
	D[s] = 0;
	for (size_t i = 0; i < n; i++) {
		// Определяем уникальное значение стартовой вершины
		// Количество вершин не должно превышать это значение
		size_t v = 1000000000;
		for (size_t j = 0; j < n; j++)
		if (!U[j] && (v == 1000000000 || D[j] < D[v]))
				v = j;
		// Выходим, если встретился хоть один inf,
		// что значит: кратчайших маршрутов больше не найдено
		if (D[v] == inf)
			break;
		// Говорим, что посетили вершину
		U[v] = true;
		// Определяем итераторы по текущему списку
		auto beg = myG[v].begin();
		auto lst = myG[v].end();
		while (beg != lst) {
			auto to = beg -> first;
			auto len = beg -> second;
			// Этот процесс называют "релаксацией", т. е.
			// поиск как можно меньшего пути,
			// что повторяет алгоритм Флойда — Уоршелла
			if (D[v] + len < D[to]) {
				D[to] = D[v] + len;
				P[to] = v;
			}
			beg++;
		}
	}
	// Выводим список кратчайших маршрутов от
	// исходной вершины ко всем остальным:
	for (auto &r : D)
		cout << r << " ";
	cout << endl;
}

Примечание. Восстановить путь до любой вершины можно так, как показано в программе 26.3 (стартовая вершина не добавляется в массив, поэтому её нужно добавить отдельной инструкцией).

Обход графа в ширину

Поиск в ширину (англ. breadth-first search, BFS) — метод обхода графа и поиска пути в графе. Поиск в ширину был формально предложен Э. Ф. Муром в контексте поиска пути в лабиринте. Ли (1961 г.) независимо открыл тот же алгоритм в контексте разводки проводников на печатных платах. Алгоритм обхода графа в ширину находит путь кратчайшей длины в невзвешенном графе, т. е. путь, содержащий наименьшее число рёбер. Граф может быть как ориентированным, так и неориентированным. Список смежности идеально подходит для работы с алгоритмом BFS. Временная сложность алгоритма O(n+m), где n — число вершин, m — число рёбер.
Работу алгоритма можно представить как распространение круга пламени от источника возгорания. Пусть источником возгорания будет вершина s. Далее, на каждом следующем шаге, огонь перекидывается с каждой уже горящей вершины на всех её соседей. За одну итерацию алгоритма происходит расширение "кольца огня" в ширину на единицу (отсюда и название алгоритма).
Для реализации алгоритма используется структура данных очередь. Идея алгоритма. Создадим очередь q, в которую будут помещаться горящие вершины, а также определим булевский массив used[], в котором для каждой вершины будем отмечать, горит она уже или нет, иными словами, была ли она посещена.
Изначально в очередь помещается только вершина s, и used[s] = true, а для всех остальных вершин used[] = false. Затем алгоритм представляет собой цикл: пока очередь не пуста, достать из её головы одну вершину, просмотреть все смежные с ней вершины, и если какие-то из просмотренных вершин ещё не горят, то поджечь их и поместить в конец очереди. В итоге, когда очередь опустеет, обход в ширину обойдёт все достижимые из s вершины, причём до каждой дойдёт кратчайшим путём.
Для подсчета длины кратчайших путей необходимо определить массив длин путей D[], а для определения кратчайшего пути из одной вершины в другую - массив "предков" P[], в котором для каждой вершины сохранять номер вершины, из которой мы попали в эту вершину.

Рис. 9. Неориентированный граф для иллюстрации работы в программе 26.3 алгоритма BFS

Программа 26.3

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void BFS(vector<vector<int>>&, int&, int&);

int main() {
	// Список смежности (рис. 9)
	vector<vector<int>> G {
		{1, 4, 5}, {0, 6}, {3, 5}, {2, 7},
		{0, 5, 9}, {0, 2, 4, 9, 10}, {1, 11}, {3, 10},
		{9, 13}, {4, 5, 10, 12}, {5, 7, 9, 15}, {6, 14},
		{9}, {8, 14}, {11, 13}, {10}
	};
	int start, finish; // стартовая и конечная вершины
	cout << "Введите стартовую вершину => "; cin >> start;
	cout << "Введите конечную вершину => ";  cin >> finish;
	BFS(G, start, finish);
	return 0;
}

void BFS(vector<vector<int>> &myG, int &s, int &fin) {
	size_t n = myG.size(); // число вершин
	queue<int> Q; // подготовим очередь
	// и поместим в нее исходную вершину
	Q.push(s); 
	vector<bool> used(n, false);
	// если нужно сохранять длины путей
	// то определяем и массив D[]:
	// vector<int> D(n);
	vector<int> P(n);
	used[s] = true;
	P[s] = -1;
	// Пока очередь не пуста
	while (!Q.empty()) {
		// Берем элемент вначале очереди
		int v = Q.front();
		Q.pop();
		for (size_t i=0; i < myG[v].size(); ++i) {
			// Осматриваем соседей
			int to = myG[v][i];
			// если не заходили к ним,
			if (!used[to]) {
				// то заходим
				used[to] = true;
				// и ставим их в очередь
				Q.push(to);
				// увеличиваем и сохраняем длину,
				// если нужно
				// D[to] = D[v] + 1;
				// запоминаем номер откуда пришли
				P[to] = v;
			}
		}
	}
	// Определение и вывод пути
	// из вершины s в вершину fin
	// включительно
	if (!used[fin])
		cout << "Пути нет!";
	else {
		vector<int> path;
		while (fin != -1) {
			path.push_back(fin);
			fin = P[fin];
		}
		auto first = path.crbegin();
		auto last  = path.crend();
		cout << "Путь: ";
		while (first != last)
			cout << *first++ << " ";
	}
}

Обход графа в глубину

Поиск в глубину (англ. Depth-first search, DFS) является наиболее важным алгоритмом, который применяется для решения многих трудных задач обхода графов: проверки связности, поиска цикла и компонент сильной связности, для топологической сортировки. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Сложность алгоритма O(N+M).
Для реализации алгоритма используется структура данных стек. Идея алгоритма. Поиск начинается с некоторой фиксированной вершины s. Далее рассматривается вершина v смежная с s. Она выбирается и отмечается как посещенная. Остальные смежные вершины (если они есть и они не посещены) отправляются в стек и ожидают следующего захода в родительскую вершину. Далее берется вершина q смежная с v. Действия повторяются. Так процесс будет продвигаться вглубь графа пока не достигнет вершины u такой, что не окажется вершин смежных с ней и не посещенных ранее. Если такая вершина получена, то осуществляется возвращение к вершине, которая была ранее (до неё) и там производится определение доступной вершины. В том случае, когда мы вернулись в вершину s, а все смежные вершины с ней уже посещены то алгоритм завершает свою работу.

Рис. 10. Граф для иллюстрации работы в программе 26.4 алгоритма DFS

Программа 26.4

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int DFS(vector<vector<int>>&, int&, int&);

int main() {
	// Список смежности графа на рис. 10
	vector<vector<int>> G {
		{1, 2, 3},
		//----------------------------------------------
		{0, 4, 5}, {0, 6, 7}, {0, 8, 9},
		//----------------------------------------------
		{1, 10, 11, 12}, {14, 13, 14}, {2, 15}, 
		{2, 16, 17}, {3}, {3, 18},
		//----------------------------------------------
		{4}, {4}, {4, 19, 20}, {5}, {5}, {6, 21, 22, 23},
		{7, 24, 25}, {7, 26, 27}, {9, 28, 29},
		//-----------------------------------------------
		{12}, {12}, {15}, {15}, {15}, {16}, {16}, {17}, 
		{17}, {18}, {18}
		//-----------------------------------------------
	};

	int start, finish; // стартовая и конечная вершины
	cout << "Введите стартовую вершину => "; cin >> start;
	cout << "Введите конечную вершину => ";  cin >> finish;
	cout << "Длина /*кратчайшего*/пути из вершины "
		 << start
		 << "\nв вершину "
		 << finish
		 << " равна "
		 << DFS(G, start, finish)
		 << endl;

	return 0;
}

int DFS(vector<vector<int>> &myG, int &s, int &u) {
	size_t n = myG.size();
	// Массив флагов посещаемости вершин
	vector<bool> used(n, false);
	// Подготовим стек
	stack<int> S;
	// Кладем исходную вершину в стек
	S.push(s);
	used[s] = true;
	// Будем считать длину пути
	vector<int> D(n);
	// Если нужно, запоминаем путь
	// vector<int> P(n);
	// P[start] = -1;
	// см. программу 26.3
	// Пока стек не пуст
	while (!S.empty()) {
		//Посещаем вершину
		size_t v = S.top();
	    S.pop();
	    // Идем в глубину графа
	    auto first = myG[v].begin();
	    auto last  = myG[v].end();
		// Осматриваем смежные вершины
	    while (first != last) {
	    	// Если какие-то ещё не посещались
	    	if (!used[*first]) {
	    		// Отправляем их в стек
	    		S.push(*first);
	    		// и фиксируем их посещение
	    		used[*first] = true;
	    		// если нужно запоминать путь, то
	    		// P[*first] = v;
	    		// Но мы будем считать длину
	    		D[*first] = D[v] + 1;
	    	}
	    	first++;
	    }
	}
	return D[u];
}

Заключение

Алгоритмы которые мы разобрали имеют более чем полувековую историю, но до сих пор находят широкое применение в информационных технологиях. Поэтому составлять, понимать и использовать эти алгоритмы должен каждый начинающий программист. Основной сферой применения алгоритмов на графах является поиск путей (возможность прохождения, вершины и ребра на кратчайшем пути, наличие циклов, мостов и т.п.). С помощью этих методов решаются классические задачи олимпиадного программирования. Они лежат в основе (либо входят как подзадачи) решения большого количества других методов обхода графа. Например, алгоритмы BFS и DFS при соответствующей доработке можно использовать в следующих задачах:

  • Поиск компонент связности
  • Нахождение кратчайшего цикла
  • Нахождение кратчайшего чётного пути
  • Поиск наименьшего общего предка
  • Поиск мостов

и мн. др. Разумеется, приведенными методами не исчерпывается все разнообразие методов работы с графами [3]. Разбор и усвоение некоторых важных алгоритмов вполне по силам учащимся старших классов. И дело здесь не только в подготовке к олимпиадам. Разбирая сложные задачи ученик учится программировать, оттачивает важный навык - составление эффективных алгоритмов.
При составлении программ этого урока использовались описания и реализации алгоритмов (язык программирования C++) на замечательном сайте MAXimal с которым мы рекомендуем вам обязательно познакомиться. Здесь представлено 145 алгоритмов, среди которых очень много алгоритмов на графах. Все материалы этого сайта распространяются под свободной лицензией. Также есть возможность скачать все алгоритмы одним файлом (pdf). Расширить ваш кругозор и познакомить с иными способами решения задач (в том числе и тех, которые мы рассмотрели на этом уроке) помогут источники перечисленные ниже.

Ссылки

  1. Глоссарий теории графов
  2. Граф (математика)
  3. Категория:Алгоритмы на графах
  4. Список смежности
  5. Способы представления графов (язык Rust)
  6. Реализация графов и деревьев на Python
  7. Алгоритмы на графах — Часть 1: Поиск в глубину и проблема взаимоблокировок
  8. Структуры данных и алгоритмы. Теория. Графы и их основные сферы применения в информатике
  9. Базовые алгоритмы нахождения кратчайших путей во взвешенных графах
  10. Лекция 45: Алгоритмы на графах. Алгоритмы обхода графа
  11. Роберт Седжвик. Алгоритмы на C++. Фундаментальные алгоритмы и структуры данных. — М.: «Вильямс», 2011. (ООП подход)
  12. Нахождение кратчайших путей от заданной вершины до всех остальных вершин алгоритмом Дейкстры
  13. Окулов С. М. Программирование в алгоритмах. М: Бином. Лаборатория знаний, 2013 (Используется матрица смежности и список ребер, паскаль)
  14. Поиск в ширину
  15. Графы для самых маленьких: DFS
  16. Скиена С. Алгоритмы. Руководство по разработке. СПб.: БХВ-Петербург, 2011
  17. Хайнеман Д., Поллис Г., Селков С. Алгоритмы. Справочник с примерами на C, C++, Java и Python. СпБ.: ООО "Альфа-книга", 2017.
  18. Лекция 7. Графы: способы их хранения и обхода (в ширину и в глубину). Проверка графа на двудольность, поиск циклов и топологическая сортировка графа
  19. От обхода в ширину к алгоритму Дейкстры
  20. Алгоритмы на графах (Pascal)
  21. Структуры данных и алгоритмы. Теория. Графы и их основные сферы применения в информатике
  22. Дасгупта С. и др. Алгоритмы / С. Дасгупта, Х. Пападимитриу, У. Вазирани. М.: МЦНМО, 2014.
Print Friendly, PDF & Email

Comments are closed.