На этом шаге мы рассмотрим формирование списка ребер и определим функции, использующие эти списки.

Определение.: Списком рёбер (дуг) будем называть способ моделирования структур смежности на языке Haskell, при котором структуры смежности представляются в виде списка рёбер (дуг) и естественно реализуются как список, состоящий из пар смежных вершин.

При таком подходе следует специально позаботиться о вершинах, не соединённых с другими вершинами посредством рёбер.

Замечание (важное). Мы рекомендуем для изображения таких "одиноких" вершин добавлять к списку рёбер фиктивное ребро, соединяющее "одинокую" вершину с вершиной "FALSE".

Пример (моделирования списка дуг, ребра, изолированной вершины). Каждая из пар

   [(x₁,y₁),(x₂,y₂),...,(x_j,y_j)]

описывает дугу, соединяющую вершины x₁ и y₁, x₂ и y₂,..., x_j и y_j.

Ребро (x,y) моделируется двумя дугами (x,y) и (y,x).

Изолированная вершина x моделируется парой (x,"FALSE").

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

Приведём основные функции библиотеки для работы с графами, представленными в виде списка рёбер (дуг):

(addArc x y graph) - добавление дуги (x,y) в граф graph, заданный списком дуг;
(listNode graph) - построение списка, содержащего все вершины графа graph, заданного списком рёбер (дуг);
(neighb x graph) - построение списка вершин, смежных вершине x, в неориентированном графе graph, заданном списком рёбер;
(neighb-1 x graph) - построение списка вершин, смежных вершине x, в ориентированном графе graph, заданном списком дуг;
(deleteNode x graph) - удаление вершины x из графа graph, заданного списком рёбер;
(addList node lst graph) - добавление в граф graph дуг, соединяющих вершину Node с вершинами, находящимися в списке lst;
(srchNode lst nodelst graph) - поиск в графе graph, заданном списком рёбер, вершины, имеющей смежные вершины, содержащиеся в списке lst; nodelst - список всех вершин графа graph;
(delArc x y graph) - удаление дуги (x,y) из ориентированного графа graph, заданного списком дуг;
(istoks graph) - восстановление списка вершин-"источников" по графу graph;
(stoks graph) - восстановление списка вершин-"стоков" по графу graph.

На следующем шаге мы рассмотрим пример использования перечисленных функций.

Предыдущий шаг Содержание Следующий шаг