Построить граф с использованием динамических структур данных. Обходы графа

      Комментарии к записи Построить граф с использованием динамических структур данных. Обходы графа отключены

Главная Форумы Программирование Помощь с решением задач на Prolog Обработка графов (деревьев) на Prolog Построить граф с использованием динамических структур данных. Обходы графа

Помечено: ,

В этой теме 3 ответа, 2 участника, последнее обновление  Васильев Владимир Сергеевич 2 года/лет назад.

  • Автор
    Сообщения
  • #1935

    questioner
    Участник

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

  • #1936

    Хранить граф в виде списков можно по-разному, например, узлом списка может быть кортеж вида: (Source, [List_of_destination_nodes]), тогда граф
    Если есть граф:

    edge(a, b).
    edge(a, c).
    edge(b, d).

    Можно представить в виде списков следующих образом:
    [(a, [b, c]), (b, [d]), (c, [])].
    С обработкой такого графа проблем нет, страдает лишь эффективность. Вы можете по прежнему эффективно выполнять поиск узла в графе — теперь для этого нужно использовать предикат member:
    member((Src, Dest), Graph).
    Однако, удаление элемента из списка (узла из графа) — это медленная операция.

  • #1937

    questioner
    Участник

    Мне нужно решение на Visual Prolog, но в нем нужно объявлять типы данных. У меня не получается описать в разделе domains список пар.
    Как добавить узел в список?
    Как найти список вершин, в которые можно попасть из текущей (заданной) вершины? — я пыталась использовать findall, но не получилось.

  • #1938

    Описать тип данных узла графа можно следующим образом:

    domains
     list = integer*
     el = pair(integer, list)
     graph = el*

    • list — список целых чисел для хранения номеров узлов;
    • el — пара из номера текущего узла и списка смежных вершин;
    • graph — список пар (граф).

    Добавление узла в граф сейчас выполняется точно также, как добавление узла в список:

    Graph = [pair(1, [1,2,3]), pair(2, [3,4,5])],
    GraphWithNode = [pair(3,[7,8])|Graph].

    Первый список (Graph) содержит 2 пары, а список GraphWithNode — уже три пары.

    Для каждой вершины в графе вы храните список смежных вершин, т.е. таких, в которые можно попасть из текущей. Найти такие вершины можно предикатом member. Пусть Graph — ваш граф, Source — текущая вершина, нужно получить DestinationList — список смежных вершин:
    member((Source, DestinationList), Graph).
    Правило найдет в графе вершину с номером Source и инициализирует переменную DestinationList списком, который там хранится.

Для ответа в этой теме необходимо авторизоваться.