Описание тега graph-algorithm
Алгоритмы графов - это последовательность четко определенных шагов, которые решают проблему, связанную с теорией графов, где граф в этом контексте представляет собой набор вершин ("узлов") и ребер, которые соединяют эти вершины.
2
ответа
Посещение всех узлов и добавление их к пути
Я пытаюсь посетить все узлы, вернуться к началу узла (Neamt) и добавьте посещенные узлы в path но проблема в том, что если я захожу в тупик, город удаляется из path, Вот 1 из возможных path этот код производит: ['Neamt', 'Iasi', 'Vaslui', 'Urziceni'…
20 май '18 в 15:33
4
ответа
Модель ранжирования пользователей
Я пытаюсь разработать простую игру, где группа пользователей может прийти и играть в игру. Исходя из результатов работы пользователя, они получают положительный или отрицательный балл. Я хочу, чтобы два параметра учитывались пользователем weight(кол…
04 апр '12 в 07:02
15
ответов
Когда целесообразно использовать поиск в глубину (DFS) по сравнению с поиском в ширину (BFS)?
Я понимаю разницу между DFS и BFS, но мне интересно знать, когда практичнее использовать один поверх другого? Может ли кто-нибудь привести примеры того, как DFS превзойдет BFS и наоборот?
26 июл '10 в 07:24
1
ответ
Маркировка графа, в которой два цикла делят не более одной вершины
Доброе утро. Мой друг дал мне интересную проблему с графиком, которая описана ниже. Для простого графа, в котором два цикла делят не более одной вершины, как пометить ребра неотрицательным вещественным числом так, чтобы для каждой вершины сумма мето…
15 май '13 в 03:53
2
ответа
Как найти вершины в цикле графа
Например. для 1->2, 2->3, 3->4, 4->2, я хочу напечатать 2, 3, 4. Я попробовал DFS, и когда я нашел вершину, которую я посетил ранее, я иду к родителю, пока я не получить эту вершину, но она не работает хорошо. Иногда это входит в бесконечный цикл. З…
03 май '12 в 08:47
1
ответ
Извлечение подграфа по узлам
Я пытаюсь найти подходы для извлечения подграфа на основе узлов. У нас есть большой граф (направленный или нет), и у нас есть список узлов, которые мы хотим извлечь из графов, но мы хотим извлечь также промежуточные узлы... Когда мы смотрим на извле…
28 ноя '13 в 20:37
1
ответ
Алгоритм Флойда – Варшалла с реконструкцией пути не находит путь
Я пытаюсь найти кратчайший путь между источником и целью, используя алгоритм Флойда-Варшалла, вычисляя кратчайшие пути между всеми парами. Мне нужно найти кратчайший путь, а не только расстояние. Вот что я пытаюсь сделать: Я храню первую вершину на …
01 апр '14 в 14:38
1
ответ
Puzzle 8 Resolver в Python - я не могу пройти все тесты
Мне нужно сделать решатель 8 головоломок с алгоритмами bfs, dfs и A* в python, но у меня есть некоторые проблемы. Я не могу пройти все тесты. Кто-нибудь может мне помочь? РЕДАКТИРОВАТЬ: я отредактировал мой код для работы с одномерным массивом. Это …
06 июл '17 в 14:44
2
ответа
Почему алгоритм Дейкстры использует ключ уменьшения?
Алгоритм Дейкстры научили меня такому while pqueue is not empty: distance, node = pqueue.delete_min() if node has been visited: continue else: mark node as visited if node == target: break for each neighbor of node: pqueue.insert(distance + distance…
13 фев '12 в 04:29
1
ответ
Что такое амортизируемая сложность в Splay Tree?
Я попытался понять амортизированную сложность и сделал несколько поисков в сети, но пока не смог найти хороший ресурс. Так может ли кто-нибудь объяснить, что такое амортизируемая сложность и как она становится O(lg n) в Splay Tree на одну операцию?
01 ноя '13 в 03:48
0
ответов
Улучшение Bellman-Ford до линейного времени выполнения
В алгоритме Джонсона он использует Беллмана-Форда для преобразования графиков с отрицательными весами ребер (без отрицательных циклов) в граф с такими же кратчайшими путями, но все веса ребер неотрицательны - за O(mn) времени. Предположим, нам дан D…
24 апр '18 в 19:35
0
ответов
Используя мой собственный силовой алгоритм с Networkx
Я пытаюсь заставить работать силовой алгоритм, который я пишу. Я не использую тот, который поставляется с Networkx, потому что мы хотим позже изменить его для наших собственных целей. В настоящее время, когда я запускаю его, в строке 54 появляется с…
20 сен '14 в 14:55
2
ответа
Как работает прямое ветвление или листовые узлы (dbl) в алгоритме Tjfast?
Я прочитал алгоритм соответствия шаблонов Twig как алгоритм TJfast. есть функция как dbl(n), параметр n является узлом, и эта функция возвращает прямые ветвящиеся или конечные узлы, но я не могу понять, что название статьи "От кодирования области до…
14 мар '15 в 07:57
2
ответа
Сериализация Python / десериализация двоичного дерева
Я пытаюсь реализовать алгоритм сериализации / десериализации в Python для двоичных деревьев. Вот мой код: class Node: count = 1 def __init__(self, value): self.value = value self.left = None self.right = None def insert(self, value): if self.value &…
23 янв '17 в 22:19
1
ответ
Как сбалансировать входы с выходами этого ориентированного графа?
Тип графика, о котором я думаю, очень специфичен. Я придумал собственное имя для этого: Iode (ГЛАЗ-ода).Это игра "I/O" и электроники "анод" и "катод". МООД Iode берет несколько элементов из связанных с ним входных узлов и равномерно распределяет эле…
13 авг '17 в 18:45
1
ответ
Алгоритм Дейкстры (обновление кучи)
Я реализую алгоритм Дейкстры, используя структуру данных кучи. Я также использую массив, который отслеживает "вероятные минимальные расстояния" узлов. Проблема в том, когда я обновляю массив, как обновить соответствующие значения в куче? хорошо, вот…
29 май '13 в 20:01
1
ответ
Учитывая DAG, удаляйте узлы, которые присутствуют только в путях короче длины 3
Я работаю с направленными ациклическими графами в networkx. У меня есть графики, которые выглядят как на рисунке ниже. По сути, я хочу удалить из этого графа все узлы, которые связаны исключительно с путями длиной менее 3. Например, на приведенном в…
09 сен '16 в 21:27
1
ответ
Формула для расчета групп для графа
Я работал над графиками, используя библиотеку JFreeChart для создания диаграммы. Пример сценария: рассмотрение данных будет в массивах /arraylist. Используя данные таблицы выше, я должен сгенерировать таблицу ниже (первые 2 столбца) и гистограмму Ме…
17 апр '13 в 11:04
2
ответа
Цикл максимального веса на графике
Учитывая взвешенный график (направленный или ненаправленный), мне нужно найти цикл графика с максимальным весом. Вес цикла является суммой веса ребер графа. Это может быть любой цикл, а не только базовый цикл, для которого мы можем найти весь базовы…
06 окт '10 в 16:31
2
ответа
Связь между плотностью ребер и числом вершин графа
Я хочу понять, как вычислить big-O для плотного и разреженного графа. "Алгоритмы в двух словах" говорят, что для разреженного графа O(E) есть O(V), а для плотного графа O(E) ближе к O(V^2). Кто-нибудь знает, как это происходит?
20 фев '12 в 16:32