Вопросы по теме 'directed-acyclic-graphs'
Как назначить уровни вершинам ациклического ориентированного графа?
У меня ациклический ориентированный граф. Я хотел бы назначить уровни каждой вершине таким образом, чтобы гарантировать, что если ребро (v1, v2) находится в графе, то level (v1)> level (v2). Мне также хотелось бы, чтобы level (v1) = level (v3)...
2343 просмотров
schedule
07.11.2022
Комбинаторика в Python
У меня есть своего рода одноуровневая древовидная структура:
Где p — родительские узлы, c — дочерние узлы, а b — гипотетические ветви.
Я хочу найти все комбинации ветвей с ограничением, что только один родитель может разветвляться...
16671 просмотров
schedule
12.06.2022
Как создать оболочку итератора для структуры DAG в Java?
Я хочу иметь итератор над структурой данных. Пока я не знаю, что такое структура данных, может быть, это DAG (ориентированный ациклический граф), а может быть, это может быть и связанный список. Поэтому я хочу обернуть его в итератор и не думать...
1114 просмотров
schedule
11.06.2023
Библиотека с открытым исходным кодом для оперативной анимации ориентированных ациклических графов.
Мне интересно узнать о библиотеках с открытым исходным кодом для анимации "на лету" ориентированных ациклических графов.
Есть много похожих вопросов по рендерингу графиков, но мне не удалось найти ни одного, отвечающего именно этой потребности....
519 просмотров
schedule
01.09.2022
Как построить в Java взвешенный направленный ациклический граф
Я искал похожие темы, но ответы слишком расплывчаты для моего уровня понимания и понимания, и я не думаю, что они достаточно конкретны для моего вопроса.
Похожие темы: Реализация дерева (направленный ациклический граф) Представление DAG...
3265 просмотров
schedule
29.08.2022
найти, существует ли путь определенной длины в ациклическом графе
В ациклическом графе я пытаюсь выяснить, существует ли путь длины L между двумя заданными узлами. Мои вопросы в том, какой лучший и самый простой алгоритм для использования в этом случае.
Обратите внимание, что граф имеет максимум 50 узлов и 100...
2281 просмотров
schedule
17.11.2022
Обход дерева порядка уровней для общего дерева с отображением уровня дерева за уровнем
Я хотел бы отображать древовидную структуру по уровням. Мой текущий код выполняет BFS или обход порядка уровней, но я не могу получить вывод для отображения древовидной структуры, такой как дерево. См. текущий вывод и ожидаемый вывод.
Моя идея...
5919 просмотров
schedule
07.04.2023
Как самая длинная возрастающая подпоследовательность является особым случаем самого длинного пути в DAG?
Я прочитал это утверждение в «Автостопом по алгоритмам». Но я не могу это представить, так как в задаче ЛИС все, что у нас есть, — это последовательность чисел. Как я могу модулировать это как задачу с графом?
1764 просмотров
schedule
17.05.2022
Связь между DAG и поиском пути между двумя узлами в сетке
В руководстве автостопщика по алгоритмам обсуждаются следующие указатели:
1.6 Counting or Optimizing Good Paths
In an n × m grid, we want to go from the left bottom corner to the upper right corner. Each
time we can only take a step to the right,...
153 просмотров
schedule
11.07.2023
ReadOnlyCollection vs Liskov — как правильно моделировать неизменяемые представления изменяемой коллекции
Принцип подстановки Лисков требует, чтобы подтипы удовлетворяли контрактам супертипов. В моем понимании это будет означать, что ReadOnlyCollection<T> нарушает Лисков. Контракт ICollection<T> предоставляет операции Add и Remove ,...
962 просмотров
schedule
18.06.2023
Алгоритмы максимального взвешенного охвата слабосвязной DAG
Существует ли алгоритм для нахождения максимального веса, охватывающего слабосвязный DAG в ориентированном графе, где каждый разрез имеет слабосвязные множества (существует хотя бы один направленный путь от одного множества к другому)? Или это...
1361 просмотров
schedule
27.06.2022
Как разместить дерево с веером в d3.js?
Макет дерева просто великолепен... для деревьев. Выкладываем деревья веером. Вот два разных возможных подхода, которые я рассматриваю:
«упорядочить дерево» DAG, произвольно удалив ребра у любых дочерних элементов с несколькими родителями....
1047 просмотров
schedule
28.08.2022
Минимизировать набор ребер в ориентированном графе, сохраняя компоненты связности
Вот полный вопрос:
Предположим, у нас есть ориентированный граф G = (V, E), мы хотим найти граф G '= (V, E'), который обладает следующими свойствами:
G 'имеет те же компоненты связности, что и G
G 'имеет тот же граф компонентов, что и G
E...
2347 просмотров
schedule
20.08.2022
Есть ли алгоритм, который может найти все критические пути в DAG?
Я пишу статью о некоторых графовых алгоритмах (которые используются в CPM), и мне нужно имя некоторого алгоритма, который может найти все критические пути в DAG. Я просмотрел алгоритм Флойда-Уоршелла и не знаю, может ли он помочь найти все...
1676 просмотров
schedule
11.02.2023
Циклические ориентированные и неориентированные графы
Как определить циклы в
ориентированный граф
неориентированный граф.
Для неориентированного графа ... один из алгоритмов, о которых я подумал, основан на использовании непересекающихся множеств.
for each vertex v in G
Make-set(v)...
1007 просмотров
schedule
20.06.2023
Как найти цикл в ориентированном графе с помощью топологической сортировки?
Я реализовал этот псевдокод в своей программе, чтобы проверить, является ли ориентированный граф ацикличным:
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node...
6303 просмотров
schedule
03.12.2022
Максимальный взвешенный путь между двумя вершинами в направленном ациклическом графе
Люблю некоторые рекомендации по этой проблеме:
G — ориентированный ациклический граф. Вы хотите перейти из вершины c в вершину z. Некоторые преимущества уменьшают вашу прибыль, а некоторые увеличивают ее. Как перейти от c к z, максимизируя...
4791 просмотров
schedule
20.04.2023
Как я могу найти самый дешевый способ в DAG, если у меня ограниченные деньги?
Итак, если у меня есть направленный ациклический граф, где стоимость каждого ребра равна 0 или больше 0, если она больше 0, она будет иметь отрицательный вес (так что вы можете купить ее за 5 долларов, и это сократит ваш путь на -20 например).
Я...
463 просмотров
schedule
27.12.2022
Создать минимально связанный ориентированный ациклический граф
У меня есть ориентированный ациклический простой граф в NetworkX.
Теперь для каждого ребра у этого ребра есть «источник» и «цель». Если существует путь от «источника» к «цели» помимо этого края, то я хочу удалить это ребро.
Есть ли в...
2013 просмотров
schedule
15.05.2022
Кратчайший путь короля на шахматной доске
У меня есть шахматная доска 8х8. Это информация, которую я получаю:
координаты короля
координаты цели
количество заблокированных квадратов
координаты заблокированных квадратов
Я не могу наступать на заблокированные квадраты. Я хочу...
1760 просмотров
schedule
05.05.2023