Реферат: Поиск в ширину на графах

Современное состояние и тенденции развития вычислительной техники как основного инструмента информатики таковы, что наряду с увеличением функциональности вычислительная техника приобретает свойства, позволяющие работать на ней пользователю, не разбирающемуся в программировании. В этот период появился более качественный интерфейс программ. Появились структуры графических данных и более крупные, интегральные информационные единицы – объекты. Следствием стало бурное развитие объектно-ориентированных систем программирования, таких как Visual C++, Visual BASIC и других, в основе которых лежит обработка объектных структур данных. Также появились новые языки программирования ADA, OCCAM.([3]) И если раньше большой популярностью пользовались простые линейные алгоритмы то в настоящее время алгоритмы таких типов как деревья, графы, списки, очереди – получают все большее распространение.

Данный алгоритм может найти своё применение в программах для транспортных и коммуникационных сетей, таких как: железнодорожной транспортной сети, где вершины - станции, связи – дороги, таксомоторная сеть: вершины – места стоянки автомобилей, связи – пути подъезда; перемещение потока вещества по системе труб в определенный пункт назначения и т.д. На основе алгоритма поиска в ширину в графе можно построить программу вывода дерева наименьшей стоимости, что позволит рассчитывать кратчайшие пути к определенному месту назначения (вершине).

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

Список литературы:

Вирт Н. Алгоритмы и структуры данных.– М.: Мир, 1989.

Кнут Д. Искусство программирования для ЭВМ. – В 7 т. - М.: Мир, 1876.

Лойко В.И. Структуры и алгоритмы данных ЭВМ: Курс лекций для спец. 220400 – Краснодар: КубГТУ, 1998.

Марченко А.И., «Программирование в среде «Turbo Pascal 7.0»,

«Век+», Киев 1999 г.

Подпись_________________________Дата___________________________

Приложение А

Листинг модуля Newtimer

unit newtimer;

interface

procedure start(var x: longint); {определяет время начала работы}

procedure stop(var x: longint); {определяет время окончания работы}

procedure format(hour, min, sec, hund: word);

procedure Report(Msg:string; x:longint);

implementation

uses dos;

var

hour_start, min_start, sec_start, hund_start,

hour_stop, min_stop, sec_stop, hund_stop,

hour, min, sec, hund: word;

systimer : longint absolute $0040 : $006c;

procedure start;

begin

gettime(hour_start, min_start, sec_start, hund_start);

x:=systimer;