11
голосов
Принятый
Что означает именно такой big O: O(|E|)
Такие Big O типичны для алгоритмов на графах.
Классические обозначения:
|V| - количество вершин в графе (V—от английского "vertices"— это множество вершин)
|E| - количество ребер в графе (E—...
7
голосов
Принятый
Алгоритм Дейкстры тоже самое что двигаться всегда по кратчайшему пути?
Вот вам граф:
1
*-----*
| |
|1 |1
| |
| 2 |
O-----*
Двигаясь просто "по наименьшему ребру", вы получите расстояние между нижними вершинами - 3, не смотря на то, что прямое ребро ...
6
голосов
Задача по поиску кратчайшего пути
Если я правильно понимаю, вам нужно оптимизировать путь для каждой из линий. Учтем что вариантов проведения каждой линии будет (для n>2, где n это ребро поля) 4^((n-2)^2) + 4*3^(n-2) + 8. Таким ...
6
голосов
Принятый
Преобразовать пары родитель-наследник в маршрут
Самый эффективный способ здесь - это проход по дереву от листа к корню. Для этого нужно сначала преобразовать ваш хэш в массив. То есть будет массив p с такими значениями p[] = {0, 0, 3, 1, 1}. Очень ...
6
голосов
Алгоритм Дейкстры, вопрос о весах рёбер графа
Вообще-то алгоритм Дейкстры работает для взвешенного графа с неотрицательными весами ребер.
Естественно, что во взвешенном графе каждое ребро имеет свой вес. Так что эти значения весов ребер не "...
6
голосов
Принятый
Алгоритм Дейкстры: отрицательное ребро на примере
Если исключить из рассмотрения тривиально некорректные постановки задачи (т.е. наличие в графе цикла отрицательного веса), то неприятие алгоритмом Дейкстры ребер с отрицательным весом базируется на ...
5
голосов
Принятый
Какие существуют виды деревьев или классификация деревьев в теории графов?
Раз вы пишите какую-то работу на тему деревьев, то лучше как можно более полно изложить материал.
Часть того, что вы перечислили - общие понятия для графов, часть - понятия для деревьев.
Я бы на ...
5
голосов
Принятый
Второй минимальный путь в алгоритме Дейкстры , не содержащий первый путь полностью
После того как отработала Дейкстра для стартовой вершины мы получили массив d1[] кратчайших расстояний от стартовой точки до любой, теперь запускаем Дейкрсту второй раз, только уже с финиша, получаем ...
5
голосов
Принятый
Максимальный поток
Да, для этого каждая вершина v расщепляется на две:
v- - вершина, в которую будут входить все ребра, которые входили в вершину v
v+ - вершина, из которой будут выходить все ребра, которые выходили из ...
5
голосов
Принятый
Кратчайший путь в графе с дополнительными условиями
Задача на самом деле достаточно простая. Давайте посмотрим на ограничения. 10к вершин. 500км запаса хода максимум (!!). Кстати можно сразу убирать дороги длиннее k, всё равно проехать не сможем.
А ...
5
голосов
Принятый
Поиск и визуализация кратчайшего пути между вершинами графа
Мне данная задача показалась интересной и поэтому я решил сделать рабочий пример, который, возможно, окажется полезным будушим посетителям SO.
import networkx as nx
G = nx.DiGraph()
G....
5
голосов
матрица инцидентности в матрицу смежности реберного графа
По размерам исходной матрицы определяем V и E - количество вершин и рёбер (в программе почему-то подразумевается их равенство).
Далее перебираем все единичные пары по строкам (т.е. находим пары ребер, ...
5
голосов
Принятый
Помогите решить задачу по теории вероятности!
Подойдем к решению, как настоящие программисты - рекурсивно :) От математиков воспользуемся симметрией - понятно, что узлы 2 и 3 равнозначны, как и узлы 4 и 5.
Пусть Среднее количество шагов из узла 1 ...
5
голосов
Принятый
Как наглядно расположить граф в NetworkX?
Выберете одно из возможных расположений (layout) и укажите его явно:
nx.draw(G, pos=nx.spring_layout(G), with_labels=True, node_size=300, arrows=True)
# NOTE: -> ^^^^^^^^^^^^^^^^^^^^^^^^
nx.draw(G,...
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)...
4
голоса
Принятый
Сортировка точек ломаной линии на 2D плоскости
Мне алгоритм решения задачи видится следующим образом:
Найти конец ломаной линии.
Конечную точку поместить в начало массива.
Использовать конечную точку как текущую.
Сравнить расстояния от текущей ...
4
голоса
Принятый
Перебор всех значений связанного графа (С++). Помогите понять в чём проблема
Список visitedIndexesPathArr один используется для всех возможных путей, поэтому за его состоянием нужно внимательно следить. Вы изменили его до рекуррентного вызова, но забыли восстановить в исходное ...
4
голоса
Как переписать DFSR в DFS?
Увеличить стек можно так: Свойства проекта → С/С++ → Командная строка и в поле Дополнительные параметры вписываете /F %количество_байт%, то есть:
/F 20971520 – это стек в 20 Мб
Вот статья об этом на ...
4
голоса
Принятый
Алгоритм Диница поиска максимального потока
Ошибки в приведённом коде следующие:
Вы выводите cout << dinic, однако dinic — это не вызов функции, это указатель на функцию. К сожалению, cout себя с ними ведёт странно, и всегда выводит ...
4
голоса
Принятый
Как смоделировать пошаговый бизнес-процесс в приложении?
Вставлю сюда на всякий случай ремарку, что все нижеописанное является моим мнением, и если я пишу "должно быть", то на самом деле там "должно быть на мой взгляд".
Сама по себе задача - конечный ...
4
голоса
Поиск всех топологических сортировок
Да, конечно. В "Искусстве программирования" Кнута, томе 4А, на стр. 395 есть алгоритм V - Все топологические сортировки.
И вообще, см. раздел 7.2.1.2, на стр. 393-396.
4
голоса
Принятый
Решение задач на Графы С++
Графы - достаточно большая и сложная тема. Но они позволяют решать много интересных задач. Изучать их можно многими способами
читать википедию (да, да, вбиваем слово граф и поехали).
Пойти на мехмат (...
4
голоса
Алгоритм разбиения дерева на компоненты связности
Задачка, кажущаяся на первой взгляд, переборной со сложностью (N -- число вершин), может быть решена проще, быстрее, за полиномиальное время. Почему это так я хочу описать ниже.
Во-первых, кажущийся ...
4
голоса
сгенеририровать список смежности для графа
Из вашего описания не очень понятно, какие именно вершины надо найти. Нельзя просто для каждой вершины перечислить все смежные, у которых больше номер по-порядку? Этим мы гарантируем, что все ребра ...
4
голоса
Принятый
Оптимальный алгоритм на графах
А если так:
Удалить красную вершину и все ребра, примыкающие к ней.
В получившемся графе провести поиск в глубину из синей вершины.
Найденная компонента связности и есть искомый результат.
4
голоса
Принятый
Как в хеш-таблице указать несколько значений к одному ключу? C#
используйте в качестве значения коллекцию элементов, например
table["key"] = new []{"val1", "val2", "val3"};
По поводу графов - если вам нужен константный доступ к ребрам узла по ключу (и массив - ...
4
голоса
Принятый
Найти минимальное расстояние между точками
Идея: строим граф, отбросив все рёбра не удовлетворяющие ограничению. Веса рёбер - расстояния. Дальше ищем кратчайший путь.
Реализация с использованием модулей: Pandas, SciPy, NetworkX:
import ...
4
голоса
Упорядоченный перебор декартового произведения упорядоченных множеств
Какая-то у вас невозможная задача.
Я решал алгоритмом обхода в ширину.
Среднее время поиска следующего кортежа в оптимизированной версии 2-3 микросекунды, максимальное число вершин в очереди порядка ...
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, ...
4
голоса
Посчитать количество графов в котором хотя бы одна вершина имеет степень N - 1
Edit исправил, т.к. первоочередное то, что в первом абзаце, а не то, что в заголовке.
Количество нужных графов из симметрии равно количеству графов, где нет ни одной изолированной вершины. А для них ...
Допускаются только превышающие минимальную длину ответы с наивысшим рейтингом, не являющиеся общими
Связанные метки
графы × 397алгоритм × 190
c++ × 99
python × 66
c# × 42
java × 28
дерево × 26
python-3.x × 19
математика × 19
c × 16
матрицы × 13
networkx × 13
dfs × 13
структуры-данных × 11
javascript × 10
поиск-пути × 9
визуализация × 8
graph × 8
дискретная-математика × 8
массивы × 7
комбинаторика × 7
оптимизация × 6
рекурсия × 6
поиск × 5
база-данных × 4