Study & Dev | Blog Archive | Структуры данных и алгоритмы. Теория. Графы и их основные сферы применения в информатике

Структуры данных и алгоритмы. Теория. Графы и их основные сферы применения в информатике

January 8, 2007

Графы и их основные сферы применения в информатике

Прежде всего, нам необходимо ознакомиться с используемой далее терминологией.

Теория графов - математический язык для формализованного определения понятий, связанных с анализом и синтезом структур систем и процессов.

Теория графов - теоретическая основа структурной информатики.

Граф (GRAPH) - вообще говоря, пара G=(V, E), где V -непустое множество вершинами, а E - множество пар ei=(vi1, vi2), которые задают ребра. Обычно V называют множеством вершин, а E - множеством ребер. Обычно граф изображают на плоскости в виде точек (вершин) и соединяющих их линий (ребер).

Вершина графа - элемент множества вершин графа.

Ребро графа - элемент множества ребер графа.

Дуга - ориентированное ребро.

Число вершин - мощность множества вершин р=|V|

Число ребер - мощность множества ребер q=|E|

Две вершины называются смежными , если существует соединяющее их ребро.

Ребра называются смежными, если они опираются на общую вершину.

Вершина графа v и некоторое его ребро e называются инцидентными, если e=(v,w) или e=(w,v), где w - некоторая вершина графа.

Петля - ребро инцидентное одной вершине (единственной). Может быть несколько петель.

Степень вершины - число инцидентных ей ребер.(Обозначается deg(v)).

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

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

Граф называют однородным, если степени всех его вершин одинаковы.

На заметку: Во всяком графе число вершин нечетной степени всегда четно.

Цепь в графе G={V,E} - последовательность вершин v0,v1 ,...vn -такая , что n>0 и vi,vj соединены ребром.(i=0..n-1;j=i+1) n - длина цепи. Если вершины входящие в цепь различны, то цепь - простая , иначе - составная.

Цикл - замкнутая цепь.

Обход графа - цикл, проходящий через все вершины графа по одному разу.

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

Корень (root) - обычно так называют специально выделенную по тем или иным причинам вершину дерева.

Подграф - часть графа G=(V, E) - граф G'=(V',E'), для которого V'
Обыкновенный граф (SIMPLE GRAPH) - граф, не содержащий мультиребер и петель.

Полный граф (FULL GRAPH) - это обыкновенный граф G=(V, E), в котором любая пара вершин смежна. Обозначается Kp, где р=|V|, при этом |E|=p(p-1)/2.

Мультиграф (MultiGraph) -граф, содержащий мультиребера или петли.

Пустой граф - граф G=(V,E), в котором |E|= 0

Тривиальный граф - граф G=(V,E), в котором |E|=0 и |V|=1

Ациклический граф (лес) - обыкновенный граф без циклов.

Дерево (tree) - связный ациклический граф.

Орграф - ориентированный граф - граф ребра, которого имеют некоторое направление.

Неориентированный граф - граф ребра, которого не имеют направления (двусторонние).

Основные алгоритмы на графах

Для рассмотренных далее алгоритмов предъявляется требование корректности, под которой понимается выполнение следующих требований:

алгоритм завершает работу за конечное время;
если решение существует, то алгоритм находит правильное решение.

Волновой алгоритм.

Данный алгоритм решает задачу поиска пути между выделенными вершинами графа S и T. Так как в общем случае существует множество путей между двумя вершинами графа, то необходим критерий оптимальности пути. В случае если граф не взвешенный, то в качестве подобного критерия будет выбрано количество промежуточных ребер, которое необходимо будет пройти по пути. Данный алгоритм представляет собой переборный алгоритм с оптимизированным поиском. Из исходной вершины S во все смежные вершины на каждом I шаге алгоритма выходит волна поиска. Данный процесс повторяется до тех пор, пока фронт волны не дойдет до искомой вершины T. Разумеется, что должны быть приняты меры недопущения возврата фронта волны на позиции, которые были посещены ранее, в противном случае поиск может никогда не завершиться (алгоритм зацикливается).

