Курсовая работа: Алгоритмы на графах. Кратчайшие расстояния на графах

read(N,FC);

for i:=1 to N do

begin

read(f,kG[f]);

for j:=1 to kG[f] do read(G[f,j]);

end;

for i:=1 to N do color[i]:=WHITE;

DFS1(FC);

MaxS:=s; DFS2(FC);

kv:=0; DFS3(FC);

kr:=0; for i:=1 to kv do DFS4(v[i]);

writeln(MaxS);

for i:=1 to kr do writeln(r[i]);

close(input); close(output);

end.

Заключение

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

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

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

Литература

1. Абдеев Р.Ф. Философия информационной цивилизации. - М.: Владос, 1994.

2. Адамар Ж. Исследование психологии процесса изобретения в области математики. - М.: Сов. радио, 1970.

3. Болтянский В.Г. Информатика и преподавание математики// Математика в школе. 1989. № 4.-С.86-90

4. Вейценбаум Дж. Возможности вычислительных машин и человеческий разум. - М.: Радио и связь, 1982.

5. Вирт Н. Алгоритмы+Структуры данных=Программа. - М.:Мир, 1989

6. Вирт Н. Систематическое программирование: Введение. - М.: Мир, 1977.

7. Громов Г.Р. Очерки информационной технологии. - М.: ИнфоАрт, 1993.

8. Дейкстра Э. Дисциплина программирования. - М.: Мир, 1978.

9. Ильенков Э. В. Философия и культура. - М.: Полит. лит., 1991.

10. Йодан Э. Структурное проектирование и конструирование программ. - М.: Мир, 1979.