Популярные ответы с меткой

11 голосов
Принятый

Что означает именно такой big O: O(|E|)

Такие Big O типичны для алгоритмов на графах. Классические обозначения: |V| - количество вершин в графе (V—от английского "vertices"— это множество вершин) |E| - количество ребер в графе (E—...
Anton Menshov's user avatar
7 голосов
Принятый

Алгоритм Дейкстры тоже самое что двигаться всегда по кратчайшему пути?

Вот вам граф: 1 *-----* | | |1 |1 | | | 2 | O-----* Двигаясь просто "по наименьшему ребру", вы получите расстояние между нижними вершинами - 3, не смотря на то, что прямое ребро ...
Pavel Mayorov's user avatar
6 голосов

Задача по поиску кратчайшего пути

Если я правильно понимаю, вам нужно оптимизировать путь для каждой из линий. Учтем что вариантов проведения каждой линии будет (для n>2, где n это ребро поля) 4^((n-2)^2) + 4*3^(n-2) + 8. Таким ...
Mirdin's user avatar
  • 5,851
6 голосов
Принятый

Преобразовать пары родитель-наследник в маршрут

Самый эффективный способ здесь - это проход по дереву от листа к корню. Для этого нужно сначала преобразовать ваш хэш в массив. То есть будет массив p с такими значениями p[] = {0, 0, 3, 1, 1}. Очень ...
Zealint's user avatar
  • 3,938
6 голосов

Алгоритм Дейкстры, вопрос о весах рёбер графа

Вообще-то алгоритм Дейкстры работает для взвешенного графа с неотрицательными весами ребер. Естественно, что во взвешенном графе каждое ребро имеет свой вес. Так что эти значения весов ребер не "...
Harry's user avatar
  • 217k
6 голосов
Принятый

Алгоритм Дейкстры: отрицательное ребро на примере

Если исключить из рассмотрения тривиально некорректные постановки задачи (т.е. наличие в графе цикла отрицательного веса), то неприятие алгоритмом Дейкстры ребер с отрицательным весом базируется на ...
AnT stands with Russia's user avatar
5 голосов
Принятый

Какие существуют виды деревьев или классификация деревьев в теории графов?

Раз вы пишите какую-то работу на тему деревьев, то лучше как можно более полно изложить материал. Часть того, что вы перечислили - общие понятия для графов, часть - понятия для деревьев. Я бы на ...
iksuy's user avatar
  • 10.5k
5 голосов
Принятый

Второй минимальный путь в алгоритме Дейкстры , не содержащий первый путь полностью

После того как отработала Дейкстра для стартовой вершины мы получили массив d1[] кратчайших расстояний от стартовой точки до любой, теперь запускаем Дейкрсту второй раз, только уже с финиша, получаем ...
Wsl_F's user avatar
  • 276
5 голосов
Принятый

Максимальный поток

Да, для этого каждая вершина v расщепляется на две: v- - вершина, в которую будут входить все ребра, которые входили в вершину v v+ - вершина, из которой будут выходить все ребра, которые выходили из ...
DAle's user avatar
  • 464
5 голосов
Принятый

Кратчайший путь в графе с дополнительными условиями

Задача на самом деле достаточно простая. Давайте посмотрим на ограничения. 10к вершин. 500км запаса хода максимум (!!). Кстати можно сразу убирать дороги длиннее k, всё равно проехать не сможем. А ...
pavel's user avatar
  • 9,799
5 голосов
Принятый

Поиск и визуализация кратчайшего пути между вершинами графа

Мне данная задача показалась интересной и поэтому я решил сделать рабочий пример, который, возможно, окажется полезным будушим посетителям SO. import networkx as nx G = nx.DiGraph() G....
MaxU - stand with Ukraine's user avatar
5 голосов

матрица инцидентности в матрицу смежности реберного графа

По размерам исходной матрицы определяем V и E - количество вершин и рёбер (в программе почему-то подразумевается их равенство). Далее перебираем все единичные пары по строкам (т.е. находим пары ребер, ...
MBo's user avatar
  • 50.5k
5 голосов
Принятый

Помогите решить задачу по теории вероятности!

Подойдем к решению, как настоящие программисты - рекурсивно :) От математиков воспользуемся симметрией - понятно, что узлы 2 и 3 равнозначны, как и узлы 4 и 5. Пусть Среднее количество шагов из узла 1 ...
Harry's user avatar
  • 217k
5 голосов
Принятый

Как наглядно расположить граф в NetworkX?

Выберете одно из возможных расположений (layout) и укажите его явно: nx.draw(G, pos=nx.spring_layout(G), with_labels=True, node_size=300, arrows=True) # NOTE: -> ^^^^^^^^^^^^^^^^^^^^^^^^ nx.draw(G,...
MaxU - stand with Ukraine's user avatar
5 голосов
Принятый

Как из исходного графа сделать новый граф с вершинами соответствующими рёбрам исходного графа?

Если я правильно понял вопрос - можно воспользоваться nx.line_graph(): L = nx.line_graph(G) результат: In [102]: print(L.edges()) [((1, 2), (1, 4)), ((1, 2), (1, 5)), ((1, 2), (1, 3)), ((1, 3), (1, 5)...
MaxU - stand with Ukraine's user avatar
4 голоса
Принятый

Сортировка точек ломаной линии на 2D плоскости

Мне алгоритм решения задачи видится следующим образом: Найти конец ломаной линии. Конечную точку поместить в начало массива. Использовать конечную точку как текущую. Сравнить расстояния от текущей ...
Dmitriy Simushev's user avatar
4 голоса
Принятый

Перебор всех значений связанного графа (С++). Помогите понять в чём проблема

Список visitedIndexesPathArr один используется для всех возможных путей, поэтому за его состоянием нужно внимательно следить. Вы изменили его до рекуррентного вызова, но забыли восстановить в исходное ...
KaZaца's user avatar
  • 3,270
4 голоса

Как переписать DFSR в DFS?

Увеличить стек можно так: Свойства проекта → С/С++ → Командная строка и в поле Дополнительные параметры вписываете /F %количество_байт%, то есть: /F 20971520 – это стек в 20 Мб Вот статья об этом на ...
Flowneee's user avatar
  • 3,789
4 голоса
Принятый

Алгоритм Диница поиска максимального потока

Ошибки в приведённом коде следующие: Вы выводите cout << dinic, однако dinic — это не вызов функции, это указатель на функцию. К сожалению, cout себя с ними ведёт странно, и всегда выводит ...
yeputons's user avatar
  • 852
4 голоса
Принятый

Как смоделировать пошаговый бизнес-процесс в приложении?

Вставлю сюда на всякий случай ремарку, что все нижеописанное является моим мнением, и если я пишу "должно быть", то на самом деле там "должно быть на мой взгляд". Сама по себе задача - конечный ...
etki's user avatar
  • 36.1k
4 голоса

Поиск всех топологических сортировок

Да, конечно. В "Искусстве программирования" Кнута, томе 4А, на стр. 395 есть алгоритм V - Все топологические сортировки. И вообще, см. раздел 7.2.1.2, на стр. 393-396.
Harry's user avatar
  • 217k
4 голоса
Принятый

Решение задач на Графы С++

Графы - достаточно большая и сложная тема. Но они позволяют решать много интересных задач. Изучать их можно многими способами читать википедию (да, да, вбиваем слово граф и поехали). Пойти на мехмат (...
KoVadim's user avatar
  • 112k
4 голоса

Алгоритм разбиения дерева на компоненты связности

Задачка, кажущаяся на первой взгляд, переборной со сложностью (N -- число вершин), может быть решена проще, быстрее, за полиномиальное время. Почему это так я хочу описать ниже. Во-первых, кажущийся ...
hedgehogues's user avatar
  • 9,361
4 голоса

сгенеририровать список смежности для графа

Из вашего описания не очень понятно, какие именно вершины надо найти. Нельзя просто для каждой вершины перечислить все смежные, у которых больше номер по-порядку? Этим мы гарантируем, что все ребра ...
dzhioev's user avatar
  • 11.6k
4 голоса
Принятый

Оптимальный алгоритм на графах

А если так: Удалить красную вершину и все ребра, примыкающие к ней. В получившемся графе провести поиск в глубину из синей вершины. Найденная компонента связности и есть искомый результат.
Инквизитор's user avatar
4 голоса
Принятый

Как в хеш-таблице указать несколько значений к одному ключу? C#

используйте в качестве значения коллекцию элементов, например table["key"] = new []{"val1", "val2", "val3"}; По поводу графов - если вам нужен константный доступ к ребрам узла по ключу (и массив - ...
tym32167's user avatar
  • 32.3k
4 голоса
Принятый

Найти минимальное расстояние между точками

Идея: строим граф, отбросив все рёбра не удовлетворяющие ограничению. Веса рёбер - расстояния. Дальше ищем кратчайший путь. Реализация с использованием модулей: Pandas, SciPy, NetworkX: import ...
MaxU - stand with Ukraine's user avatar
4 голоса

Упорядоченный перебор декартового произведения упорядоченных множеств

Какая-то у вас невозможная задача. Я решал алгоритмом обхода в ширину. Среднее время поиска следующего кортежа в оптимизированной версии 2-3 микросекунды, максимальное число вершин в очереди порядка ...
Pak Uula's user avatar
  • 12.9k
4 голоса
Принятый

Как найти смежные рёбра в графе?

Пример: import matplotlib.pyplot as plt import networkx as nx G = nx.karate_club_graph() nx.draw(G, with_labels=True) список ребер смежных вершине 5: In [231]: G.edges(5) Out[231]: EdgeDataView([(5, ...
MaxU - stand with Ukraine's user avatar
4 голоса

Посчитать количество графов в котором хотя бы одна вершина имеет степень N - 1

Edit исправил, т.к. первоочередное то, что в первом абзаце, а не то, что в заголовке. Количество нужных графов из симметрии равно количеству графов, где нет ни одной изолированной вершины. А для них ...
MBo's user avatar
  • 50.5k

Допускаются только превышающие минимальную длину ответы с наивысшим рейтингом, не являющиеся общими