Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 17.05.2010, 02:36
гость

 
Сообщений: n/a

Поиск всех элементов в дереве
Всем привет! К сожалению, я не силён в дискретке и в теории графов, поэтому не могу подобраться к созданию алгоритма для решения задачи, или хотя бы найти готовый.

Задача состоит вот в чём: есть набор элементов-вершин, которые связаны между собой, связи все односторонние, т.е. если 1->2, то вариант 1<-2 невозможен. Необходимо взяв любой элемент, найти все оставшиеся элементы, которые связаны с ним. Проблема скоре не в том, чтобы найти эти элементы, а в том, что я всегда ухожу в бесконечный цикл, например в случае 1 -> 2, 2->3, 3 -> 1, так как использую рекурсию. Можно конечно использовать глобальные переменные, чтобы проверять есть ли элемент, на котором повторяется цикл, но по-моему должно быть более элегантное решение.
  #2  
Старый 17.05.2010, 03:09
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Необходимо взяв любой элемент, найти все оставшиеся элементы, которые связаны с ним.
Что значит "связаны"? Достижимы из него что-ли?

Цитата:
например в случае 1 -> 2, 2->3, 3 -> 1
Это не есть дерево.

Дерево - неориентированный связный ациклический граф.

Цитата:
так как использую рекурсию. Можно конечно использовать глобальные переменные, чтобы проверять есть ли элемент, на котором повторяется цикл, но по-моему должно быть более элегантное решение.
А в чем проблема? Не нравятся глобальные переменные - заворачивай их в класс. Не нравится рекурсия - используй цикл со стеком.
  #3  
Старый 17.05.2010, 06:27
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Используйте обход в ширину или в глубину (BFS и DFS).
Пройденные вершины придется помечать.
  #4  
Старый 17.05.2010, 15:39
гость

 
Сообщений: n/a

Спасибо.

Я же говорил, что не силён в теории графов. Если это не дерево, то что это?
  #5  
Старый 17.05.2010, 19:11
гость

 
Сообщений: n/a

обычный ориентированный граф
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск в бор-дереве Антон Сортировка и поиск 3 09.04.2010 14:14
Поиск всех путей в графе Eldar Графы 6 21.05.2009 09:53
поиск всех возможных путей из одной вершины, до другой Xavier Teodonius Графы 5 03.05.2009 16:01
Поиск и вкл элементов в дерево гость Оффтопик 0 17.12.2007 18:47
поиск всех максимальных паросочетаний force_sk Графы 1 29.09.2006 09:14