ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм поиска все путей между двумя вершинами в ациклическом графе
14 сообщений из 14, страница 1 из 1
Алгоритм поиска все путей между двумя вершинами в ациклическом графе
    #34896430
yanich
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
yanich
Участник
Доброго времени суток ...

Собственно сабж ...
Подскажите, а то что-то сам недокумекаю.
...
Рейтинг: 0 / 0
26.10.2007, 10:05
| Ответить | Цитировать | Написать  
Алгоритм поиска все путей между двумя вершинами в ациклическом графе
    #34896565
ssw
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ssw
Участник
А ты подумай сколько может быть путей в ациклическом графе?

Либо 0 (не связный, орграф), либо 1

Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
26.10.2007, 10:39
| Ответить | Цитировать | Написать  
Алгоритм поиска все путей между двумя вершинами в ациклическом графе
    #34896600
yanich
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
yanich
Участник
ssw
А ты подумай сколько может быть путей в ациклическом графе?

Либо 0 (не связный, орграф), либо 1

Posted via ActualForum NNTP Server 1.4

Ацикличный ориентированный граф и дерево - это разные вещи!

Вот пример графа с тремя путями от вершины 1 до вершины 4:

Ребра:
1->2, 2->3, 1->3, 2->3, 3->4.
Существует 3 пути !!!
...
Рейтинг: 0 / 0
26.10.2007, 10:44
| Ответить | Цитировать | Написать  
Алгоритм поиска все путей между двумя вершинами в ациклическом графе
    #34896659
ssw
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ssw
Участник
Сорри, упустил (вернее поздно вспомнил) про ор-ребра.
Давно я с этим не сталкивался.
Так сходу, может быть стоит приспособить к этому один из алгоритмов поиска минимального пути.

Удачи.

Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
26.10.2007, 10:59
| Ответить | Цитировать | Написать  
Алгоритм поиска все путей между двумя вершинами в ациклическом графе
    #34896704
мод
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
мод
Участник
yanichПодскажите, а то что-то сам недокумекаю.
Рекурсивный перебор с возвратом.
...
Рейтинг: 0 / 0
26.10.2007, 11:10
| Ответить | Цитировать | Написать  
Алгоритм поиска все путей между двумя вершинами в ациклическом графе
    #34896951
1211212
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
1211212
Гость
мод yanichПодскажите, а то что-то сам недокумекаю.
Рекурсивный перебор с возвратом.

не думаю, что это возможно во всех случаях
...
Рейтинг: 0 / 0
26.10.2007, 12:14
| Ответить | Цитировать | Написать  
Алгоритм поиска все путей между двумя вершинами в ациклическом графе
    #34897168
teras
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
teras
Гость
yanich wrote:
> Доброго времени суток ...
>
> Собственно сабж ...
> Подскажите, а то что-то сам недокумекаю.

Поиск в глубину: <http://en.wikipedia.org/wiki/Depth-first_search>.

Например с раскраской: Вначале красишь все вершины в белый цвет, затем
начиная с заданной вершины рекурсивно просматриваешь все соседние белые
вершины, перекрашивая просмотренные в черный. Если увидел целевую,
значит в стеке находится путь.
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
26.10.2007, 13:02
| Ответить | Цитировать | Написать  
Алгоритм поиска все путей между двумя вершинами в ациклическом графе
    #34897373
1211212
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
1211212
Гость
teras
yanich wrote:
> Доброго времени суток ...
>
> Собственно сабж ...
> Подскажите, а то что-то сам недокумекаю.

Поиск в глубину: <http://en.wikipedia.org/wiki/Depth-first_search>.

Например с раскраской: Вначале красишь все вершины в белый цвет, затем
начиная с заданной вершины рекурсивно просматриваешь все соседние белые
вершины, перекрашивая просмотренные в черный. Если увидел целевую,
значит в стеке находится путь.
Posted via ActualForum NNTP Server 1.4