каждой вершине vi приписывается целое число T(vi) - волновая метка (начальное значение T(vi)=-1);
заводятся два списка OldFront и NewFront (старый и новый "фpонт волны"), а также пеpеменная T (текyщее вpемя);
OldFront:={s}; NewFront:={}; T(s):=0; T:=0;
для каждой из веpшин, входящих в OldFront, пpосматpиваются инцидентные (смежные) ей веpшины uj, и если T(uj) = -1, то T(uj):=T+1, NewFront:=NewFront + {uj};
если NewFront = {}, то ВЫХОД("нет решения");
если t NewFront (т.е. одна из веpшин uj совпадает t), то найден кpатчайший пyть между s и t с T(t)=T+1 промежуточными ребрами; ВЫХОД("решение найдено");
OldFront:=NewFront; NewFront:={}; T:=T+1; goto (4).

Замечание: на шаге (4) "соседними" вершинами для неориентированных графов считаются все смежные вершины, а для орграфов - вершины, в которые из данной вершины ведут дуги.

Данный алгоритм гарантированно находит путь или сообщает о невозможности его нахождения. Интерес также представляет способ восстановления истории пути к искомой вершине T. Раскрутка маршрута начинается от искомой вершины T. Для нее находится та вершина, из которой мы пришли в T. Очевидно, что это должна быть та смежная вершина “x” для которой обязательно выполняется условие T(x) должно быть равно T(t) – 1. т.е именно эту вершину мы посетили в предыдущий момент времени. Далее в качестве целевой вершины полагается t=x, и алгоритм повторяется до нахождения s. Разумеется, что найденный путь не будет единственным. Возможны и другие пути, однако все они будут иметь одинаковую цену и в общем случае равноценны. Рекомендуется объединить поиск пути и сохранение истории. Так на шаге четыре в ранее описанном алгоритме следует воспользоваться вспомогательным массивом history каждый элемент, которого будет равен номеру той вершины, из которой фронт волны дошел до текущей, т.е. history {uj} = x. В таком случае процесс восстановления будет проще.

Пример исходного кода алгоритма:

```
#include "string.h"
```
```
#include "stdio.h"
```
```
 
```
```
#include <algorithm>
```
```
#include <iostream>
```
```
#include <functional>
```
```
#include <fstream>
```
```
#include <vector>
```
```
using namespace std;
```
```
 
```
```
const N = 20;
```
```
 
```
```
void main (void){
```
```
	int arr [N][N];
```
```
	int n;
```
```
	int i , j;
```

	ifstream fin ("graph.in" , ios_base::in);

```
	fin >> n;
```
```
	for (i = 0; i < n; i++)
```
```
		for (j = 0; j < n; j++)
```
```
			fin >> arr [i][j];
```
```
 
```
```
	int start , end;
```
```
	fin >> start >> end;
```
```
	int costs [N];
```
```
	for (i = 0; i < n ; i++)
```
```
		costs [i] = -1;
```
```
	costs [start] = 0;
```
```
 
```
```
	vector <int> history;
```
```
	history.push_back (start);
```
```
 
```
```
	while (! history.empty () ){
```
```
		int cur = *history.begin ();
```
```
		history.erase(history.begin ());
```
```
		if (cur == end){
```
```
			printf ("\n--- found ---\n");
```
```
			printf ("--%d" , cur);
```
```
			while (cur != start){
```
```
				for (i = 0; i < n ; i++)
```

					if (arr [i][cur] > 0 && arr[i][cur]+costs [i] == costs [cur]){

```
						cur = i;
```
```
						printf ("--%d" , i);
```
```
						break;
```
```
					}
```
```
			}
```
```
			printf ("\n");
```
```
		}
```
```
		else{
```
```
			for (i = 0; i < n ; i++)
```

				if (arr [cur][i] > 0 && (costs [i] == -1 || costs [i] > costs [cur] + arr [cur][i])){

					costs [i] = costs [cur] + arr [cur][i];

					history.insert (history.begin () ,  i );

```
				}
```
```
		}
```
```
 
```
```
	}
```
```
}
```

Алгоритм Флойда

Данный алгоритм является естественным развитием ранее приведенного волнового алгоритма. Действительно в ходе его мы уже решаем задачу поиска пути между двумя вершинами, попутно мы собираем информацию о расстояниях и путях между иными вершинами графа. В алгоритме Флойда в непустом взвешенном графе G=(V, E) с произвольными весами ребер (дуг) требуется найти длины кратчайших путей между всеми парами вершин графа, если в графе нет циклов (контуров) отрицательной суммарной длины, либо обнаружить наличие таких контуров.

Особо следует отметить чувствительность данного алгоритма к наличию в графе циклов с отрицательным весом, т.к. алгоритм ставит своей целью поиск наиболее выгодного маршрута, то при обнаружении отрицательного цикла он зациклится, и будет бесконечно перемещаться по нему снижая стоимость пути. В качестве простейшего приема противодействия можно порекомендовать найти самую большую по модулю отрицательную стоимость пути в графе “Z” и добавить ее ко всем вершинам, таким образом, отрицательные пути исчезнут, а рассчитать истинную стоимость пути можно, отняв от ее значения Z*n, где n – количество пройденных ребер.

Алгоритм Флойда может быть представлен следующими шагами:

1) Предварительная подготовка: построим матрицу D⁰ размерности |V| x |V|, элементы которой определяются по правилу:

 1. d<sub>ii</sub><sup>0</sup>= 0;
 2. d<sub>ii</sub><sup>0</sup>= стоимость(v<sub>i</sub>, v<sub>j</sub>), где i<>j, если в графе существует ребро (дуга) (v<sub>i</sub>, v<sub>j</sub>);
 3.  d<sub>ii</sub><sup>0</sup>= бесконечность , где i<>j, если нет ребра (дуги) (v<sub>i</sub>, v<sub>j</sub>).

2) Основная часть алгоритма:

