Распознавание и представление графов. Часть 1
Перевод статьи gladius: “Section 1: Recognizing and Representing a Graph”
Введение
Графы представляют собой фундаментальные структуры данных в программировании. Как правило, имеется множество различных способов решений задач с графами. Например, это могут быть задачи, связаны с поиском пути на двумерном графе (между начальной и конечной точками), или поиском максимального количества жидкости, которое может пройти через трубопровод, если известна максимальная пропускная способность каждого участка трубопровода (эта задача также известна в качестве задачи о максимальном потоке или задачи о минимизации отходов при раскрое, которые мы будет рассматривать позднее). Понимание структур данных при решении задач на графах имеет решающее значение. Подчас решение, казалось бы неразрешимой задачи, при использовании подходящей структуры данных может представлять несколькими строками кода, и к счастью стандартные библиотеки языков программирования могут нам оказать здесь неоценимую помощь!
Идентификация задач на графах
Первым шагом к решению задач, связанных с графами, является идентификация типа задач, решаемых с помощью графов. При знакомстве с проблемой на практике бывает сразу трудно усмотреть такую связь. Поэтому при анализе важно обратить внимание возможные упоминания в условиях каких-либо сетей. Если явные упоминания отсутствуют, следует поискать косвенные ссылки, например, постановка проблема может требовать найти путь или маршрут. В этом случае метод решения задачи непосредственно связан с применением графов. В качестве ориентиров также следует обратить внимание на некоторые ключевые слова, используемые в постановке задач, решаемых с помощью графов — это такие термины как вершины, узлы, ребра, соединения, соединения, пути, циклы, направление. Вот простой пример постановки проблемы:
«Боб потерялся в своем районе и ему нужно вернуться обратно домой. Район Боба — это равномерная двумерная сетка, которая начинается в точке (0, 0) и далее описывается следующими параметрами: ширина клетки сетки равна 1, высота — 1. На сетке располагаются пустые пространства, через которые Боб может пройти без труда, и места, занятые домами, через которые Боб не может пройти. Боб может двигаться только по горизонтали или по вертикали на один квадрат за один шаг (момент времени).
Обозначим начальное положение Боба точкой «B», а расположение дома точкой «H». Пустые квадраты на сетке обозначим точками «.», а дома — крестиком «X». Необходимо найти минимальное количество шагов, которые потребуются Бобу для возвращения домой, а если Боб не сможет вернуться домой, необходимо возвратить значение «-1».
Вот пример окрестности шириной 7 и высотой 5 клеток сети:
...X..B
.X.X.XX
.H.....
...X...
.....X."Как только вы поняли, что данная задача относится к теории графов, приступайте к созданию представления графа в памяти компьютера.
Представление графа и ключевые понятия
В реальности графы могут представляться множеством различных систем, начиная с двумерной сетки (как в вышеприведенной задаче), заканчивая картой интернета, которая показывает, сколько времени требуется для переноса данных с компьютера А на компьютер B. Сначала нужно определить элементы, из которых состоит граф. В действительности таких элементов всего два — это узлы и ребра. Узел (или вершина) — это фиксированная точка на графе. Ребро (или соединение) — это связующее звено между двумя вершинами, которое может быть направленным (ориентированное ребро) или не направленным (неориентированное ребро), также ребру может быть приписана численная характеристика (например, стоимость). Неориентированное ребро означает отсутствие ограничений на направление, к котором можно проходить через ребро между узлами. Так, например, по неориентированному ребру между узлами A и B можно проходить как в направлении от A к B так и от B к A. Ориентированное ребро допускает перемещение только в одном направлении, поэтому, например, для направленного ребра от A к B можно передвигаться только из вершины A в вершину B, но не наоборот, от B в A. Наиболее простым представлением о ребрах и вершинах является следующее: ребро — это функция двух вершин, возвращающая стоимость. Рассмотрим пример такого подхода.
Если пользоваться математической нотацией для обозначения графа, то можно определить его как G = {V, E} — множество вершин V и набор ребер E (для ребер требование составлять множество является не обязательным). Тогда ребром будем называть пару (u, v), где u и v — элементы V. Существует несколько технических терминов, которые было бы полезно обсудить и в данный момент:
- Порядок — количество вершин в графе
- Размер — количество ребер в графе
Односвязные списки
Примером одного из простейших типов графов является односвязный список! Рассмотрим преимущества графовой структуры данных, с помощью которой можно описывать как очень сложные отношения, так и весьма простые, например, список.
У односвязного списка есть один «корневой» узел, и каждый узел ссылается на следующий узел. Таким образом, структура выглядит так:
structure node
[node] link;
[data]
endnode head;
Можно привести следующий простой пример:
node B, C;
head.next = B;
B.next = C;
C.next = null;Графически это можно было бы представить как корень->B->C->null. Здесь null представляет собой конец списка.
Вернемся к концепции функции стоимости. Наша функция стоимости может выглядеть следующим образом:
cost(X, Y) := if (X.link = Y) return 1;
else if (X = Y) return 0;
else "Not possible"Такая функция стоимости показывает, что мы можем перейти непосредственно от одного узла к другому через ребро. Вам нужно привыкнуть к использованию функции затрат, поскольку каждый раз, когда вы будете сталкиваться с графами, в той или иной форме вы будете иметь дело с функцией затрат! В данный момент у вас может возникнуть вопрос: «Подождите секундочку, для пути от A до C функция стоимости может не существовать, хотя фактически, я могу добраться до C от A, пройдя через B!» Это действительно так, но дело в том, что функция стоимости просто хранит непосредственно стоимость кратчайшего пути при движении от одного узла к другому. Позже мы рассмотрим, как найти расстояния в на графах общего типа.
Теперь, когда мы рассмотрели пример одного из самых простых типов графов, перейдем к более сложным примерам.
Деревья
Далее для подробного рассмотрения деревьев мы отводим отдельный раздел. Сейчас пока кратко рассмотрим их в качестве примера. Выше мы были несколько ограничены в представляемом типе данных. Например, если вы захотите создать генеалогическое древо (иерархическую организацию родственных связей), вы не сможете сохранить более одного родителя для каждого ребенка. Поэтому, очевидно, нужен новый тип структуры данных. Новая структура узла будет выглядеть примерно так:
structure node
[node] mother, father;
[string] name
endnode originalChild;
С функцией стоимости:
cost(X, Y) := if ((X.mother = Y) or (X.father = Y)) return 1;
else if (X = Y) return 0;
else "Not possible"Здесь видно, что у каждого узла имеется и мать и отец. Узел позволяет рекурсивно определить структуру в целом — у каждой матери есть свои мать и отец и у каждого отца, также есть свои мать и отец, и так далее. Здесь может возникнуть такая проблема как образование циклов, если вы захотите описать эту структуру данных на компьютере. Но дерево не может содержать петель. Это очевидно, если задуматься над следующим вопросом: является ли отец одновременно и сыном своего ребенка? У меня уже начала болеть голова :). Поэтому вы должны быть очень осторожны при построении дерева — каждый раз вам следует убедиться, что это действительно древовидная структура, а не граф более общего вида. Более формальное определение дерева таково: дерево — это связный граф без циклов. Это означает, что каждый узел графа соединяется, по меньшей мере, с одним узлом графа.
Еще одно замечание: можно легко представить ситуацию, когда дерево требует более двух ребер между узлами, например, в случае описания организационной иерархии — у вас может иметься менеджер, который управляет несколькими подчиненными, тогда как генеральный директор также управляет несколькими менеджерами. Наш пример ‑ это пример графа, известного как двоичное дерево, поскольку имеется только две связи с узлами. Далее перейдем к построению структуры данных, которая может представлять граф общего вида!
Графы
Дерево допускает для узла только наличие потомков и в дереве отсутствуют циклы, для графа общего вида возможно представление более богатого выбора ситуаций. Весьма распространенным примером является маршрут перелета между городами. Если рассматривается рейс между городом А и городом В, это означает что между этими городами можно провести ребро. Стоимостью ребра может являться время, которое потребуется для выполнения перелета, или, например, расход топлива.
Способ представления для этой задачи заключается в описании ребер между узлами (или вершинами) с другими узлами, а также с помощью приписанных узлам параметров. Таким образом, для примера перелета мы могли бы описать аэропорт как узел, и тогда для каждого вылета из города у нас имеется соседний узел, являющийся пунктом назначения.
structure node
[list of nodes] neighbors
[data]
endcost(X, Y) := if (X.neighbors contains Y) return X.neighbors[Y];
else "Not possible"list nodes;
Это пример общего способа представления графа. Такое описание допускает наличие нескольких ребер, исходящих из одного узла к другому, что позволяет очень компактно описать графа. Однако недостатком здесь является большая трудность работы с таким представлением, по сравнению, например, с методом массива, обсуждаемым далее.
Представление массива
Метод представления графа в виде списка узлов очень удобен. Но обычно topcoder накладывает на нас определенные ограничения, чтобы облегчить жизнь. Мы рассматриваем небольшие графы, содержащие малое количество узлов и ребер. В такой ситуации мы можем воспользоваться другим типом структуры данных, с которым легче работать.
Идея состоит в том, чтобы описать двумерный массив целых чисел, в котором элемент строки i, и столбце j представляет собой стоимость ребра между узлами i и j. Если ребро между i и j отсутствует, используем некоторое контрольное значение (обычно это или очень большое или очень маленькое значение, например -1 или максимальное целочисленное значение). Еще одним удобным свойством этого типы структуры данных является легкость представления направленных и ненаправленных ребер.
Для примера, ниже представлена следующая матрица связей:
A B C
A 0 1 5
B -1 0 1
C -1 -1 0Это означает, что вес связи узла А с самим сбой (цикл) равен нулю, единица — это вес связи с узлом B, а 5 ‑ вес связи с узлом C. Узел B, с другой стороны, не имеет связи с узлом A, а вес его связи с узлом C равен 1. Узел C ни к одному из узлов не подключен. Если вы нарисуете этот граф, он будет выглядеть так:
Такое представление удобно для графов, которые не содержат нескольких ребер между каждым из узлов, что позволяет значительно упростить работу.
