Tavix Junior Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору Вот такая проблема: зная матрицу смежности ориентированного графа, нужно проверить, является ли одна вершина достижима из другой.   Вообще, нужен алгоритм, но от программы на c//c++ не откажусь Может кто знает, где, вообще, это можно посмотреть??? Всего записей: 33 | Зарегистр. 18-12-2002 | Отправлено: 16:08 15-05-2004

pazlik Junior Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору Tavix Делал что то подобное около года назад. Если найду отправлю на мыло. Всего записей: 195 | Зарегистр. 14-08-2003 | Отправлено: 18:26 15-05-2004

Tavix Junior Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору pazlik если не сложно, отправь ... Tavix@ngs.ru Заранее спасибо! Всего записей: 33 | Зарегистр. 18-12-2002 | Отправлено: 19:25 15-05-2004

WiseAlex Софтовых дел М... Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору Насколько помню есть алгоритм обхода в ширину берем первую вершину и помечаем ее каким-либо способом (в оригинале алгоритма цветом) например числом 1.   далее цикл из всех вершин, помеченные текущей меткой, находим все доступные вершины по матрице смежности и помечаем их. (например на 1 больше номера текущей вершины).   Если ни одной новой вершины не найдено, или дошли до нужной, то кончено. Увеличиваем номер текущей вершины. и повторяем цикл ---   Всего записей: 1001 | Зарегистр. 02-03-2003 | Отправлено: 22:39 15-05-2004

WiseAlex Софтовых дел М... Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору krast Цитата: которые еще не были помечены.   Очень точное замечание, спасибо Всего записей: 1001 | Зарегистр. 02-03-2003 | Отправлено: 20:36 16-05-2004

Tavix Junior Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору Вот такая идея ко мне пришла (с помощью вашей помощи, конечно): я возьму, к примеру, очередь и буду пишать туда нечто, издали напоминающее дерево. Вот тут возникает проблема, что меня может перекидывать очередной узел наверх. Но этого можно избежать, если проверять, есть ли уже такой элемент в очереди. "Постороив" такое дерево, используя обход в ширену, я пройду по дереву, пока очередь не пуста или пока не найден нужный мне путь.   Так? Всего записей: 33 | Зарегистр. 18-12-2002 | Отправлено: 10:40 17-05-2004

UncoNNecteD Silver Member Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору Tavix Просто ставь метки там где уже был. ---------- -= Я тут чертовски давно =- Всего записей: 4040 | Зарегистр. 21-03-2002 | Отправлено: 10:48 17-05-2004

Sleepwalker Advanced Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору если я не ошибаюсь, алгоритм просто до безобразия... нужно ведь только достижимость проверить? еще и на ориентированном графе... вообще фигня.. строишь матрицу достижимостей (ну допустим, перекресток гориз-верт - достижимость вертикали из горизонтали)... и поехали... рекурсивная процедура перехода, переходишь на новую вершину, при этом вычеркиваешь столбец исходной, дабы не возвращаться... и так до тех пор пока не дойдешь... если перехода нет - откатываешь назад (при рекурсии это автоматически произойдет). ---------- ...или я ничего не понимаю в этой жизни... или понимаю слишком хорошо... Всего записей: 1957 | Зарегистр. 19-10-2002 | Отправлено: 12:47 17-05-2004

WiseAlex Софтовых дел М... Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору Tavix Цитата: я возьму, к примеру, очередь и буду пишать туда нечто, издали напоминающее дерево. А зачем так сложно? Я в свое время делал так - матрица смежности обычная квадратная таблица (например м), а метки массив.(например а). ставишь 1 в а[i]  где i номер начальной вершины, а затем гоняешь по этом массиву (а)  и смотришь на текущий индекс, проверяешь по матрице куда можно дойти и ставишь там метку+1 Всего записей: 1001 | Зарегистр. 02-03-2003 | Отправлено: 14:41 17-05-2004

Sleepwalker Advanced Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору WiseAlex то же самое небольшая вариация ---------- ...или я ничего не понимаю в этой жизни... или понимаю слишком хорошо... Всего записей: 1957 | Зарегистр. 19-10-2002 | Отправлено: 09:34 18-05-2004