Положим значение m=0.

Далее построим матрицы с D¹ по D^k, вычисляя элементы очередной “m+1” матрицы по руководствуясь тем, что для того чтобы уменьшить стоимость пути из V_A в V_B, т.е. элемент D_ab, где A – узел из которого мы идем, а B – узел куда мы идем, нам необходимо найти некоторую третью промежуточную вершину Z через которую стоит пройти так чтобы стоимость D_az + D_zb < D_ab.

Если же D_az + D_zb < 0 для какого-то Z, то в графе существует цикл (контур) отрицательной длины, проходящий через вершину V_z а, следовательно, программу следует прервать. В противном случае следует увеличить m: m=m+1. Данный набор шагов должен повторяться до тех пор, пока пока на очекредной итерации алгоритма мы не сможем улучишить ни одного пути. В этом случае мы завершили поиск всех наилучших путей и элементы последней построенной матрицы D_k равны длинам кратчайших путей между соответствующими вершинами.

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

```
#include "string.h"
```
```
#include "stdio.h"
```
```
 
```
```
#include <algorithm>
```
```
#include <iostream>
```
```
#include <functional>
```
```
#include <fstream>
```
```
#include <vector>
```
```
using namespace std;
```
```
 
```
```
const N = 20;
```
```
 
```
```
void main (void){
```
```
	int arr [N][N];
```
```
	int n;
```
```
	int i , j;
```

	ifstream fin ("graph.in" , ios_base::in);

```
	fin >> n;
```
```
	for (i = 0; i < n; i++)
```
```
		for (j = 0; j < n; j++){
```
```
			fin >> arr [i][j];
```
```
					}
```
```
 
```
```
 
```
```
	/*
```

	 Договор: “-1”  - означает что пути нет

```
	*/
```
```
	int M_Next  [N] [N];
```
```
 
```
```
	bool mustScan;
```
```
	do{ 
```
```
		mustScan = false;
```

		memcpy (M_Next , arr , sizeof (int) * N * N);

```
 
```
```
		for (int i=0; i < n; i++)
```
```
			for (int j=0; j < n; j++){
```
```
				if (i == j) continue;
```
```
 
```
```
				for (int k = 0; k < n; k++){
```

					if ( k== i ||  k==j || (arr [i][k] == -1) ||  (arr [k][j] == -1)) continue;

```
 
```

					int new_price = arr [i][k] + arr [k][j];

```
					if (new_price < 0){
```

						 perror ("error graph has negative iterations");

```
						 exit (0);
```
```
					}
```
```
					if (new_price < arr [i][j] ){
```
```
						M_Next [i][j] = new_price;
```
```
						mustScan = true;
```
```
					}
```
```
				}//for <K>
```
```
			}
```

		memcpy (arr , M_Next , sizeof (int) * N * N);

