Список всех пользователей в сети графа с указанным расстоянием X
Расстояние X от чего? от стартового узла или расстояние X между собой? Можете привести пример? Это может быть или не быть так просто, как поиск BF или запуск Dijkstra.
Предполагая, что вы начинаете с определенного узла и хотите перечислить все узлы, которые имеют расстояния X до начального узла, просто запустите BFS от начального узла. Когда вы собираетесь вставить новый узел в очередь, убедитесь, что расстояние от начального узла до узла, с которого вы хотите вставить новый узел, + вес ребра от узла, с которого вы хотите вставить новый узел, до новый узел <= <code>X. Если он строго ниже, вставьте новый узел и, если он равен, просто распечатайте новый узел (и вставьте его только в том случае, если в качестве веса ребра также можно указать 0).
Список всех пользователей в сети графа с указанием расстояния X и типа отношения
Смотри выше. Просто укажите тип отношения в BFS: если тип родителя отличается от типа узла, который вы пытаетесь вставить в очередь, не вставляйте его.
Рассчитать кратчайший путь между двумя пользователями в сети графа с учетом типа отношения
Алгоритм зависит от ряда факторов:
- Как часто вам нужно будет это вычислять?
- Сколько у вас узлов?
Поскольку вы хотите легкого, самые легкие - это Рой-Флойд и Дейкстра.
- Использование Roy-Floyd является кубическим по количеству узлов, поэтому неэффективно. Используйте это только в том случае, если вы можете позволить себе запустить его один раз, а затем ответить на каждый запрос в O (1). Используйте это, если вы можете позволить себе сохранить матрицу смежности в памяти.
- Число Дейкстры является квадратичным по числу узлов, если вы хотите, чтобы оно было простым, но вам придется запускать его каждый раз, когда вы хотите рассчитать расстояние между двумя узлами. Если вы хотите использовать Dijkstra's, используйте список смежности.
Вот реализации C: Рой-Флойд и Dijkstra_1 , Dijkstra_2 . Вы можете найти много на Google с "<algorithm name> c implementation".
Редактировать: Рой-Флойд исключен для 18 000 узлов, как и матрица смежности. Это займет слишком много времени, чтобы построить и слишком много памяти. Лучше всего либо использовать алгоритм Дейкстры для каждого запроса, но предпочтительно реализовать Дейкстру, используя кучу - в приведенных мною ссылках используйте кучу, чтобы найти минимум. Если вы запускаете классическую Dijkstra для каждого запроса, это также может занять очень много времени.
Другим вариантом является использование алгоритма Bellman-Ford для каждого запроса, что даст вам O(Nodes*Edges) время выполнения для каждого запроса. Тем не менее, это большая переоценка, если вы не реализуете это, как вам говорит Википедия. Вместо этого используйте очередь, аналогичную той, которая используется в BFS. Всякий раз, когда узел обновляет свое расстояние от источника, вставьте этот узел обратно в очередь. Это будет очень быстро на практике, а также будет работать для отрицательных весов. Я предлагаю вам использовать эту или Dijkstra с кучей, поскольку классическая Dijkstra может занять много времени на 18 000 узлов.
Рассчитать максимальное расстояние между двумя пользователями в сети графа
Самый простой способ - это вернуться назад: попробуйте все возможности и сохраните самый длинный путь. Это NP-полная , поэтому полиномиальных решений не существует.
Это действительно плохо, если у вас 18 000 узлов, я не знаю ни одного алгоритма (простого или нет), который бы работал достаточно быстро для такого количества узлов. Попробуйте аппроксимировать его, используя жадные алгоритмы. Или, возможно, ваш график имеет определенные свойства, которыми вы могли бы воспользоваться. Например, это DAG (направленный ациклический граф)?
Подсчет самых удаленных подключенных пользователей в сети графа
То есть вы хотите найти диаметр графика. Самый простой способ сделать это - найти расстояния между каждыми двумя узлами (во всех парах кратчайшие пути - либо запустить Roy-Floyd или Dijkstra между каждыми двумя узлами и выбрать два с максимальным расстоянием).
Опять же, это очень сложно сделать быстро с вашим количеством узлов и ребер. Боюсь, вам не повезло с этими двумя последними вопросами, если у вашего графика нет специальных свойств, которые можно использовать.
Как вы думаете, было бы полезно, если бы я "преобразовал" график в матрицу смежности для представления веса ссылок и типа отношений? Будет ли проще выполнить алгоритм на этом, а не на связанных списках? Я мог бы легко реализовать функцию, чтобы сделать это преобразование при необходимости. Я говорю это, потому что у меня было ощущение, что будет легче после прочтения нескольких страниц по этому вопросу, но я могу ошибаться.
Нет, матрица смежности и Рой-Флойд - очень плохая идея, если ваше приложение не предназначено для суперкомпьютеров.