Предложения наиболее простых алгоритмов для некоторых графовых операций

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

Операции, которые мне нужно будет выполнить, следующие:

  • перечислите всех пользователей в Графовой сети с заданным расстоянием X
  • Список всех пользователей в сетевой график дали расстояние X и тип отношения
  • вычислить кратчайший путь между 2 пользователями в Графовой сети при заданном типе связи
  • вычислите максимальное расстояние между 2 пользователями в Графовой сети
  • вычислить наиболее удаленных подключенных пользователей в Графовой сети

Несколько заметок о моей реализации графа:

  • граничный узел имеет 2 свойства, одно из которых имеет тип char, а другое int. Они представляют тип отношения и веса, соответственно.
  • Граф реализуется с помощью связанных списков, как для вершин, так и для ребер. Я имею в виду, что каждая вершина указывает на следующую, и каждая вершина также указывает на начало другого связанного списка, ребра для этой конкретной вершины.

Что я знаю о том, что мне нужно сделать:

  • я не знаю, является ли это самым простым, как я сказал выше, но для кратчайшего пути между 2 пользователями, я считаю, что алгоритм Дейкстры-это то, что люди, кажется, рекомендуют довольно часто, поэтому я думаю, я соглашусь с этим.
    • я искал и искал, и мне трудно реализовать этот алгоритм, кто-нибудь знает какой-нибудь учебник или что-то простое для понимания, чтобы я мог реализовать этот алгоритм сам? Если это возможно, с примерами исходного кода C, это очень поможет. Я вижу много примеров с математическими нотациями, но это еще больше сбивает меня с толку.
    • Как вы думаете, поможет ли мне "преобразовать" граф в матрицу смежности, чтобы представить вес связей и тип отношений? Было бы проще выполнить алгоритм на этом вместо связанных списков? Я мог бы легко реализовать функцию, чтобы сделать это преобразование, когда это необходимо. Я говорю это, потому что у меня было чувство, что это будет легче, прочитав пару страниц об этом предмете, но я могу ошибаться.
  • у меня нет никаких идей по поводу других 4-х операций, предложений?
3 8
algorithm dijkstra

3 ответа:

Перечислите всех пользователей в Графовой сети с заданным расстоянием X

Расстояние X от чего? от начального узла или расстояния X между собой? Можете ли вы привести пример? Это может быть или не быть так же просто, как выполнить поиск BF или запустить Dijkstra.

Предполагая, что вы начинаете с определенного узла и хотите перечислить все узлы, которые имеют расстояния X до начального узла, просто запуститеBFS из начального узла. Когда вы собираетесь вставить новый узел в очередь, проверьте, является ли расстояние от начального узла до узла, из которого вы хотите вставить новый узел, + вес ребра от узла, из которого вы хотите вставить новый узел, до нового узла X. Если он строго меньше, вставьте новый узел, а если он равен, просто выведите новый узел (и только вставьте его, если вы также можете иметь 0 в качестве веса ребра).

Перечислите всех пользователей в Графовой сети с заданным расстоянием X и типом связи

См. выше. Просто учитывайте это тип связи в BFS: если тип родительского узла отличается от типа узла, который вы пытаетесь вставить в очередь, не вставляйте его.

Вычислить кратчайший путь между 2 пользователями в Графовой сети при заданном типе связи

Алгоритм зависит от ряда факторов:

  • как часто вам нужно будет вычислять это?
  • сколько у вас узлов?

Поскольку вы хотите легкого, самые легкие-это Рой-Флойд и Дийкстры.

  • использование Roy-Floyd кубично по числу узлов, поэтому неэффективно. Используйте его только в том случае, если вы можете позволить себе запустить его один раз, а затем ответить на каждый запрос в O(1). Используйте это, если вы можете позволить себе сохранить матрицу смежности в памяти.
    • Дийкстра квадратичен по числу узлов, Если вы хотите сохранить его простым, но вам придется запускать его каждый раз, когда вы хотите вычислить расстояние между двумя узлами. Если вы хотите использовать Дийкстру, используйте смежность список.

Вот реализации C: Roy-Floyd и Dijkstra_1, Dijkstra_2 . Вы можете найти многое в google с помощью "<algorithm name> c implementation".