krast Full Member Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору Sleepwalker Цитата: рекурсивная процедура перехода, переходишь на новую вершину, при этом вычеркиваешь столбец исходной, дабы не возвращаться... и так до тех пор пока не дойдешь...   привет, слип. то что ты пишешь - это всего лишь - алгоритм с возвратом - тупой до безобразия, волновой алгоритм - имхо лучше,  это действительно так. А если еще говорить, что я вообще против рекурсии и стараюсь всегда ее развернуть во что-то более удобо варимое, то.... ну ты понял меня, дружище Всего записей: 442 | Зарегистр. 15-09-2003 | Отправлено: 20:52 18-05-2004

Tavix Junior Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору Ребят, давайте не будем спорить! СПАСИБО всем ОГРОМНОЕ!!!!!!!!!!!!!!!!!!!!!! Я написал, осталось только отчет написать и можно сдавать Sleepwalker Рекурсия - великая вещь, здорово упрощающая некоторые алгоритмы (например, прямой, обратный, концевой для бинарных деревьев), но на рекурсивные переходы требуется гораздо больше времени, чем, например, на цикл... Тем не менее, я обошелся без нее   Всего записей: 33 | Зарегистр. 18-12-2002 | Отправлено: 16:43 19-05-2004

krast Full Member Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору Tavix Цитата: Ребят, давайте не будем спорить а как же истина, которая с спорах... того...   Цитата: Рекурсия - великая вещь, здорово упрощающая некоторые алгоритмы   в силу своей сегодняшней язвительности отмечу, что по большей части она упрощает только читабельность (как пример - как красиво читать рекурсивный алгоритм генерации чисел Фибоначчи - сказка - но зато какой он не оптимальный - кошмар!)? и все!   а что это: Цитата: прямой, обратный, концевой для бинарных деревьев это что за алгоритмы такие? обходы что ли, или как? кстати, любое дерево можно преобразовать в бинарное по схеме - левый_ребенок-правый_брат, так что разницы в этом плане нет Всего записей: 442 | Зарегистр. 15-09-2003 | Отправлено: 17:31 19-05-2004 | Исправлено: krast, 17:36 19-05-2004

Tavix Junior Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору Цитата: так что разницы в этом плане нет Да.   При прямом обходе просматриватся корень -> левое поддерево (в прямом обходе) - >правое поддерево (в прямом обходе) При обратном:  просматриватся левое поддерево ->корень  - >правое поддерево При концевом:  просматриватся левое поддерево ->правое поддерево ->корень       Всего записей: 33 | Зарегистр. 18-12-2002 | Отправлено: 12:34 24-05-2004

krast Full Member Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору Tavix это конечно прикольно но мне больше нравится названия сих блужданий по Столмену:   parent - left child - right child итд...   и не надо заучивать странные названия   Всего записей: 442 | Зарегистр. 15-09-2003 | Отправлено: 13:05 24-05-2004 | Исправлено: krast, 13:07 24-05-2004

Tavix Junior Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору CrazY AngeL И какого хера ты тут делаешь? Цитата: Знает только то что говорили на лекциях Ты так вообще на лекции не ходишь... Я то хоть че-то знаю, а ты помнишь только то, что в садике научили....   Всего записей: 33 | Зарегистр. 18-12-2002 | Отправлено: 09:18 26-05-2004

Компьютерный форум Ru.Board » Компьютеры » Прикладное программирование » Обход ориентированного графа

Переход по форумам  Закладки   » Компьютеры Цифровое изображение Программы Microsoft Windows UNIX Другие OS Hardware В помощь сисадмину Прикладное программирование Игры Форумные игры   » Интернет Web-программирование В помощь вебмастеру Графика Хостинг Зацените-ка!   » Тематические Ikonboard v.2 Ikonboard v.3 Invision Board Другие форумы PHP-Nuke и другие порталы Мобила   » Общие Спорт Флейм Темы по региональным встречам Музыка и Кино Юмор Литература и Живопись   » Ru.Board Новости Помощь по форуму   » Андеграунд eBookz Варезник Раздачи и акции Мобильный варезник Андеграунд Игры и фильмы   » Специальные Тестирование