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

Многие прикладные задачи легко сформулировать в терминах такой
структуры данных, как граф [1, 2, 3]. Для ряда подобных задач хорошо изу-
чены эффективные (полиномиальные) алгоритмы их решения. Алгоритмы
на графах полезны при решении ряда сложных и важных задач. Свойства
графов активно используются для решения задач на сетевых системах (неф-
тепроводах, газопроводах, электросетях и т.п.), в решении сложных задач
на многопроцессорных вычислительных системах. Граф алгоритма позво-
ляет получить представление о том, как распространяется и преобразуется
информация при его реализации [4], что особенно важно для оптимизации
параллельных вычислительных алгоритмов. Перспективным направлением
решения сложных задач теории графов являются имитационные методы,
основанные на природных механизмах принятия решений (клеточных авто-
матах, муравьиных алгоритмах, генетических алгоритмах и др.) [5].
Долгое время задачи теории графов решались вручную. В настоящее
время с появлением компьютеров компьютерное моделирования резко рас-
ширило сферу своего применения в различных областях знания, в том числе
в теории графов, появилась возможность написания специальных программ
на алгоритмических языках.
Любая компьютерная программа предназначена для обработки данных,
от способа организации которых зависят алгоритмы работы, поэтому вы-
бор структур данных должен предшествовать созданию алгоритмов. Лю-
бой язык программирования содержит стандартные способы организации
данных – основные и составные типы. Наиболее часто в программах ис-
пользуются массивы, структуры и их сочетания, например, массивы струк-
тур [6]-[11].
Общая стратегия поиска на графах разрабатывается и применяется к
фундаментальным задачам связности, в том числе к задаче отыскания крат-
чайшего пути, построения минимального остовного дерева, к задаче о по-
токах в сетях и задаче о паросочетаниях. Унифицированный подход к этим
алгоритмам показывает, что в их основе лежит одна и та же процедура, и...

Развитие вычислительной техники и программирования сопровождалось
эволюцией представлений о роли данных, взглядов на их организацию. В
большинстве случаев одним из доминирующих свойств компьютеров явля-
ется способность хранить огромные объемы информации, к которым мож-
но просто обратиться. Информация, подлежащая обработке, в некотором
смысле представляет абстракцию некоторого фрагмента реального мира.
Мы говорим о данных как об абстрактном представлении реальности, по-
скольку некоторые свойства и характеристики реальных объектов при этом
игнорируются как несущественные для данной задачи.
Суть всех алгоритмов состоит в том, что они описывают обработку дан-
ных, преобразование некоторых начальных данных в конечные. Какие-то
данные алгоритм (программа) может использовать как промежуточные.
Естественно, что представление и организация данных имеет при разработ-
ке алгоритма первостепенное значение. Вопрос о том, как должны быть ор-
ганизованы данные, необходимо решать до того, как начинается разработка
алгоритма (программы). Ведь прежде, чем выполнить какие-либо операции,
нужно иметь объекты, к которым они применяются, и четко представлять
себе структуру объектов, которые будут получены.
Представление данных определяется, исходя из средств и возможностей,
допускаемых компьютером и его программным обеспечением. Однако очень
важную роль играют и свойства самих данных, операции, которые должны
выполняться над ними. С развитием вычислительной техники и программи-
рования средства и возможности представления данных получили большое
развитие и теперь позволяют использовать как простейшие неструктури-
рованные данные, так и данные более сложных типов, которые обладают
некоторой организацией.
В данной работе приведены алгоритмы определения связности вершин
графа, основанные на классических алгоритмах обхода вершин, имеющих
универсальное применение. Представлена программная реализация на язы-
ке Pascal. Рассмотрено применение динамических типов...