Форум: "Потрепаться";
Текущий архив: 2004.01.26;
Скачать: [xml.tar.bz2];
ВнизЕщё графовый алгоритм Найти похожие ветки
← →
asdqwer (2004-01-05 11:26) [0]Нужно найти в ориентированном графе (т.е. со стрелочками :-) такую вершину, у которой глубина дерева минимальна или можно эту самую глубину. Я имею ввиду, что из той вершины можно будет "обойти" весь граф быстрее всего, думаю это понятно. Заранее спасибо.
← →
Ega23 (2004-01-05 11:28) [1]Ту не в Дубне, случайно, учишься?
← →
pasha_golub (2004-01-05 11:52) [2]Разновидность алгоритма Дейкстры нахождения кратчайнего пути, назывется, если я конечно не ошибаюсь, алгоритм Уоршела. Сложность О(n^3). Это просто алгоритм Дейкстры примененный по очереди ко всем узлам графа. Ориентированный или нет - это не важно. Надо будет составить только таблицу инцидентности
← →
Romkin (2004-01-05 11:55) [3]По-моему, алгоритм Дейкстры для ориентированных графов не работает... Или наоборот?
← →
JibSkeart (2004-01-05 12:14) [4]2 Romkin
ориентированый граф грубо говоря который имеет напровление , так если помню еще :) ,
а у меня задача такая стояла и я ее реализовал именно через
алгоритм Дейкстры нахождения кратчайнего пути ...
← →
DAC (2004-01-05 12:24) [5]Может снчала нужно определиться: ориентированый граф или дерево?
Для дерева - обычная задача балансировки.
← →
pasha_golub (2004-01-05 21:42) [6]2Romkin
Алгоритм Дейкстры работает с таблицей (матрицей) инцидентности, емцу накакать на ориентированность, просто матрица будет не симметрична. :-)
2JibSkeart
Ориентированный граф, это у которого связи имеют направление, но не всегда однонаправленное. Представим себе ситуайию. Из города А в город В построена новейшая магистраль в три полосы, а из города В в город А идет маленькая узенькая дорога. Так вот связь тут двухсторонняя, но пропускаемость разная. Такого рода велечины назыают весом связи (или узла в зависимости от задачи). И тогда встают задачи о взвешенных графах. Так вот ориентированный граф - это частный случай взвешенного графа.
2DAC
Дерево - частный случай графа и не более.
Страницы: 1 вся ветка
Форум: "Потрепаться";
Текущий архив: 2004.01.26;
Скачать: [xml.tar.bz2];
Память: 0.46 MB
Время: 0.004 c