Главная » Java, Структуры данных и алгоритмы » Графы

0

В греческой мифологии описывается лабиринт, в котором был заключен получеловек-полубык по имени Минотавр. Лабиринт был настолько сложен, что ни человек, ни чудовище не могли из него выбраться. Ни один человек до греческого героя Тесея, воспользовавшегося помощью царской дочери Ариадны, не смог воплотить один из алгоритмов, обсуждаемых в этой главе. Тесей привязал нить к двери лабиринта и разматывал ее при движении по извилистым коридорам в поисках монстра. Очевидно, что Тесей разбирался в вопросах проектирования, так как после того, как он нашел и убил чудовище, смог вернуться обратно, воспользовавшись направлением, отмеченным нитью, прямо в объятья влюбленной Ариадны.

Возможность определить объекты, например, переходы лабиринта, связанные друг с другом, может быть не всегда жизненно важна, но все же достаточно существенна. Данные о связях имеются, например, в географических картах, где объектами выступают дороги, или в маршрутных таблицах Интернета, в которых объектами являются компьютеры. Данные о связях также включены в родительско-дочерние отношения в бинарных деревьях, объектами которых являются узлы дерева. В принципе информация о взаимосвязях может присутствовать во всех видах отношений, существующих между парами объектов. Темой данной главы являются графы, используемые для представления алгоритмов обработки такого вида отношений. Здесь граф рассматривается как множество объектов совместно с перечнем попарных связей между ними. Кстати, понятие «граф» не стоит путать с чертежами и графиками, которые не рассматриваются в данной главе.

применяются во многих областях знаний, включая картографию (географические информационные системы), системы коммуникации (дороги и авиатрассы), элект^окоммуникации, вычислительные сети (подключение через Интернет). Поскольку применение графов имеет широкое распространение в различных областях человеческой деятельности, то для описания компонентов и свойств графов используется огромное количество терминов. К счастью, поскольку графы относятся к последним разработкам, большая часть терминологии является интуитивно понятной.

Эту главу начнем ознакомлением с такой терминологией и представлением АТД «граф», включая некоторые из элементарных свойств графов. После этого в разделе 12.2 рассмотрим основные структуры данных для представления графов. Как и в случаях с деревьями, проблема проходов так же важна и для графов, что обсуждается в разделе 12.3. Разные типы графов рассматриваются в разделе 12.4. Но, поскольку тема направленных отношений прямо не соотносится с обсуждаемым материалом, читатель может этот раздел пропустить. В разделах 12.5-12.7 обсуждаются веса графов, когда связи можно оценить или измерить. Поскольку взвешенные связи могут быть направленными, в этих разделах исследуются хорошо известные проблемы выбора наикратчайшего пути и минимального объема дерева для ненаправленных графов.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии