Вниз
Скачать: 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.009 c
3-83120
Alex-kosmonavt
2003-12-29 10:34
2004.01.26
размен уникальными, ключевыми полями


7-83294
GH@ST
2003-11-06 17:34
2004.01.26
Форма под иконками рабгочего стола


3-83095
Orxan
2003-12-29 17:04
2004.01.26
Ищу DBGrid, в котором:


4-83300
Alexander
2003-11-20 14:24
2004.01.26
Как можно определить, что пользователь А входит в группу В?


1-83171
roa36
2004-01-14 17:06
2004.01.26
Вопрос по работе с EHLib компонентами




   Наверх