Форум: Форум PHPФорум ApacheФорум Регулярные ВыраженияФорум MySQLHTML+CSS+JavaScriptФорум FlashРазное
Новые темы: 0000000
MySQL 5. В подлиннике. Авторы: Кузнецов М.В., Симдянов И.В. C++. Мастер-класс в задачах и примерах. Авторы: Кузнецов М.В., Симдянов И.В. Объектно-ориентированное программирование на PHP. Авторы: Кузнецов М.В., Симдянов И.В. PHP на примерах (2 издание). Авторы: Кузнецов М.В., Симдянов И.В. PHP Puzzles. Авторы: Кузнецов М.В., Симдянов И.В.
ВСЕ НАШИ КНИГИ
Консультационный центр SoftTime

Форум PHP

Выбрать другой форум

 

Здравствуйте, Посетитель!

вид форума:
Линейный форум Структурный форум

тема: Алгоритм обхода дерева
 
 автор: fsn   (11.06.2008 в 16:41)   письмо автору
25.5 Кб
 
 

Помогите написать алгоритм, решение где-то вертится теоретически, но практически написать не могу.
Имеется дерево, смотрите рисунок в прикрепленном файле. Здесь я упростил его, на самом деле узлов дерева гораздо больше. В базе данных MySQL имеется две таблицы:
1 таблица - список всех узлов дерева
id name
1 1
2 2
3 3
4 4
5 5
6 6

2 таблица - узлы, примыкающие к узлу в первой таблице
id_1 name_1 id
1 2 1
2 3 1
3 4 2
4 5 2
5 1 2
6 6 3
7 1 3
8 5 3
9 2 4
10 2 5
11 3 5
12 3 6

На форме пользователь выбирает из списка узлов дерева начальную точку и конечную точку, допустим: узел5 и узел6 соответственно. Надо найти все маршруты от узла5 к узлу6.
Маршрут1 = 5-1-3-6.
Маршрут2 = 5-3-6.
Может кто-то такое делал? Помогите.
Заранее благодарен.

   
 
 автор: Trianon   (11.06.2008 в 16:59)   письмо автору
 
   для: fsn   (11.06.2008 в 16:41)
 

1 - 2 - 5 - 3 - 1 -- это не дерево. В дереве циклов быть не может.

   
 
 автор: fsn   (11.06.2008 в 17:01)   письмо автору
 
   для: Trianon   (11.06.2008 в 16:59)
 

Ну хорошо, пусть будет - граф. Или уберите ребро 3-5, я чуть ступил, рисуя пример.

   
Rambler's Top100
вверх

Rambler's Top100 Яндекс.Метрика Яндекс цитирования