Публикации по теме 'topological-sort'
Наглядное объяснение топологической сортировки
Топологическая сортировка - это результат, который вы получаете, когда сортируете дерево в порядке уменьшения времени завершения. Это означает, что вы запускаете алгоритм поиска в глубину, и после его завершения у вас будет два набора значений: время обнаружения и время завершения. Время окончания, отсортированное в обратном порядке, будет генерировать топологически отсортированный список.
DFS начинает обход дерева в вершине A. Поскольку оно было обнаружено, мы помечаем его цифрой..
График — Чужой Словарь
LeetCode: https://leetcode.com/problems/alien-dictionary/
Существует новый инопланетный язык, использующий латинский алфавит. Однако порядок букв вам неизвестен. Вы получаете список непустых слов из словаря, где слова отсортированы лексикографически по правилам этого нового языка . Выведите порядок букв в этом языке.
Input:
[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]
Output: "wertf"
Input:
[
"z",
"x"
]
Output: "zx"
Input:
[
"z",
"x",
"z"
]..
Топологическая сортировка с помощью алгоритма Кана
Информатика
Топологическая сортировка с помощью алгоритма Кана
Вы могли встретить термин «топологическая сортировка или упорядочение» при решении проблем, связанных с разрешением зависимостей, планированием задач и т. Д. Это чрезвычайно полезный метод, который находит применение в нескольких реальных приложениях.
Прежде чем переходить к деталям, давайте сначала разберемся, что такое топологическая сортировка и зачем она нам нужна. Давайте рассмотрим пример большого проекта, который..
Вопросы по теме 'topological-sort'
Топологическая сортировка с использованием LINQ
У меня есть список элементов, которые имеют отношение частичного порядка , т.е. д., список можно рассматривать как частично упорядоченный набор . Я хочу отсортировать этот список так же, как в этом вопросе . Как правильно ответили там, это...
4606 просмотров
schedule
09.08.2023
Топологическая сортировка в OCaml
Я пытаюсь написать топологическую сортировку в ocaml, но я новичок (в алгоритмах OCaml и графов) и не могу сделать это сам.
Мне проще думать о топологической сортировке, например, в C ++ (а примеров топологической сортировки на C ++ в Интернете...
4466 просмотров
schedule
04.04.2022
Запуск ациклического графа, ориентированного на службы
Фреймворк, с которым я работаю, состоит из сервисов с отслеживанием состояния, которые зависят от других сервисов, образуя направленный ациклический граф http://en.wikipedia.org/wiki/Directed_acyclic_graph
Хочу как можно эффективнее запускать...
609 просмотров
schedule
11.05.2022
Проблема коммивояжера с дополнительным частичным заказом
Я ищу название этой проблемы или какие-либо сведения о алгоритме или исходном коде :
Пример: вы хотите найти лучший маршрут для посещения 100 крупнейших городов США (классический TSP), но прежде чем вы сможете посетить какой-либо конкретный...
1607 просмотров
schedule
25.12.2021
Как сделать топосорт; создание степеней
Я строю структуру графа для школьного задания. В настоящее время он представлен в виде списка смежности: я использую хэш-карту, в которой ключами являются узлы (вершины) графа, а значениями являются списки ребер (объекты, содержащие указатель...
285 просмотров
schedule
17.08.2023
Каково максимальное количество возможных топологических видов прямого ациклического графа N-го порядка?
Мне нужно найти максимальное количество топологических сортировок на прямом ациклическом графе N-порядка. Я проверил, запустив алгоритм поиска в глубину на различных прямых ациклических графиках, и похоже, что это размер леса алгоритма поиска в...
7309 просмотров
schedule
13.02.2023
Зачем использовать DFS для поиска циклов в неориентированном графе и топологической сортировки для поиска циклов в ориентированном графе?
Для неориентированных графов, если нам нужно найти цикл, мы используем поиск в глубину, как описано в этом старый вопрос , который является хорошо известным и оптимальным методом.
Но для ориентированного графа этот другой вопрос предлагает...
4728 просмотров
schedule
26.04.2023
Поиск кратчайших путей с помощью python-IGraph в группах DAG с отрицательными весами
Задача : найти кратчайший путь для DAG (направленного ациклического графа) с отрицательными весами, используя интерфейс Python для библиотеки igraph в виде списка ребер / вершин в настройке с одним источником / одной целью.
Попытка: наиболее...
1618 просмотров
schedule
04.01.2022
Является ли эта топологическая сортировка в Ruby ошибочной?
Я смотрел на топологическую сортировку, и это казалось очень сложным. Я придумал это, и, кажется, он работает со всеми примерами, которые я смог найти. Является ли эта логика ошибочной?
@tsort_array = []
def tsort item, dependencies_array
if...
438 просмотров
schedule
07.03.2023
Топологическая сортировка для ориентированного ациклического графа
Возможны ли разные топологические сорта для ориентированного ациклического графа G? Например, на графике:
A --> B --> D
B --> E
A --> C --> E
Я думал, что топологические сортировки зависят от времени завершения каждой...
1814 просмотров
schedule
17.05.2022
Топологическая сортировка ориентированного ациклического графа
Как бы вы вывести все возможные топологические сортировки для ориентированного ациклического графа? Например, для графика, где V указывает на W и X, W указывает на Y и Z, а X указывает на Z:
V --> W --> Y
W --> Z
V --> X -->...
2854 просмотров
schedule
04.03.2022
Топологический вид DAG
У меня есть даг (Дерево), в котором направленные ребра бывают только трех видов:
Слева направо (братья и сестры)
Ребенок к родителю
Родитель для ребенка
В частности, проблема заключается в оценке дерева синтаксического анализа атрибутов,...
212 просмотров
schedule
22.11.2022
Объединение недостижимых вершин в DAG может создать цикл?
У меня есть DAG (ориентированный ациклический граф), в котором мне нужно объединить некоторые вершины, которые недостижимы друг от друга. Мой последний график должен быть DAG. Мой вопрос заключается в том, что, выполняя эту операцию, может ли...
59 просмотров
schedule
07.03.2023
Топологическая сортировка, поиск зависимостей быстрее
Я работаю над проблемой графа уже несколько месяцев, и сейчас я ищу новый вклад от других.
Я провожу часы в библиотеке и берусь за книги. Я вполне уверен, что нашел решение, но, возможно, кто-то здесь может дать мне новую точку зрения....
486 просмотров
schedule
08.10.2022
Поиск приоритета символов в словаре
** Учитывая словарь строк [строки в отсортированном порядке], вы должны найти приоритет символов в соответствии со словарем.
есть бкси
e ранжируется выше b согласно словарю!**
Я попытался решить этот вопрос с помощью топологической...
144 просмотров
schedule
06.08.2023
Алгоритмы — поиск в глубину графа
Я изучаю график и DFS и пытаюсь сделать что-то похожее на то, как ANT разрешает зависимость. Я что-то запутался, и все статьи, которые я читал, предполагают, что все это знают.
Я думаю иметь Map> с ключом = файл, а значение = набор файлов, от...
171 просмотров
schedule
28.09.2022
Если топологическая сортировка использует поиск в глубину, как она может быть успешной на несвязанных графах?
В моих знаниях есть пробел, но я не уверен, где именно. Топологическая сортировка может быть выполнена с использованием поиска в глубину, как объясняет Википедия . Однако я видел только поиск в глубину, реализованный для деревьев, тогда как...
6891 просмотров
schedule
22.05.2023
DAG и высшая сортировка
«Упорядочивание вершин DAG в соответствии с возрастающим предварительным номером приводит к топологической сортировке». по-видимому, не является истинным утверждением, но я не понимаю, почему это не так. Если граф ориентирован и не имеет циклов, то...
159 просмотров
schedule
20.05.2022
Правильное использование топологической сортировки в алгоритмах
Дан отсортированный словарь чужого языка, содержащий N слов и k начальных алфавитов стандартного словаря, задача состоит в том, чтобы завершить функцию, которая возвращает строку, обозначающую порядок символов в языке.
Input: Dict[] = { "baa",...
718 просмотров
schedule
08.05.2023
Проверка того, сохраняется ли топологический порядок одного графа в другом
Если у меня есть набор узлов N и набор вершин V_1 , которые определяют граф G_1 с определенным топологическим порядком, как я могу проверить, поддерживает ли подмножество узлов из N и новый набор вершин V_2 , которые определяют граф G_2 ,...
283 просмотров
schedule
28.05.2022
