Коллеги,
есть ли алгоритм , который максимально быстро поможет получить ответ на вопрос есть ли на графе цикл или нету.
Нутром чую что это прогулянная теория графов....-)

если граф обычный, неориентированный, то делаешь поиск в ширину, и сохраняешь множество тех вершин в которых уже был. Если вершина в которую пришел, уже была посещена ранее, то значит есть цикл.

Здравствуйте, dilmah, Вы писали:

D>если граф обычный, неориентированный, то делаешь поиск в ширину, и сохраняешь множество тех вершин в которых уже был. Если вершина в которую пришел, уже была посещена ранее, то значит есть цикл.
Спасибо, задача на самом деле в оригинале такая : есть в системе расширени, которые зависят от других расширений.... нужно найти и предупредить пользователя о цикличной зависимости расширений _)

Здравствуйте, malkolinge, Вы писали:

M>Здравствуйте, dilmah, Вы писали:

D>>если граф обычный, неориентированный, то делаешь поиск в ширину, и сохраняешь множество тех вершин в которых уже был. Если вершина в которую пришел, уже была посещена ранее, то значит есть цикл.
M>Спасибо, задача на самом деле в оригинале такая : есть в системе расширени, которые зависят от других расширений.... нужно найти и предупредить пользователя о цикличной зависимости расширений _)

искать по словами "топологическая сортировка"

D>>если граф обычный, неориентированный, то делаешь поиск в ширину, и сохраняешь множество тех вершин в которых уже был. Если вершина в которую пришел, уже была посещена ранее, то значит есть цикл.
M>Спасибо, задача на самом деле в оригинале такая : есть в системе расширени, которые зависят от других расширений.... нужно найти и предупредить пользователя о цикличной зависимости расширений _)

зависимости -- это стандартная задача с _ориентированным_ графом. Строится ориентированный граф зависимостей. Циклы в нем ищет http://ru.wikipedia.org/wiki/Топологическая_сортировка