```
 
```
```
	}while (mustScan);
```
```
 
```
```
 
```
```
	printf ("--- After ----\n");
```
```
	for (i = 0; i < n; i++){
```
```
		for (j=0; j < n; j++)
```
```
			printf ("%4d"  , arr [i][j]);
```
```
		printf ("\n");
```
```
	}
```
```
}
```

Алгоритм Йена

Данный алгоритм позволяет находить k-кратчайшие пути без циклов последовательно, и предполагает, что мы располагаем достаточно эффективным алгоритмом поиска одного кратчайшего пути в графе.

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

Данный процесс должен повторяться итеративно. Следует также отметить, что рост количества кандидатов при каждом шаге алгоритма не велик и составляет порядка N, где N – количество ребер, которые образуют очередной наикротчайший путь.

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

Двунаправленный поиск в ширину.

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

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

Е. Дийкстра разработал классический алгоритм для прохода по графам, грани которых имеют различный вес. На каждом шаге, он ищет необработанные узлы близкие к стартовому, затем просматривает соседей найденного узла, и устанавливает или обновляет их соответствующие расстояния от старта. Этот алгоритм имеет два преимущества по сравнению с поиском в ширину: он принимает во внимание стоимость или длину пути и обновляет узлы, если к ним найден лучший путь. Для хранения промежуточных узлов используют приоритетную очередь, где извлеченный узел имеет лучшее значение - здесь, это наименьшая стоимость пути от старта. Однако, будучи построенным, на основе поиска в ширину данный алгоритм имеет недостаток, т.к. игнорирует направление к цели.

Поиск в глубину

Этот поиск противоположен поиску в ширину. Вместо посещения вначале всех соседей, а потом их наследников, он сначала посещает всех наследников, а только затем переключается на соседей. Для уверенности в том, что поиск закончится, необходимо предусмотреть остановку на определенной глубине. Можно использовать тот же самый код, что и в поиске в ширину, если добавить параметр для отслеживания глубины каждого узла и заменить используемую дисциплину хранения промежуточных узлов с FIFO на LIFO (т.е. использовать стек). Как вариант можно сделать поиск рекурсивной подпрограммой, Однако следует понимать, что в данном случае мы понесем дополнительные вычислительные затраты на работу со стеком, для передачи параметров вызова функции, также будут велики затраты и процессорного времени. Рекурсию не рекомендуется применять в случае если граф достаточно велик. Для реализации необходимо, чтобы каждая вершина маркировалась как "посещенная" при продвижении в глубь и эта пометка снималась на обратном ходу, чтобы избежать генерации путей, которые посещают дважды одну и ту же ячейку. Для геометрического поиска пути можно сделать два дополнения. Первое будет заключаться в добавлении метки на каждую ячейку (вершину) с длиной найденного к ней кратчайшего пути; алгоритм больше не посетит эту ячейку пока не будет иметь к ней путь с меньшей стоимостью. Другое заключается в выборе вначале соседей, которые ближе к цели. С этими двумя дополнениями, можно заметить, что поиск в глубину быстро найдет путь. Могут обрабатываться даже взвешенные пути, если сделать остановку по общей накопленной стоимости вместо общего расстояния.

```
#include "string.h"
```
```
#include "stdio.h"
```
```
 
```
```
#include <algorithm>
```
```
#include <iostream>
```
```
#include <functional>
```
```
#include <fstream>
```
```
#include <stack>
```
```
using namespace std;
```
```
 
```
```
const N = 20;
```
```
 
```
```
void main (void){
```
```
	int arr [N][N];
```
```
	int n;
```
```
	int i , j;
```

	ifstream fin ("graph.in" , ios_base::in);

