Предложения самых легких алгоритмов для некоторых операций Графика
Крайний срок для этого проекта приближается очень быстро, и у меня нет большого количества времени для контакта с тем, что это оставляют. Так, вместо того, чтобы искать лучшее (и вероятно более сложный/трудоемкий) алгоритмы, я ищу самые легкие алгоритмы для реализации нескольких операций на структуре Графика.
Операции, которые я должен буду сделать, следующие:
- Перечислите всех пользователей в сети графика, учитывая расстояние X
- Перечислите всех пользователей в сети графика, учитывая расстояние X и тип отношения
- Вычислите кратчайший путь между 2 пользователями в сети графика, учитывая тип отношения
- Вычислите максимальное расстояние между 2 пользователями в сети графика
- Вычислите большинство удаленных подключенных пользователей на сеть графика
Несколько примечаний о моей реализации Графика:
- Граничный узел имеет 2 свойства, каждый имеет тип
charи другойint. Они представляют тип отношения и веса, соответственно. - График реализован со связанными списками, и для вершин и для краев. Я имею в виду, каждая вершина указывает на следующую, и каждая вершина также указывает на заголовок различного связанного списка, краев для той определенной вершины.
Что я знаю о том, что я должен сделать:
- Я не знаю, является ли это самым легким, как я сказал выше, но для кратчайшего пути между 2 пользователями, я полагаю, что алгоритм Dijkstra - то, что люди, кажется, рекомендуют довольно часто, таким образом, я думаю, что иду с этим.
- Я искал и искал, и мне трудно реализовать этот алгоритм, кто-либо знает о каком-либо учебном руководстве или чем-то легком для понимания, таким образом, я могу реализовать этот алгоритм сам? Если бы возможно, с примерами исходного кода C, это помогло бы много. Я вижу много примеров с математическими нотациями, но это просто смущает меня еще больше.
- Вы думаете, что помогло бы, "преобразовал" ли я график в матрицу смежности для представления веса ссылок и типа отношения? Было бы легче выполнить алгоритм на этом вместо связанных списков? Я мог легко реализовать функцию, чтобы сделать то преобразование при необходимости. Я говорю это, потому что я получил чувство, что это будет легче после чтения нескольких страниц о предмете, но я мог быть неправым.
- У меня нет идей о других 4 операциях, предложениях?
3 ответа
Список всех пользователей в сети графа с учетом расстояния X
Расстояние X от чего? от начального узла или расстояние X между собой? Вы можете привести пример? Это может быть или не быть таким простым, как поиск BF или запуск Dijkstra.
Предполагая, что вы начинаете с определенного узла и хотите перечислить все узлы, которые имеют расстояния X до начального узла, просто запустите BFS с начального узла.Когда вы собираетесь вставить новый узел в очередь, проверьте, соответствует ли расстояние от начального узла до узла, в который вы хотите вставить новый узел, + вес ребра от узла, из которого вы хотите вставить новый узел, до новый узел <= X . Если он строго ниже, вставьте новый узел, а если он равен, просто распечатайте новый узел (и вставляйте его только в том случае, если у вас также может быть 0 в качестве веса края).
Список всех пользователей в сети графа с учетом расстояния X и типа отношения
См. Выше. Просто учитывайте тип отношения в BFS: если тип родительского элемента отличается от типа узла, который вы пытаетесь вставить в очередь, не вставляйте его.
Вычислить кратчайший путь между 2 пользователями в сети графа с учетом типа отношения
Алгоритм зависит от ряда факторов:
- Как часто вам нужно будет это вычислять?
- Сколько узлов это делает у вас есть?
Поскольку вы хотите легкого, самые легкие - это Рой-Флойд и Дейкстра.
- Использование Рой-Флойда является кубическим по количеству узлов, поэтому неэффективно. Используйте это только в том случае, если вы можете позволить себе запустить его один раз, а затем ответить на каждый запрос в O (1). Используйте это, если вы можете позволить себе хранить в памяти матрицу смежности.
- Диаграмма Дейкстры квадратична по количеству узлов, если вы хотите, чтобы она была простой, но вам придется запускать ее каждый раз, когда вы хотите вычислить расстояние между двумя узлами. Если вы хотите использовать Dijkstra's, используйте список смежности.
Вот реализации C: Рой-Флойд и Дейкстра_1 , Дейкстра_2 .Вы можете многое найти в Google с «<имя алгоритма> c реализация» .
Редактировать: Рой-Флойд исключен для 18 000 узлов, как и матрица смежности. На сборку уйдет слишком много времени и слишком много памяти. Лучше всего использовать алгоритм Дейкстры для каждого запроса, но предпочтительно реализовать Дейкстру с использованием кучи - в приведенных мною ссылках используйте кучу, чтобы найти минимум. Если вы запускаете классический метод Dijkstra для каждого запроса, это также может занять очень много времени.
Другой вариант - использовать алгоритм Беллмана-Форда для каждого запроса, что даст вам O (Узлы * Ребра) время выполнения для каждого запроса. Однако это сильно переоценить, ЕСЛИ вы не реализуете это так, как вам говорит Википедия. Вместо этого используйте очередь, аналогичную той, что используется в BFS. Каждый раз, когда узел обновляет свое расстояние от источника, вставьте этот узел обратно в очередь. Это будет очень быстро на практике, а также будет работать при отрицательных весах. Я предлагаю вам использовать либо это, либо Dijkstra с кучей, поскольку классическая Dijkstra может занять много времени на 18 000 узлов.
Вычислить максимальное расстояние между 2 пользователями в сети графа
Самый простой способ - использовать отслеживание с возвратом: попробовать все возможности и сохранить самый длинный найденный путь. Это NP-полный , поэтому полиномиальных решений не существует.
Это действительно плохо, если у вас 18 000 узлов. Я не знаю ни одного алгоритма (простого или нет), который работал бы достаточно быстро для такого количества узлов. Рассмотрите возможность аппроксимации с помощью жадных алгоритмов.Или, может быть, у вашего графика есть определенные свойства, которыми вы могли бы воспользоваться. Например, это DAG (направленный ациклический граф)?
Вычислить наиболее удаленных подключенных пользователей в сети графа
Это означает, что вы хотите найти диаметр графа. Самый простой способ сделать это - найти расстояния между каждыми двумя узлами (все пары кратчайших путей - либо запустите Рой-Флойда, либо Дейкстру между каждыми двумя узлами и выберите два с максимальным расстоянием).
Опять же, это очень сложно сделать быстро с вашим количеством узлов и ребер. Боюсь, вам не повезло с этими двумя последними вопросами, если только ваш график не имеет особых свойств, которые можно использовать.
Как вы думаете, поможет ли я "преобразовать" граф в матрицу смежности, чтобы представить вес ссылок и тип отношения? Было бы проще применить алгоритм к этому вместо связанных списков? Я мог бы легко реализовать функцию для этого преобразования, когда это необходимо. Я говорю это, потому что у меня возникло чувство, что после прочтения пары страниц по этой теме будет легче, но я могу ошибаться.
Нет, матрица смежности и Рой-Флойд - очень плохая идея, если ваше приложение не предназначено для суперкомпьютеров.
Предполагается, что O (E log V) является приемлемым временем работы, если вы делаете что-то в сети, этого может не быть, и для этого потребуется более мощное оборудование.
- Перечислите всех пользователей в сети графа с учетом расстояния X
Алгоритм Джикстры подходит для этого, для одноразового использования. Вы можете сохранить результат для будущего использования с линейным сканированием по всем вершинам (или еще лучше, с сортировкой и двоичным поиском).
- Перечислите всех пользователей в сети графа с учетом расстояния X и типа отношения
Может быть почти таким же, как указано выше - просто используйте некоторую функцию, где вес будет бесконечным, если это не правильное отношение.
- Вычислить кратчайший путь между двумя пользователями в сети графа с учетом типа отношения
То же, что и выше, по сути, просто определите заранее, соответствуете ли вы двум пользователям. (В качестве альтернативы, вы можете «встретиться посередине» и завершить работу раньше, если вы найдете кого-то на обоих покрывающих дереве кратчайших путей)
- Вычислите максимальное расстояние между двумя пользователями в графовой сети.
Самый длинный путь - это NP-полная задача .
- Вычислить наиболее удаленных подключенных пользователей в сети графов
Это диаметр графа, о котором вы можете прочитать в Math World .
Что касается вопроса между списком смежности и матрицей смежности, это зависит от того, насколько плотно заполнен ваш граф. Кроме того, если вы хотите кэшировать результаты, матрица может быть подходящим вариантом.
Простейший алгоритм вычисления кратчайшего пути между двумя узлами находится Floyd-Warshall . Он просто тройной вложенности циклов for; это оно.
Он вычисляет ВСЕ -пары кратчайшего пути в O (N ^ 3) , поэтому он может выполнить больше работы, чем необходимо, и займет некоторое время, если N огромен.