Вопросы по теме 'topological-sort'
Частичная сортировка заказов?
Скажем, у нас есть несколько элементов, и каждый из них определяет некоторые правила частичной сортировки, например:
Мне A и я хочу быть до B
Мне C и я хочу быть после A , но до D
Итак, у нас есть элементы A,B,C,D со...
5790 просмотров
schedule
01.08.2023
Топологическая сортировка пытается отсортировать вершины или ребра?
Всем счастливой пасхи.
В настоящее время я изучаю топологическую сортировку и задаюсь вопросом о том, какая топологическая сортировка пытается сортировать на самом деле.
В Руководстве по разработке алгоритмов топологическая сортировка...
1850 просмотров
schedule
30.03.2022
Определить, имеет ли ориентированный граф уникальный топологический порядок?
Я пытаюсь создать псевдокод для алгоритма, который сможет определить, имеет ли ориентированный граф уникальный топологический порядок. Я уже придумал следующий псевдокод для топологической сортировки, но что мне нужно добавить или отредактировать,...
1963 просмотров
schedule
23.02.2023
Убедитесь, что данный список узлов графа является правильным топологическим порядком
Мне дали задание написать код, который берет список узлов из графа и определяет, находятся ли они в правильном топологическом порядке.
Граф представляется в памяти следующим образом:
typedef struct graph_t* Graph;
typedef struct node_t* Node;...
4173 просмотров
schedule
13.12.2023
Алгоритм линейного времени для количества различных путей из каждой вершины в ориентированном ациклическом графе
Я работаю над следующим прошлым бумажным вопросом для модуля алгоритмов:
Пусть G = (V, E) — простой ориентированный ациклический граф (DAG). Для пары вершин v, u в V мы говорим, что v достижима из u, если существует (направленный) путь из u в v в...
1313 просмотров
schedule
22.02.2022
Уникальная топологическая сортировка для DAG с несколькими решениями tsort
У меня есть DAG (ориентированный ациклический граф), который имеет более одной допустимой топологической сортировки. Я ищу способ отсортировать его топологически и применить вторичное упорядочение, чтобы всегда получать один и тот же четко...
996 просмотров
schedule
20.02.2022
Линейное упорядочение направленного мультиграфа зависимостей с учетом дубликатов
Описание проблемы
Даны вершины V , которые можно рассматривать как "предложения".
Данные веса:
data W
= Requires -- ^ Denotes that a "proposition" depends on another.
| Invalidates -- ^ Denotes that a "proposition"...
312 просмотров
schedule
11.04.2022
Как кодировать/исследовать несколько линейных порядков DAG
Рассмотрим ориентированный ациклический граф G(V,E) , где V={1,2,3,4,5,6,7} и E={ (1,2),(1,3),(1,4),(2,5),(3,5),(4,6),(5,7),(6,7)}
Проблема здесь состоит в том, чтобы исследовать несколько линейных порядков графа. Следовательно, как...
82 просмотров
schedule
13.07.2022
Может ли ориентированный ациклический граф иметь нулевые ребра?
Предположим, что Graph G - ориентированный ациклический граф с n вершинами. Будет ли это DAG, если я удалю все ребра из графа и сделаю его полностью отключенным?
834 просмотров
schedule
10.05.2022
Топологическая сортировка DAG в C++; структура данных для хранения отсортированного списка?
Я реализовал топологическую сортировку ориентированного ациклического графа на C++, которая выводит топологически отсортированный список.
Я вижу некоторые реализации, в которых отсортированный список хранится в std::stack , а некоторые в...
165 просмотров
schedule
26.06.2023
Представление списка смежности в топологической сортировке
Я видел следующую реализацию топологической сортировки с использованием DFS на Leetcode https://leetcode.com/problems/course-schedule/discuss/58509/18-22-lines-C++-BFSDFS-Solutions
Что меня смущает, так это представление ориентированного графа,...
438 просмотров
schedule
12.06.2022
Сортировка, когда функция сравнения может вернуть значение «не знаю» для определенных пар
Я хотел бы сортировать объекты (или, возможно, строки базы данных) определенным образом. В основном основано на time , но это значение может быть NULL. У меня есть второе значение sequence , которое представляет собой число, указывающее порядок,...
30 просмотров
schedule
06.06.2024
Есть ли разница между dfs и топологической сортировкой? Можно ли добиться топологического упорядочения без использования dfs?
Я пытался написать код для обнаружения цикла в ориентированном графе, и если цикла нет, то вернуть тот же топологический порядок.
Пока я искал его, я столкнулся с различными методами, такими как поиск в глубину и топологическая сортировка, для...
6055 просмотров
schedule
14.11.2023
Топологическая сортировка с использованием алгоритма удаления источника не отображается
В настоящее время я кодирую алгоритм топологической сортировки с использованием алгоритма удаления источника.
Сначала я идентифицировал вершину без входящих ребер в оставшемся орграфе и удалил ее вместе со всеми отходящими от нее ребрами. И...
538 просмотров
schedule
05.05.2022
Как изменить DFS на топологическую сортировку
Я читал о топологической сортировке самостоятельно, но не могу преобразовать псевдокод DFS в TS.
Может ли кто-нибудь объяснить мне, как я могу изменить эту DFS для выполнения топологической сортировки
Может ли кто-нибудь сказать мне, каково...
79 просмотров
schedule
17.10.2023
Минимальное использование памяти в топологической сортировке
Я пишу программу для топологической сортировки ориентированного графа.
Пусть количество вершин равно V ≤ 2000 , а количество ребер равно E ≤ V * (V - 1) / 2 , тогда программа должна использовать меньше памяти, чем 10 * V + 2 * E + 4Mb .
Я...
51 просмотров
schedule
21.11.2022
