Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, сокращённый курс, по 2 часа в неделю)



Уроки 47 - 49
Графы. Основные понятия
(§44. Графы)




Содержание урока

Что такое граф?

«Жадные» алгоритмы. Задача 1

«Жадные» алгоритмы. Задача 2

Кратчайшие маршруты

Некоторые задачи

Вопросы и задания

Задачи


«Жадные» алгоритмы. Задача 2


Задача 2. В стране Лимонии есть N городов, которые нужно соединить линиями связи. Между какими городами нужно проложить линии связи, чтобы все города были связаны в одну систему и общая длина линий связи была наименьшей?

В теории графов эта задача называется задачей построения минимального остовного дерева (т. е. дерева, связывающего все вершины). Остовное дерево для связного графа с N вершинами имеет N - 1 ребро.

Рассмотрим «жадный» алгоритм решения этой задачи, предложенный Крускалом:

1) начальное дерево — пустое;
2) на каждом шаге к дереву добавляется ребро минимального веса, которое ещё не входит в дерево и не приводит к появлению цикла в дереве.

На рисунке 6.27 показано минимальное остовное дерево для одного из рассмотренных выше графов (сплошные жирные линии).

Рис. 6.27

Рис. 6.27

Здесь возможна такая последовательность добавления рёбер: СЕ, DF, АВ, EF, АС. Обратите внимание, что после добавления ребра EF следующее «свободное» ребро минимального веса — это DE (длина 3), но оно образует цикл с рёбрами DF и EF, поэтому не было включено в дерево.

При программировании этого алгоритма сразу возникает вопрос: как определить, что ребро ещё не включено в дерево и не образует цикла в нём? Существует очень красивое решение этой проблемы, основанное на «раскраске» вершин.

Сначала все вершины «раскрашиваются» в разные цвета (т. е. им присваиваются разные числовые коды): 

for i:=l to N do col[i]:=i;

Здесь N — количество вершин, a col — целочисленный массив с индексами от 1 до N.

Затем в цикле N — 1 раз (именно столько рёбер нужно включить в дерево) выполняем следующие операции:

1) ищем ребро минимальной длины среди всех рёбер, концы которых окрашены в разные цвета;
2) найденное ребро (iMin,jMin) добавляется в список выбранных, и все вершины, имеющие цвет col[jMin], перекрашиваются в цвет col[iMin].

Приведём полностью основной цикл программы: 

for k:=1 to N-1 do begin
		{поиск ребра с минимальным весом} 
	min:=MaxInt; 
	for i:=1 to N do 
		for j:=1 to N do
			if (col[i]<>col[j]) and (W[i,j] < min) 
				then begin
					iMin:=i; jMin:=j; min:=W[i,j]; 
				end;
			{добавление ребра в список выбранных} 
		ostov[k,1]:=iMin; 
		ostov[k,2}:=jMin;
			{перекрашивание вершин} 
		for i:=1 to N do
			if col[i]=col[jMin] then 
			col[i]:=col[iMin];
end;

Здесь W — целочисленная матрица размера N x N (индексы строк и столбцов начинаются с 1); ostov — целочисленный массив из N-1 строк и двух столбцов для хранения выбранных рёбер (для каждого ребра хранятся номера двух вершин, которые оно соединяет).

После окончания цикла остаётся вывести результат — рёбра из массива ostov: 

for i:=1 to N-1 do
writeln('(', ostov[i,1],	ostov[i,2],	')');


Следующая страница Кратчайшие маршруты



Cкачать материалы урока






Наверх