Итерация графика снизу вверх по алгоритму? - PullRequest
Новая
       34

Итерация графика снизу вверх по алгоритму?

1 голос
/ 05 марта 2011

Учитывая этот график зависимостей: что такое «хороший» подход для его перебора снизу вверх?

Мои ожидаемые результаты для каждого "цикла": 

Iteration step "1": Project B, Project D, Project Z, Project O 
Iteration step "2": Project C, Project W, Project V, Project Q
Iteration step "3": Project A, Project M
Iteration step "4": Start X // End

Мозговой штурм 

// PSEUDO CODE: Find and return "next projects fixes" to perform. 
// -> All projects with no or already fixed dependencies. 
FUNC FindNextDependciesToFix ( NODE StartNode, BYREF LIST<NODE> RefNextProjectsToFix )
{    
 ... // Algorithm ?
}

Причина, по которой «поиск в глубину» не работает: 

DO
{
 FindNextDependciesToFix (StartX, FixNextList);
 CallASYNCAndWaitForEndOfFix (FixNextList);
 // <- Wait till end of project fix (async...) 
} WHILE ( FixNextList.IsEmpty() );

Алгоритм

Я действительно не хочу изобретать велосипед:уже есть алгоритм, который решает эту проблему, или у кого-нибудь есть «умный» подход?

Ответы [ 2 ]

1 голос
/ 05 марта 2011

Вы, вероятно, хотите, чтобы топологическая сортировка прошла через график зависимостей. Вы можете сделать это также с помощью DFS (поиск в глубину) и BFS (поиск в выдохе) - оба упомянуты в псевдокоде по ссылке в википедии. Оба являются линейными по размеру ввода.

0 голосов
/ 05 марта 2011

Выполните топологическую сортировку , которая дает узлы в порядке глубины.Затем, если вы хотите найти границы между различными глубинами, используйте алгоритм динамического программирования.Это решение является линейным по размеру графа O (| V | + | E |).

...