Вниз
Скачать: CL | DM;

Ещё графовый алгоритм   Найти похожие ветки 

← →
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 вся ветка

Скачать: CL | DM;



Память: 0.46 MB
Время: 0.008 c
4-83310
Sirakuz
2003-11-20 16:33
2004.01.26
запись в файл в удалённой расшаренной папке


6-83225
S@shka
2003-11-23 01:51
2004.01.26
POP3


6-83228
Кен
2003-11-23 06:24
2004.01.26
Как в IE реализовано перетаскивание картинок из браузера на


3-83107
belyh
2003-12-30 00:31
2004.01.26
SQL DATE >=


1-83150
FREEMAN
2004-01-15 11:54
2004.01.26
Копирование файлов по битам




   Наверх