Шаг 184.
Основы языка Haskell. Программное представление графов в языке Haskell: структуры смежности. Список рёбер (дуг)

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

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

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


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


    Пример (моделирования списка дуг, ребра, изолированной вершины). Каждая из пар
   [(x1,y1),(x2,y2),...,(xj,yj)]
описывает дугу, соединяющую вершины x1 и y1, x2 и y2,..., xj и yj.

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

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

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

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

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

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




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