Публикации по теме 'topological-sort'
Топологическая сортировка графов — Алгоритм Кана
В другой статье ( Топологическая сортировка графа — реализация JavaScript ) я реализую топологическую сортировку с использованием DFS, вот реализация алгоритма Кана, вдохновленная этим обучающим видео:
Алгоритм Кана
Повторно удалять вершины без каких-либо зависимостей из графа и добавлять их в массив топологического упорядочения. Когда одна вершина удаляется, ее соседи становятся свободными, поэтому они являются кандидатами на следующее удаление. Продолжайте удалять вершины без..
Вопросы по теме 'topological-sort'
Алгоритм топологической сортировки при наличии циклов
Некоторые языки программирования (например, haskell ) допускают циклические зависимости между модули. Поскольку компилятору необходимо знать все определения всех модулей, импортированных при компиляции одного модуля, обычно ему приходится...
13058 просмотров
schedule
30.04.2022
Топологическая сортировка с использованием std::sort
Примечание. Написав этот вопрос, я думаю, что уже нашел ответ. Не стесняйтесь исправлять или дополнять его лучшей версией. Я подумал, что было бы неплохо задокументировать мою проблему. редактировать Я был неправ, мой ответ был неверным....
2617 просмотров
schedule
02.01.2023
Итеративная/динамическая топологическая сортировка для чайников
В настоящее время я реализую динамический граф DAG на C++ — он будет отображаться через пользовательский интерфейс для пользователя, а вставка/удаление узлов/ребер будет обычными операциями.
Размер графиков потенциально может варьироваться от очень...
1539 просмотров
schedule
30.05.2022
Уникальная топологическая сортировка подразумевает существование гамильтонова пути
В DAG, чтобы найти гамильтонов путь, сначала обнаруживается топологическая сортировка, а затем находится гамильтонов путь из топологической сортировки.
Hamiltonian path in a DAG exists if and only if there is unique topological sorting.
Как...
3002 просмотров
schedule
26.02.2023
Преобразование рекурсивной топологической сортировки на основе DFS в нерекурсивный алгоритм (без потери обнаружения цикла)
Вот псевдокод топологической сортировки из Википедии:
L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
select an unmarked node n
visit(n)
function visit(node n)
if n has a temporary mark then stop...
779 просмотров
schedule
30.03.2022
Оптимизация топологической сортировки
Итак, в настоящее время я работаю над изометрической игрой, основанной на тайлах, и я использую топологическую сортировку, чтобы отсортировать порядок тайлов, которые будут отображаться. Что ж, топологическая сортировка на самом деле определяет...
396 просмотров
schedule
15.06.2022
Как мне сделать мою топологическую сортировку линейной по времени? (Код хорошо аннотирован)
Вопрос 1:
Каким должно быть правильное время работы для хорошо реализованной топологической сортировки. Я вижу разные мнения:
Википедия говорит: O(log^2(n))
Geeksforgeeks говорит: O(V+E)
Вопрос 2:
Моя реализация работает на O(V*E)....
184 просмотров
schedule
14.03.2023
Объединить большинство черных вершин DAG вместе, чтобы он остался DAG?
У меня есть DAG (направленный ациклический граф) с вершинами, имеющими любой из двух цветов: черный или белый. Мне нужно объединить как можно больше черных вершин вместе с ограничением, что граф должен оставаться ациклическим. Следовательно,...
258 просмотров
schedule
04.10.2023
Обнаружение цикла ациклического графа, ориентированного на один корень
Граф имеет только один корень. И сохраняется в следующем формате:
0 -> 1,
0 -> 2,
1 -> 3,
1 -> 4,
2 -> 4,
2 -> 5,
4 -> 5,
5 -> 2 (This is the cycle)
Каков наиболее эффективный способ определить, существует ли в графе...
215 просмотров
schedule
03.06.2022
Как определить, имеет ли граф неуникальную топологическую сортировку
Я создал программу, которая упорядочивает граф по топологической сортировке по заданной диаграмме. Я определил 3 результата:
ok
существующие циклы
недостающая информация
Вывод первых двух пунктов правильный, а третьего нет. Например,...
1451 просмотров
schedule
15.03.2023
SQL-запрос для топологической сортировки
У меня есть ориентированный ациклический граф:
DROP TABLE IF EXISTS #Edges
CREATE TABLE #Edges(from_node int, to_node int);
INSERT INTO #Edges VALUES (1,2),(1,3),(1,4),(5,1);
Я хочу перечислить все узлы, всегда перечисляя узел до его...
294 просмотров
schedule
24.02.2023
