Структуры данных: деревья, сети, графы, таблицы

Данные, используемые в любой информационной модели, всегда опре­деленным образом упорядочены, структурированы. Иначе можно сказать так: данные, на которых базируется информационная модель, представ­ляют собой систему со всеми характерными признаками — элементным составом, структурой, назначением. Такие структурированные системы данных часто называют структурами данных. Исследуя некоторую реаль­ную систему (объект моделирования), системный аналитик строит ее тео­ретическую модель. При этом в первую очередь он должен описать структуру данных.

Рассмотрим несколько часто используе­мых видов описания структур данных: графы, иерархические структуры (деревья) и таблицы.

Графы. Информация о некотором реальном объекте может быть представлена по-разному. В разговорной речи мы используем словесное (вербальное) представление информации.

Вот, например, словесное описание некото­рой местности: «Наш район состоит из пяти поселков: Дедкино, Бабки­но, Репкино, Кошкино и Мышкино. Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино». По такому описанию доволь­но трудно представить себе эту местность, нелегко и запомнить описание. А представьте себе, что поселков не 5, а 25! Всё гораздо понят­нее становится из схемы на рис. 1 (на ней поселки обозначены первыми буквами своих названий).

Рисунок 1. Неориентированный граф (сеть)

Это не карта местности. Здесь не выдержаны направления по сторонам света, не соблюден масштаб. На этой схеме отражен лишь факт существо­вания пяти поселков и дорожной связи между ними. Такая схема называ­ется графом.

Граф отображает элементный состав системы и структуру связей.

Составными частями графа являются вершины и ребра. Здесь верши­ны изображены кружками, обозначающими элементы системы, а ребра изображены линиями, показывающими связи (отношения) между эле­ментами. Глядя на этот граф, легко понять структуру дорожной системы в данной местности.

Построенный граф позволяет, например, ответить на вопрос: через ка­кие поселки надо проехать, чтобы добраться из Репкино в Мышкино. Вид­но, что есть два возможных пути; обозначим их так:

1)Р —К —Б —М;

2)Р —К —Д —Б —М.

Очевидно, первый путь более выгодный, потому что он короче. Однако если по какой-то причине дорога между К и Б окажется непроезжей (нач­нутся ремонтные работы или дорогу занесет снегом), то единственным остается второй путь. Граф на рисунке 1 еще называют сетью.

Для сети характерна возможность множества различных путей перемещения по ребрам между некоторыми парами вершин.

Для сетей также характерно наличие замкнутых путей, которые назы­ваются циклами. На рис. 1 имеется цикл: К - Д - Б - К.

Граф, изображенный на рис. 1, является неориентированным гра­фом. На нем каждое ребро обозначает наличие дорожной связи между дву­мя пунктами. Но дорожная связь действует одинаково в обе стороны: если по дороге можно проехать от Б к М, то по ней же можно проехать и от М к Б. Такую связь еще называют симметричной.

А теперь рассмотрим другой пример графа — на рисунке 2.

Этот пример относится к медицине. Известно, что существуют четыре группы крови человека. Оказывается, что при переливании крови от одно­го человека к другому не все группы совместимы. Граф на рис. 2 показывает возможные варианты переливания крови.

Рисунок 2. Ориентированный граф

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

Связи между вершинами данного графа несимметричны и поэтому изображаются направленными линиями со стрелками. Такие линии при­нято называть дугами (в отличие от ребер неориентированных графов). Граф с такими свойствами называется ориентированным. Линия, выхо­дящая и входящая в одну и ту же вершину, называется петлей. На рис. 2 присутствуют четыре такие петли.