Edit: Roy-Floyd не может быть и речи для 18 000 узлов, как и матрица смежности. На это уйдет слишком много времени и слишком много памяти. Ваш лучший выбор-либо использовать алгоритм Дийкстры для каждого запроса, но предпочтительно реализовать Дийкстру с помощью кучи - в ссылках, которые я предоставил, используйте кучу, чтобы найдите минимум. Если вы запускаете классическую Дийкстру для каждого запроса, это также может занять очень много времени.

Другой вариант-использовать алгоритмBellman-Ford для каждого запроса, который даст вам O(Nodes*Edges) время выполнения для каждого запроса. Однако это большая переоценка, если вы не реализуете ее, как говорит Википедия. Вместо этого используйте очередь, аналогичную той, что используется в BFS. Всякий раз, когда узел обновляет свое расстояние от источника, вставьте этот узел обратно в очередь. Это будет очень быстро. на практике же будет работать и для отрицательных Весов. Я предлагаю вам использовать либо эту, либо Дийкстру с кучей, так как классическая Дийкстра может занять много времени на 18 000 узлов.

Вычислите максимальное расстояние между 2 пользователями в Графовой сети

Самый простой способ-использовать обратный путь: испробовать все возможности и сохранить самый длинный найденный путь. это NP-полное, поэтому полиномиальных решений не существует.

Это очень плохо, если у вас есть 18 000 узлы, я не знаю никакого алгоритма (простого или иного), который будет работать достаточно быстро для такого количества узлов. Рассмотрите возможность его аппроксимации с помощью жадных алгоритмов. Или, может быть, ваш график имеет определенные свойства, которые вы могли бы использовать в своих интересах. Например, является ли это DAG (направленный ациклический граф)?

Вычислить наиболее удаленных подключенных пользователей в Графовой сети

Означает, что вы хотите найти диаметр графа. Самый простой способ сделать это-найти расстояния между ними. каждые два узла (все пары кратчайших путей - либо выполнить Roy-Floyd, либо Dijkstra между каждым из двух узлов и выбрать два с максимальным расстоянием).

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

Как вы думаете, поможет ли мне "преобразовать" граф в матрицу смежности для представления веса связей и типа отношений? Было бы проще выполнить алгоритм на этом вместо связанных списков? Я мог бы легко реализовать функцию, чтобы сделать это преобразование, когда это необходимо. Я говорю это, потому что у меня было чувство, что это будет легче, прочитав пару страниц об этом предмете, но я могу ошибаться.

Нет, матрица смежности и Рой-Флойд-очень плохая идея, если только ваше приложение не нацелено на суперкомпьютеры.
8

Это предполагает, что O(E log V) является приемлемым временем выполнения, если вы делаете что-то онлайн, это может быть не так, и это потребует некоторого более мощного оборудования.

  • перечислите всех пользователей в Графовой сети с заданным расстоянием X

Алгоритм Джикстры хорош для этого, для одноразового использования. Вы можете сохранить результат для дальнейшего использования, с линейным сканированием через все вершины (или еще лучше, сортировка и двоичный поиск).

  • Список всех пользователей в Графовой сети учитывая расстояние X и тип отношения

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

  • вычислить кратчайший путь между 2 пользователями в Графовой сети с учетом типа связи

То же, что и выше, по существу, просто определите заранее, соответствуете ли вы двум пользователям. (В качестве альтернативы, вы можете "встретиться в середине", и закончить рано, если вы найдете кого-то на обоих самых коротких путь связующего дерева)

  • вычислить максимальное расстояние между 2 пользователями в Графовой сети

Самый длинный путь является NP-полной задачей.

  • вычислить наиболее удаленных подключенных пользователей в Графовой сети

Это диаметр графа, о котором вы можете прочитать в разделеMath World .

Что касается вопроса о списке смежности и матрице смежности, то он зависит от того, насколько плотно заполнен ваш граф. Кроме того, если вы если вы хотите кэшировать результаты, то матрица может быть подходящим способом.

5

Самый простой алгоритм вычисления кратчайшего пути между двумя узлами - этоFloyd-Warshall . Это просто тройная вложенность для циклов, вот и все.

Он вычисляет все-пары кратчайших путей в O(N^3), поэтому он может выполнить больше работы, чем необходимо, и займет некоторое время, если N огромен.

1