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

Question

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

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

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

Несколько замечаний о моей реализации Graph:

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

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

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

Answer 1

Список всех пользователей сети графа с указанным расстоянием X

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

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

Перечислите всех пользователей в сети графа с указанием расстояния X и типа связи

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

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

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

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

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

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

Вот реализации C: Рой-Флойд и Дейкстра_1, Дейкстра_2. Вы можете найти много на Google с "<algorithm name> c implementation",

Редактировать: Рой-Флойд исключен для 18 000 узлов, как и матрица смежности. Это займет слишком много времени, чтобы построить и слишком много памяти. Лучше всего либо использовать алгоритм Дейкстры для каждого запроса, но предпочтительно реализовать Дейкстру, используя кучу - в приведенных мною ссылках используйте кучу, чтобы найти минимум. Если вы запускаете классическую Dijkstra для каждого запроса, это также может занять очень много времени.

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

Рассчитайте максимальное расстояние между двумя пользователями в сети графа

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

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

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

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

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

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

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

Answer 2

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

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

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

• Перечислите всех пользователей в сети графа с указанием расстояния X и типа связи

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

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

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

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

Самый длинный путь - это NP-полная проблема.

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

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

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

Answer 3

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

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