может быть это занудство, но вопрос звучит так "Алгоритм поиска все путей между двумя вершинами в ациклическом графе"
...
Рейтинг: 0 / 0
26.10.2007, 13:53
| Ответить | Цитировать | Написать  
Алгоритм поиска все путей между двумя вершинами в ациклическом графе
    #34897863
мод
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
мод
Участник
1211212не думаю, что это возможно во всех случаях
А в чем вы видите проблему ?
...
Рейтинг: 0 / 0
26.10.2007, 15:40
| Ответить | Цитировать | Написать  
Алгоритм поиска все путей между двумя вершинами в ациклическом графе
    #34897890
1211212
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
1211212
Гость
мод 1211212не думаю, что это возможно во всех случаях
А в чем вы видите проблему ?

Количество вариантов - не более того
...
Рейтинг: 0 / 0
26.10.2007, 15:47
| Ответить | Цитировать | Написать  
Алгоритм поиска все путей между двумя вершинами в ациклическом графе
    #34898033
teras
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
teras
Гость
1211212 teras
yanich wrote:
> Доброго времени суток ...
>
> Собственно сабж ...
> Подскажите, а то что-то сам недокумекаю.

Поиск в глубину: <http://en.wikipedia.org/wiki/Depth-first_search>.

Например с раскраской: Вначале красишь все вершины в белый цвет, затем
начиная с заданной вершины рекурсивно просматриваешь все соседние белые
вершины, перекрашивая просмотренные в черный. Если увидел целевую,
значит в стеке находится путь.
Posted via ActualForum NNTP Server 1.4

может быть это занудство, но вопрос звучит так "Алгоритм поиска все путей между двумя вершинами в ациклическом графе" Ну так - не останавливайся, найдя первый путь, и перекрашивай вершины обратно в белый, после того, как просмотрел все исходящие ребра.
...
Рейтинг: 0 / 0
26.10.2007, 16:18
| Ответить | Цитировать | Написать  
Алгоритм поиска все путей между двумя вершинами в ациклическом графе
    #34900618
мод
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
мод
Участник
Для направленного графа
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
static items:={{ 1 , 2 },{ 1 , 3 },{ 2 , 4 },{ 2 , 5 },{ 3 , 7 },{ 3 , 6 },{ 4 , 7 },{ 7 , 8 },{ 6 , 7 }}

proc main
  tree("", 1 , 7 )

proc tree(path,id1,id2)
  aeval(child_list(id1),{|id|chk(path+str(id1)+"-",id,id2)})

func child_list(id)
  local list:={}
  aeval(items,{|item|iif(item[ 1 ]=id,aadd(list,item[ 2 ]),nil)})
  return list

proc chk(path,id,id2)
  if id=id2
    ?path+str(id2)
  else
    tree(path,id,id2)
  end
Вывод:
1-2-4-7
1-3-7
1-3-6-7
...
Рейтинг: 0 / 0
29.10.2007, 10:19
| Ответить | Цитировать | Написать  
Алгоритм поиска все путей между двумя вершинами в ациклическом графе
    #34903559
yanich
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
yanich
Участник
мод
Ruby чтоли? - давно я на него не смотрел ... Спасибо
...
Рейтинг: 0 / 0
30.10.2007, 09:17
| Ответить | Цитировать | Написать  
Алгоритм поиска все путей между двумя вершинами в ациклическом графе
    #34904390
мод
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
мод
Участник
yanichRuby чтоли? - давно я на него не смотрел ... Спасибо
Хуже - это клиппер :) (что было под рукой)
...
Рейтинг: 0 / 0
30.10.2007, 12:58
| Ответить | Цитировать | Написать  
14 сообщений из 14, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм поиска все путей между двумя вершинами в ациклическом графе
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=34896565&tid=1345743]:
 0ms
get settings:
 9ms
get forum list:
 19ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 178ms
get topic data:
 12ms
get forum data:
 3ms
get page messages:
 74ms
get tp. blocked users:
 1ms
others: 216ms
total:  520ms
созд. / загр.: 520ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]