```
	fin >> n;
```
```
	for (i = 0; i < n; i++)
```
```
		for (j = 0; j < n; j++)
```
```
			fin >> arr [i][j];
```
```
 
```
```
	int start , end;
```
```
	fin >> start >> end;
```
```
	int costs [N];
```
```
	for (i = 0; i < n ; i++)
```
```
		costs [i] = -1;
```
```
	costs [start] = 0;
```
```
 
```
```
	stack <int> history;
```
```
	history.push (start);
```
```
 
```
```
	int cur = history.top ();
```
```
 
```

	while (! history.empty () && cur != end){

```
		cur = history.top ();
```
```
		history.pop ();
```
```
		if (cur == end){
```

			printf ("path was found price=%d:\n" , costs[end]);

```
			printf ("--%d--"  , cur);
```
```
			while (cur != start){
```
```
				for (i  = 0; i < n; i++)
```

					if (arr [i][cur] > 0 && arr [i][cur] + costs [i] == costs [cur]){

```
						cur = i;
```
```
						printf ("%d--"  , i);
```
```
						break;
```
```
					}
```
```
			}
```
```
			printf ("\n");
```
```
		}
```
```
		else{
```
```
			for (i = 0; i < n; i++)
```
```
				if (arr [cur][i] > 0 )
```

					if (costs[i] == -1 || costs[i] > costs [cur] + arr [cur][i]){

```
						history.push (i);
```

						costs [i] = costs [cur] + arr [cur][i];

```
					}
```
```
		}
```
```
	}
```
```
 
```
```
 
```
```
}
```

Задачи к разделу графы, операции на графах

1) Граф, заданный матрицей связности необходимо проверить на связность. В случае несвязности необходимо вывести подмножество вершин каждого из связных подграфов.

2) Заданный орграф необходимо проверить на наличие циклов. При их наличии вывести каждый цикл в виде последовательности номеров вершин образующих цикл.

3) В орграфе найти все стоки, т.е. вершины в которые входят другие дуги, а также необходимо найти истоки, т.е. вершины из которых выходят другие дуги.

4) На площади своими вершинами заданы набор точек. Необходимо построить такой связной граф, длина ребер которого будет наименьшей.

5) На площади задано N красных и N синих точек, необходимо построить N отрезков которые должны соединять разноцветные точки и при этом их суммарная длина должна быть наименьшей.

6) В заданном орграфе необходимо перенумеровать вершины так, чтобы всякая дуга вела от вершины с меньшим номером к вершине с большим номером или доказать что это не возможно.

7) Найти все вершины графа, к которым существует путь заданной длины (не обязательно кратчайший) от его первой вершины.

8) Боб любит иностранные языки и хочет спланировать расписание занятий на несколько лет вперед. Его интересуют следующие девять учебных курсов: LA15, LA16, LA22, LA31, LA32, LA126, LA127, LA141, LA169. Заданы также предварительные условия для прохождения курсов:

LA15 (нет);
LA16 : LA15;
LA22: (нет);
LA31: LA15;
LA32: LA16, LA31;
LA126: LA22, LA32;
LA127: LA16;
LA141: LA22, LA16;
LA169: LA32.

Необходимо определить такую последовательность курсов, которая позволяет Бобу выполнить данные условия.

9) Университет Тамариндо совместно с несколькими другими университетами выполняет мультимедийный проект. Все университеты связаны единой телекоммуникационной сетью, образующей граф. Университеты решили установить на одной из площадок информационный сервер. Также уже заранее построены коммуникационные лини. Длины линий между каждым из университетов заданы в виде матрицы. Вам необходимо создать приложение, которое должно будет находить наилучшее месторасположение информационного центра. В качестве критерия выбирается наибольшее расстояние от центра до любого из университетов.

10) Сеть космических станций NASA связана телекоммуникационной сети, каждая из станций имеет выделенный канал связи с каждой из других станций напрямую. В связи с нехваткой средств, планируется расформировать некоторое количество линий связи, планируется оставить не более чем N. Вам необходимо решить какие именно линии необходимо расформировать, чтобы при этом не оказалось, что некоторая станция не имеет связи с другими станциями.

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

12) В условиях предыдущей задачи необходимо найти наиболее многочисленный семейный клан и вывести всех его членов на экран. Также в этом семейном клане найти его главу – человека имеющего наибольшее количество детей.

Categories: Структуры данных и алгоритмы

Study & DevО программировании и не только

Структуры данных и алгоритмы. Теория. Графы и их основные сферы применения в информатике

Основные алгоритмы на графах

Волновой алгоритм.

Алгоритм Флойда

Алгоритм Йена

Двунаправленный поиск в ширину.

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

Поиск в глубину

Задачи к разделу графы, операции на графах

Поиск

Недавнее

Архив

Разделы